二叉树的先中后序遍历(递归+非递归 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);

output: 4 5 2 6 7 3 1


标签

Henry

大前端进阶中

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.