跳到主要内容

二叉树与遍历方式

树（Tree）是一种非线性的层次结构。在这一节中，我们将首先建立对树型结构的基本认知，并深入学习最常用的一种特化结构——**二叉树（Binary Tree）**及其遍历算法。

1. 树的核心名词概念​

在深入算法前，我们需要先统一树型结构中的专业术语：

       [ A ]          <-- 根节点 (Root) / 高度 = 2
      /     \
   [ B ]   [ C ]      <-- A 的子节点 (Children)，层级 = 1
   /   \
 [ D ] [ E ]          <-- 叶子节点 (Leaf)，层级 = 2 / 深度 = 2
  • 根节点 (Root)：树的顶端节点，一棵树只有一个根（如节点 A）。
  • 子节点 (Children) / 父节点 (Parent)：B 和 C 是 A 的子节点；A 是 B 和 C 的父节点。
  • 叶子节点 (Leaf)：没有子节点的终端节点（如 D、E、C）。
  • 节点的度 (Degree)：一个节点拥有的子树个数（如 B 的度为 2，C 的度为 0）。
  • 层级 (Level)：根节点为第 0 层（或第 1 层，不同教材定义不同，这里根暂定为第 0 层），其子节点为第 1 层，以此类推。
  • 高度 (Height) vs 深度 (Depth)：
    • 深度：从根节点到该节点的最长路径上的边数。
    • 高度：从该节点到叶子节点的最长路径上的边数。整棵树的高度即为根节点的高度。

2. 什么是二叉树？​

二叉树 (Binary Tree) 是一种特殊的树：每个节点最多只能有两个子节点，分别称为左子节点和右子节点。它的度最大为 2。

两种特殊的二叉树​

在实际应用和复杂度分析中，有两类特殊的二叉树形式非常关键：

1) 满二叉树 (Perfect Binary Tree)​

  • 定义：除叶子节点外，所有节点都有左、右两个子节点，且所有的叶子节点都在同一层（最底层）。

  • 特点：结构呈现完美的三角形。若根节点为第 0 层，高度为 h 的满二叉树的节点总数为 2^(h+1) - 1。

  • 图示：

              o
            /   \
           o     o
          / \   / \
         o   o o   o

2) 完全二叉树 (Complete Binary Tree)​

  • 定义：除最后一层外，其他各层的节点数都达到最大个数，且最后一层的所有节点都连续集中在最左侧。

  • 特点：若按从上至下、从左至右的顺序给节点编号，完全二叉树的节点编号与满二叉树完全一致，中间没有任何缺失。

  • 图示对照：

    正例（是完全二叉树）​
                1
              /   \
             2     3
            / \   /
           4   5 6

    解析：如果没有 5 就不算完全二叉树，因为不符合连续集中在最左侧的定义。

二叉树的经典 TypeScript 定义​

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

3. 二叉树的四种遍历方式​

遍历是指按照某种规则，不重复地访问二叉树中的所有节点。根据访问根节点 N、左子树 L、右子树 R 的顺序不同，深度优先遍历分为以下三种，另外还有一种广度优先的层序遍历。

我们以如下这棵二叉树为例说明遍历顺序：

      A
     / \
    B   C
   / \
  D   E

1) 前序遍历 (Pre-order Traversal)​

  • 顺序：根节点 -> 左子树 -> 右子树 (N -> L -> R)

  • 直观表现：先访问自己，再访问左侧子树，最后访问右侧子树。

  • 上述树的结果：A -> B -> D -> E -> C

  • 代码实现 (递归)：

    function preOrder(node: TreeNode | null) {
      if (node === null) return;
      console.log(node.val); // 访问根
      preOrder(node.left); // 递归左
      preOrder(node.right); // 递归右
    }

2) 中序遍历 (In-order Traversal)​

  • 顺序：左子树 -> 根节点 -> 右子树 (L -> N -> R)

  • 直观表现：先访问完左边，再访问自己，最后访问右边。

  • 上述树的结果：D -> B -> E -> A -> C

  • 代码实现 (递归)：

    function inOrder(node: TreeNode | null) {
      if (node === null) return;
      inOrder(node.left); // 递归左
      console.log(node.val); // 访问根
      inOrder(node.right); // 递归右
    }

    重要提示：在下一节我们将看到，中序遍历在二叉搜索树中扮演着极其重要的角色，它能按升序输出所有元素。

3) 后序遍历 (Post-order Traversal)​

  • 顺序：左子树 -> 右子树 -> 根节点 (L -> R -> N)

  • 直观表现：把左右子树都处理完了，最后才访问自己（常用于释放内存、销毁树等场景）。

  • 上述树的结果：D -> E -> B -> C -> A

  • 代码实现 (递归)：

    function postOrder(node: TreeNode | null) {
      if (node === null) return;
      postOrder(node.left); // 递归左
      postOrder(node.right); // 递归右
      console.log(node.val); // 访问根
    }

4) 层序遍历 (Level-order Traversal)​

  • 顺序：自上而下，自左向右逐层访问（广度优先搜索 BFS）。

  • 上述树的结果：A -> B -> C -> D -> E

  • 代码实现 (队列迭代)：

    function levelOrder(root: TreeNode | null): number[] {
      if (!root) return [];
      const result: number[] = [];
      const queue: TreeNode[] = [root]; // 使用队列

      while (queue.length > 0) {
        const node = queue.shift()!; // 出队
        result.push(node.val);
        if (node.left) queue.push(node.left); // 左子树入队
        if (node.right) queue.push(node.right); // 右子树入队
      }
      return result;
    }

掌握了二叉树的基本骨架和遍历方法后，我们就可以为二叉树添加排序规则，进化为具有查找性能的二叉搜索树。请点击下一页继续阅读！