二叉树的先中后序遍历（递归+非递归 JS 实现）

Code 代码

• 2020年7月19日

JavaScript 中没有树这种数据结构，但可以用 Object 和 Array 来构建树。二叉树是指，树中每个节点最多只能有两个子节点，分别为左节点、右节点，通常使用 Object 模拟二叉树。二叉树的先中后序遍历一般可以用递归来完成，也可以利用栈实现非递归的方式实现。

数据源：

const bt = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null
    },
    right: {
      val: 5,
      left: null,
      right: null
    }
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null
    },
    right: {
      val: 7,
      left: null,
      right: null
    }
  }
};

二叉树数据源

先序遍历

根-左-右：先访问根节点，再对根节点的左子树进行先序遍历，最后对根节点的右子树进行先序遍历

递归

const preorder = (root) => {
  if (!root) return;
  preorder(root.left);
  preorder(root.right);
};
preorder(bt);

非递归

const preorder = (root) => {
  if (!root) return;
  const stack = [root];
  while (stack.length) {
    const n = stack.pop();
    console.log(n.val);
    // 由于栈先进后出的特性，所有先 push right，再 push left
    if (n.right) stack.push(n.right);
    if (n.left) stack.push(n.left);
  }
};
preorder(bt);

output: 1 2 4 5 3 6 7

中序遍历

左-根-右：先对根节点的左子树进行中序遍历，再访问根节点，最后对根节点的右子树中序遍历

递归

const inorder = (root) => {
  if (!root) return;
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
};
inorder(bt);

非递归

const inorder = (root) => {
  if (!root) return;
  const stack = [];
  let p = root;
  while (stack.length || p) {
    // 类似于遍历链表，把当前根节点的所有左节点 push 到 stack 中
    while (p) {
      stack.push(p);
      p = p.left;
    }
    // 访问最底层的左节点
    const n = stack.pop();
    console.log(n.val);
    // 然后将指针指向当前根节点的右节点，以该右节点作为根节点继续下轮的遍历
    p = n.right;
  }
};
inorder(bt);

output: 4 2 5 1 6 3 7

后序遍历

左-右-根：先对根节点的左子树进行后序遍历，再对根节点的右子树进行后序遍历，最后访问根节点

递归

const postorder = (root) => {
  if (!root) return;
  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
};
postorder(bt);

非递归

// 先将后序遍历取反变为类似于先序遍历，即：左-右-根 => 根-右-左
// 再利用栈先进后出特性，把先序遍历的结果取反，遍历访问就是后序遍历的结果
const postorder = (root) => {
  if (!root) return;
  const outputStack = []; // 最终用来倒序输出的栈
  const stack = [root]; // 用来先序遍历的栈
  while (stack.length) {
    const n = stack.pop();
    // 将 n push 到 outputStack 中
    outputStack.push(n);
    // 因为和现需遍历不完全一样，先序遍历：根-左-右，此时为：根-右-左
    // 所以此时先 push left，再 push right
    if (n.left) stack.push(n.left);
    if (n.right) stack.push(n.right);
  }
  // 最终遍历 pop outputStack 的所有元素输出，即为后序遍历的结果
  while (outputStack.length) {
    const n = outputStack.pop();
    console.log(n.val);
  }
};
postorder(bt);