【js】-【树】-学习笔记

声明：本笔记是根据掘金小册总结的，如果要学习更多细节，请移步https://juejin.cn/book/6844733800300150797

1 二叉树

在 JS 中，二叉树使用对象来定义。它的结构分为三块：
数据域
左侧子结点（左子树根结点）的引用
右侧子结点（右子树根结点）的引用

1. 定义二叉树构造函数

// 二叉树结点的构造函数
function TreeNode(val) {
    
    this.val = val;
    this.left = this.right = null;
}

2. 新建一个二叉树结点

const node  = new TreeNode(1)

1.1 先序遍历

// 所有遍历函数的入参都是树的根结点对象
function preorder(root) {
    
   # 递归边界，root 为空
    if(!root) {
    
        return 
    }
     
    # 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
    // 递归遍历左子树 
    preorder(root.left)  
    // 递归遍历右子树 
    preorder(root.right)
}

1.2 中序遍历

# 所有遍历函数的入参都是树的根结点对象
function inorder(root) {
    
    // 递归边界，root 为空
    if(!root) {
    
        return 
    }
     
    // 递归遍历左子树 
    inorder(root.left)  
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
    // 递归遍历右子树 
    inorder(root.right)
}

1.3 后序遍历

function postorder(root) {
    
    // 递归边界，root 为空
    if(!root) {
    
        return 
    }
     
    // 递归遍历左子树 
    postorder(root.left)  
    // 递归遍历右子树 
    postorder(root.right)
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
}