二叉树

二叉树是指满足以下要求的树：

• 它可以没有根结点，作为一棵空树存在
• 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。如下图：

注意，二叉树不能被简单定义为每个结点的度都是2的树。普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定、不能交换的。对应到图上来看，也就意味着 B 和 C、D 和 E、F 和 G 是不能互换的。

二叉树的编码实现

在 JS 中，二叉树使用对象来定义。它的结构分为三块：

• 数据域
• 左侧子结点（左子树根结点）的引用
• 右侧子结点（右子树根结点）的引用

在定义二叉树构造函数时，我们需要把左侧子结点和右侧子结点都预置为空：

function TreeNode(val){
    this.val = val;
    this.left = this.right = null;
}
const node  = new TreeNode(1)

二叉树的遍历

以一定的顺序规则，逐个访问二叉树的所有结点，这个过程就是二叉树的遍历。按照顺序规则的不同，遍历方式有以下四种：

• 先序遍历
• 中序遍历
• 后序遍历
• 层次遍历

按照实现方式的不同，遍历方式又可以分为以下两种：

• 递归遍历（先、中、后序遍历）
• 迭代遍历（层次遍历）

  递归遍历初相见

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。

简单来说，当我们看到一个函数反复调用它自己的时候，递归就发生了。“递归”就意味着“反复”，像咱们之前对二叉树的定义，就可以理解为是一个递归式的定义：

• 它可以没有根结点，作为一棵空树存在
• 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。

这个定义有着这样的内涵：如果我们想要创建一个二叉树结点作为根结点，那么它左侧的子结点和右侧的子结点也都必须符合二叉树结点的定义，这意味着我们要反复地执行“创建一个由数据域、左右子树组成的结点”这个动作，直到数据被分配完为止。

结合这个定义来看，每一棵二叉树都应该由这三部分组成：

对树的遍历，就可以看做是对这三个部分的遍历。这里就引出一个问题：三个部分中，到底先遍历哪个、后遍历哪个呢？我们此处其实可以穷举一下，假如在保证“左子树一定先于右子树遍历”这个前提，那么遍历的可能顺序也不过三种：

• 根结点 -> 左子树 -> 右子树
• 左子树 -> 根结点 -> 右子树
• 左子树 -> 右子树 -> 根结点

上述三个遍历顺序，就分别对应了二叉树的先序遍历、中序遍历和后序遍历规则。
在这三种顺序中，根结点的遍历分别被安排在了首要位置、中间位置和最后位置。
所谓的“先序”、“中序”和“后序”，“先”、“中”、“后”其实就是指根结点的遍历时机。

上述树的结构

const root = {
    val: "A",
  left:{
      val: "B",
    left: {
        val: "D"
    }
    right: {
          val: "E"
      }
  },
  right: {
      val: "C",
    right: {
      val: "F"
    }
  }
}

递归函数的编写要点

• 递归式
• 递归边界

递归式，它指的是你每一次重复的内容是什么。在这里，我们要做先序遍历，那么每一次重复的其实就是 根结点 -> 左子树 -> 右子树 这个旅行路线。
递归边界，它指的是你什么时候停下来。
在遍历的场景下，当我们发现遍历的目标树为空的时候，就意味着旅途已达终点、需要画上句号了。这个“画句号”的方式，在编码实现里对应着一个 return 语句——这就是二叉树遍历的递归边界。

先序遍历

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

图解先序遍历的完整过程

我们直接把它套进 preorder 函数里，一步一步来认清楚先序遍历的每一步做了什么：

1. 调用 preorder(root)，这里 root 就是 A，它非空，所以进入递归式，输出 A 值。接着优先遍历左子树，preorder(root.left) 此时为 preorder(B) ：

2. 进入 preorder(B) 的逻辑： 入参为结点 B，非空，进入递归式，输出 B 值。接着优先遍历 B 的左子树，preorder(root.left) 此时为 preorder(D) ：

1. 进入 preorder(D) 的逻辑： 入参为结点 D，非空，进入递归式，输出 D 值。接着优先遍历 D 的左子树，preorder(root.left) 此时为 preorder(null)：
   
   5. 再次进入preorder(null) ，发现抵达了递归边界，直接 return 掉，回到preorder(D) 里。接着 preorder(D) 的逻辑往下走，发现 preorder(D) 已经执行完了。于是返回，回到preorder(B) 里，接着preorder(B) 往下走，进入 preorder(root.right) ，也就是 preorder(E) ：

E 不为空，进入递归式，输出 E 值。接着优先遍历 E 的左子树，preorder(root.left) 此时为 preorder(null)，触碰递归边界，直接返回 preorder(E)；继续preorder(E)执行下去，是preorder(root.right) ，这里 E 的 right 同样是 null，故直接返回。如此一来，preorder(E)就执行完了，回到preorder(B)里去；发现preorder(B)也执行完了，于是回到preorder(A)里去，执行preorder(A)中的 preorder(root.right)。

1. root 是A，root.right 就是 C 了，进入preorder(C)的逻辑：
   

C 不为空，进入递归式，输出 C 值。接着优先遍历 C 的左子树，preorder(root.left) 此时为 preorder(null)，触碰递归边界，直接返回。继续preorder(C)执行下去，是preorder(root.right) ，这里 C 的 right 是 F：

1. 进入preorder(F)的逻辑，F 不为空，进入递归式，输出 F 值。接着优先遍历 F 的左子树，preorder(root.left) 此时为 preorder(null)，触碰递归边界，直接返回 preorder(F)；继续preorder(F)执行下去，是preorder(root.right) ，这里 F 的 right 同样是 null，故直接返回preorder(F)。此时preorder(F)已经执行完了，返回preorder(C)；发现preorder(C)也执行完了，就回到 preorder(A)；发现preorder(A)作为递归入口，它的逻辑也已经执行完了，于是我们的递归活动就正式画上了句号。到此为止，6个结点也已全部按照先序遍历顺序输出：

当前遍历的结点值是： A
当前遍历的结点值是： B
当前遍历的结点值是： D
当前遍历的结点值是： E
当前遍历的结点值是： C
当前遍历的结点值是： F

中序遍历

function inorder(root) {
    if(root) {
      return
  }
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
}

后序遍历

function postorder(root) {
    // 递归边界，root 为空
    if(!root) {
        return 
    }

    // 递归遍历左子树 
    postorder(root.left)  
    // 递归遍历右子树  
    postorder(root.right)
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
}