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

Code 代码
7月 19, 2020 ~

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);

output: 4 5 2 6 7 3 1


标签

Henry

大前端进阶中