二叉树遍历

二叉树存储

实际开发中，一般会使用数组来存储树结构，通过数组，我们可以非常方便的找到一个节点的所有亲属。

• 寻找父节点：Math.floor((当前节点的下标 - 1) / 2)，例如：

  子节点	父节点
  1	0
  2	0
  3	1
  4	1

• 寻找左分支节点：当前节点下标 * 2 + 1，例如：

  父节点	左分支节点
  0	1
  1	3
  2	5

• 寻找右分支节点：当前节点下标 * 2 + 2，例如：

  父节点	左分支节点
  0	2
  1	4
  2	6

完全二叉树遍历

class TreeNode {
  constructor(value) {
    this.value = value // 节点的值
    this.left = null // 左子树
    this.right = null // 右子树
  }
}

// 构建上面的完全二叉树
const root = new TreeNode('A')
root.left = new TreeNode('B')
root.right = new TreeNode('C')
root.left.left = new TreeNode('D')
root.left.right = new TreeNode('E')
root.left.left.left = new TreeNode('H')
root.left.left.right = new TreeNode('I')
root.left.right.left = new TreeNode('J')
root.left.right.right = new TreeNode('K')
root.right.left = new TreeNode('F')
root.right.right = new TreeNode('G')
root.right.left.left = new TreeNode('L')
root.right.left.right = new TreeNode('M')
root.right.right.left = new TreeNode('N')
root.right.right.right = new TreeNode('O')

1. 前序遍历

   根节点 --> 左子树 --> 右子树

   遍历出来的顺序如下：

   A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> L -> M -> G -> N -> O

   function preOrder(root) {
     if (root === null) return
   
     // 访问根节点
     console.log(root.value)
   
     // 遍历左子树
     preOrder(root.left)
   
     // 遍历右子树
     preOrder(root.right)
   }

2. 中序遍历

   左子树 --> 根节点 --> 右子树

   中序遍历的具体顺序可以看节点投影，投影出来的线性顺序就是遍历出来的顺序

   

   H -> D -> I -> B -> J -> E -> K -> A -> L -> F -> M -> C -> N -> G -> O

   function inOrder(root) {
     if (root === null) return
   
     // 遍历左子树
     inOrder(root.left)
   
     // 访问根节点
     console.log(root.value)
   
     // 遍历右子树
     inOrder(root.right)
   }

3. 后序遍历

   左子树 --> 右子树 --> 根节点

   H -> I -> D -> J -> K -> E -> B -> L -> M -> F -> N -> O -> G -> C -> A

   function postOrder(root) {
     if (root === null) return
   
     // 遍历左子树
     postOrder(root.left)
   
     // 遍历右子树
     postOrder(root.right)
   
     // 访问根节点
     console.log(root.value)
   }

-EOF-