请用 JavaScript 实现一个二叉树的遍历 (前序、中序、后序) 或广度优先/深度优先遍历。 - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

各位观众老爷们，大家好！今天咱们来聊聊二叉树的那些事儿。别看这玩意儿长得像个倒过来的树杈子，实际上在计算机世界里可是个大明星。无论是数据库的索引，还是编译器的语法分析，都少不了它的身影。今天我就来给大家好好扒一扒，用JavaScript怎么玩转这颗“树杈子”。

二叉树是个啥？

简单来说，二叉树就是每个节点最多有两个孩子（左孩子和右孩子）的树。就像你家里的族谱，每个人最多有两个孩子（当然，超生游击队的情况咱们这里不考虑）。

代码表示

先用JavaScript把二叉树的节点定义出来：

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

这里 val 是节点的值，left 指向左孩子，right 指向右孩子。

遍历大法好！

二叉树遍历，顾名思义，就是把二叉树的所有节点都访问一遍。就像你过年回家，挨个给亲戚拜年一样。遍历的顺序不同，拜年的顺序也就不同，效果嘛，自然也不同。

二叉树遍历主要分为两大类：

深度优先遍历 (DFS)：一条路走到黑，不撞南墙不回头。
广度优先遍历 (BFS)：像水波一样，一层一层地扩散。

深度优先遍历 (DFS)

深度优先遍历又分为三种：

前序遍历 (Preorder Traversal)：先拜访自己，再拜访左边，最后拜访右边 (根 -> 左 -> 右)。
中序遍历 (Inorder Traversal)：先拜访左边，再拜访自己，最后拜访右边 (左 -> 根 -> 右)。
后序遍历 (Postorder Traversal)：先拜访左边，再拜访右边，最后拜访自己 (左 -> 右 -> 根)。

咱们用递归的方式来实现这三种遍历：

// 前序遍历
function preorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) {
      return;
    }
    result.push(node.val); // 先访问根节点
    traverse(node.left);    // 再访问左子树
    traverse(node.right);   // 最后访问右子树
  }

  traverse(root);
  return result;
}

// 中序遍历
function inorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) {
      return;
    }
    traverse(node.left);    // 先访问左子树
    result.push(node.val); // 再访问根节点
    traverse(node.right);   // 最后访问右子树
  }

  traverse(root);
  return result;
}

// 后序遍历
function postorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) {
      return;
    }
    traverse(node.left);    // 先访问左子树
    traverse(node.right);   // 再访问右子树
    result.push(node.val); // 最后访问根节点
  }

  traverse(root);
  return result;
}

举个栗子

假设我们有这样一棵二叉树：

那么：

前序遍历的结果是：[1, 2, 4, 5, 3]
中序遍历的结果是：[4, 2, 5, 1, 3]
后序遍历的结果是：[4, 5, 2, 3, 1]

非递归实现深度优先遍历

递归虽然简单易懂，但是当树的深度很深的时候，容易导致栈溢出。所以，咱们还得掌握非递归的实现方式。这时候，栈 (Stack) 就派上用场了。

前序遍历 (非递归)

function preorderTraversalIterative(root) {
  const result = [];
  const stack = [];

  if (root) {
    stack.push(root);
  }

  while (stack.length > 0) {
    const node = stack.pop(); // 弹出栈顶元素
    result.push(node.val);      // 访问根节点

    // 先将右子节点入栈，再将左子节点入栈
    // 因为栈是后进先出，所以左子节点会先被访问到
    if (node.right) {
      stack.push(node.right);
    }
    if (node.left) {
      stack.push(node.left);
    }
  }

  return result;
}

中序遍历 (非递归)

中序遍历的非递归实现稍微复杂一些。因为我们需要先找到最左边的节点，才能开始访问。

function inorderTraversalIterative(root) {
  const result = [];
  const stack = [];
  let current = root;

  while (current || stack.length > 0) {
    // 找到最左边的节点
    while (current) {
      stack.push(current);
      current = current.left;
    }

    // 弹出栈顶元素，访问根节点
    current = stack.pop();
    result.push(current.val);

    // 访问右子树
    current = current.right;
  }

  return result;
}

后序遍历 (非递归)

后序遍历的非递归实现是最复杂的。因为我们需要保证在访问根节点之前，已经访问了左子树和右子树。一个常用的技巧是使用一个 prev 变量来记录上一次访问的节点。

function postorderTraversalIterative(root) {
    const result = [];
    const stack = [];
    let prev = null; // 记录上一次访问的节点
    let curr = root;

    if (!root) return result;

    stack.push(root);

    while (stack.length > 0) {
        curr = stack[stack.length - 1]; // 查看栈顶元素

        // 从上往下走，判断左右节点是否为空
        if (!prev || prev.left === curr || prev.right === curr) {
            if (curr.left) {
                stack.push(curr.left);
            } else if (curr.right) {
                stack.push(curr.right);
            } else {
                // 叶子节点直接访问
                result.push(curr.val);
                stack.pop();
            }
        } else if (curr.left === prev) {
            // 从左往上走
            if (curr.right) {
                stack.push(curr.right);
            } else {
                result.push(curr.val);
                stack.pop();
            }
        } else if (curr.right === prev) {
            // 从右往上走
            result.push(curr.val);
            stack.pop();
        }

        prev = curr; // 更新上一次访问的节点
    }

    return result;
}

广度优先遍历 (BFS)

广度优先遍历，也叫层序遍历。就像水波一样，一层一层地扩散。这时候，队列 (Queue) 就派上用场了。

function levelOrderTraversal(root) {
  const result = [];
  const queue = [];

  if (root) {
    queue.push(root);
  }

  while (queue.length > 0) {
    const levelSize = queue.length; // 当前层的节点个数
    const currentLevel = [];      // 当前层的结果

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();   // 弹出队首元素
      currentLevel.push(node.val); // 访问节点

      // 将左右孩子入队
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
    }
    result.push(currentLevel); // 将当前层的结果添加到总结果中
  }

  return result;
}

对于上面的例子，广度优先遍历的结果是：[[1], [2, 3], [4, 5]]

各种遍历方法的对比

为了方便大家理解，我把各种遍历方法的特点总结成一个表格：

遍历方法	访问顺序	实现方式	适用场景
前序遍历	根 -> 左 -> 右	递归/栈	复制树，创建表达式树
中序遍历	左 -> 根 -> 右	递归/栈	二叉搜索树的有序输出
后序遍历	左 -> 右 -> 根	递归/栈	删除树，计算目录大小
广度优先遍历	从上到下，从左到右	队列	查找最短路径，社交网络关系查找
深度优先遍历	一条路走到黑	递归/栈	适用于解决需要遍历所有可能路径的问题，比如迷宫问题，或者找到所有可能的解
广度优先遍历	一层一层扩散	队列	适用于解决需要找到最短路径或者最快到达目标的问题，比如网络爬虫，社交关系查找

总结

二叉树的遍历是二叉树操作的基础。掌握了这些遍历方法，你就可以轻松地对二叉树进行各种操作，比如查找节点、插入节点、删除节点等等。希望今天的讲解能够帮助大家更好地理解和应用二叉树。

一些小技巧

递归 vs. 迭代：递归代码简洁易懂，但是容易导致栈溢出；迭代代码稍微复杂一些，但是效率更高，更不容易出错。
栈 vs. 队列：栈是后进先出，队列是先进先出。根据不同的遍历需求，选择合适的数据结构。
多练习：熟能生巧，多练习一些二叉树相关的题目，才能真正掌握这些技巧。

好了，今天的分享就到这里。感谢大家的观看！如果大家有什么问题，欢迎在评论区留言。下次有机会再和大家聊聊二叉树的其他高级应用。比如平衡二叉树、红黑树等等。咱们下期再见！

发表回复 取消回复

发表回复取消回复