Chapter 5: 树

树(Tree)数据结构是我们继续学习进阶数据结构的基石。

树

首先我们先介绍通用树 (General Trees)，这种树的每个节点可以拥有任意数量的子节点。这种结构常见于文件系统。

那么树这样的数据结构有什么要求吗？

一个树里面包含这些内容和结构：

根 (Root): 也叫树的根节点。这个是树的顶端，在它之上没有父节点。
叶子 (Leaf)：也叫外部节点(External Node)。这些节点没有子节点。
内节点 (Internal Node)：包含至少一个子节点的节点。
节点深度 (Depth of Node)：也叫做层数。如果"Depth of Node x"的意思是从根节点往下数距离为x的层。
树高度 (Height of Tree)：等于树里面任意节点的最大深度。例如一个只包含一个根节点的树高度为0，一个空树 (Null tree)的深度为-1。

实现一个树结构

那么我们如何在计算机中实现一个树？对于通用树来讲，一个节点可以有任意子节点。那么问题在于，我们如何在不知道一个节点有多少子节点的情况下，定义一个struct node？

首先我们尝试为node做出这样的结构定义：node *child[100]。这种方案显然不可取，因为这样太浪费空间了，你永远不知道你的树中的每个节点平均有多少子节点（一般来讲也不会有很多子节点），所以在大多数情况下会造成存储空间的浪费。

另一种方式是使用左子节点，右兄弟节点表示法 (Left-Child, Right-Sibling Representation)

简单来讲，每一个节点包含两个指针：

FirstChild指针指向该节点的第一个子节点
NextSibling指针指向该节点附近的一个兄弟节点

使用这样的一个结构，我们就可以来表示任意通用树了！

遍历通用树

表示出来之后还不够，我们需要知道该如何遍历这棵树。我们可以采取三个方式：

前序遍历 (Pre-Order, Root-Left-Right)：先访问当前节点，然后再访问我的子节点。这种情况比较适用于复制目录结构。
后序遍历 (Post-Order, Left-Right-Root)：先遍历子节点，然后再遍历父节点。例如计算文件夹大小，你需要先去获取子节点大小。
中序遍历 (In-Order, Left-Root-Right)：这种遍历方式一般用于二叉树。如果在二叉树中使用这样的遍历方式可以直接生成排序输出。

一会我们会展开来讲。

二叉树

二叉树 (Binary Tree) 是一种特殊的树结构，每个节点最多只能有两个子节点，分别称为左子节点和右子节点。并且二叉树的每个节点只能有0个或者两个节点。

二叉树的节点定义非常简洁：

struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

二叉树的性质

二叉树有一些非常重要的数学性质，考试经常会考到：

📐重要公式

第 $i$ 层的最大节点数：$2^i$（根节点在第 0 层）
高度为 $h$ 的二叉树最多有：$2^{h+1} - 1$ 个节点
具有 $n$ 个节点的完全二叉树高度：$h = \lfloor \log_2 n \rfloor$
叶子节点数与子节点数量为2的节点数关系：$n_0 = n_2 + 1$（其中 $n_0$ 是叶子数，$n_2$ 是有两个子节点的节点数）

特殊的二叉树

满二叉树 (Full Binary Tree)：每个节点要么是叶子节点，要么恰好有两个子节点。不存在只有一个子节点的节点。
完全二叉树 (Complete Binary Tree)：除了最后一层外，其他层都是满的，且最后一层的节点都靠左排列。
完美二叉树 (Perfect Binary Tree)：所有内部节点都有两个子节点，且所有叶子节点都在同一层。

例Cpt5.1

一棵完美二叉树有 31 个节点，请问它的高度是多少？有多少个叶子节点？

根据完美二叉树的性质：

节点总数 $n = 2^{h+1} - 1 = 31$
解得 $2^{h+1} = 32 = 2^5$，因此 $h = 4$

叶子节点数：

完美二叉树的叶子节点都在最后一层，数量为 $2^h = 2^4 = 16$

二叉树的遍历

二叉树有四种主要的遍历方式，理解它们对于解题至关重要。遍历的本质是将树这种非线性结构转化为线性序列。

深度优先遍历 vs 广度优先遍历

在学习具体的遍历方式之前，我们先理解两大类遍历策略：

深度优先遍历 (DFS)：沿着一条路径走到底，再回溯。前序、中序、后序都属于这一类，通常用递归或栈实现。
广度优先遍历 (BFS)：逐层访问节点。层序遍历属于这一类，通常用队列实现。

这些内容在之前的章节提到过了。忘了的话可以去看一看。

前序遍历 (Pre-Order)

访问顺序：根 → 左子树 → 右子树

"前序"的意思是根节点在最前面被访问。

void preOrder(TreeNode *node) {
    if (node == NULL) return;
    visit(node);           // 先访问根
    preOrder(node->left);  // 再遍历左子树
    preOrder(node->right); // 最后遍历右子树
}

应用场景：

复制一棵树（先创建根，再创建子树）
序列化树结构
表达式树的前缀表示（波兰表示法）

中序遍历 (In-Order)

访问顺序：左子树 → 根 → 右子树

"中序"的意思是根节点在中间被访问。

void inOrder(TreeNode *node) {
    if (node == NULL) return;
    inOrder(node->left);   // 先遍历左子树
    visit(node);           // 再访问根
    inOrder(node->right);  // 最后遍历右子树
}

⚠注意

对于二叉搜索树，中序遍历会按照升序输出所有节点值！这是一个非常重要的性质，常用于验证一棵树是否是 BST。

应用场景：

二叉搜索树的有序输出
表达式树的中缀表示（需要加括号）

我们在本章不会讲到二叉搜索树。与二叉搜索树相关的内容我们放到第七章去讲。

后序遍历 (Post-Order)

访问顺序：左子树 → 右子树 → 根

"后序"的意思是根节点在最后被访问。

void postOrder(TreeNode *node) {
    if (node == NULL) return;
    postOrder(node->left);  // 先遍历左子树
    postOrder(node->right); // 再遍历右子树
    visit(node);            // 最后访问根
}

应用场景：

删除一棵树（先删除子树，最后删除根）
计算目录大小（先计算子目录，再汇总）
表达式树的后缀表示（逆波兰表示法）
计算树的高度

层序遍历 (Level-Order)

使用队列实现，按层从上到下、从左到右访问节点。

如果你将BFS的算法应用到树上，那么你就得到了层序遍历：

void levelOrder(TreeNode *root) {
    Queue q;
    enqueue(q, root);
    while (!isEmpty(q)) {
        TreeNode *node = dequeue(q);
        visit(node);
        if (node->left) enqueue(q, node->left);
        if (node->right) enqueue(q, node->right);
    }
}

应用场景：

逐层打印树
寻找最短路径（在树中等价于求深度）
判断完全二叉树

非递归实现遍历

递归本质上是利用系统调用栈，我们也可以用显式的栈来实现非递归遍历：

前序遍历（非递归）：

void preOrderIterative(TreeNode *root) {
    Stack s;
    push(s, root);
    while (!isEmpty(s)) {
        TreeNode *node = pop(s);
        visit(node);
        // 注意：先压右子节点，再压左子节点（栈是LIFO）
        if (node->right) push(s, node->right);
        if (node->left) push(s, node->left);
    }
}

中序遍历（非递归）：

void inOrderIterative(TreeNode *root) {
    Stack s;
    TreeNode *curr = root;
    while (curr != NULL || !isEmpty(s)) {
        // 一直往左走到底
        while (curr != NULL) {
            push(s, curr);
            curr = curr->left;
        }
        // 访问节点，然后转向右子树
        curr = pop(s);
        visit(curr);
        curr = curr->right;
    }
}

遍历序列的性质

📐遍历序列的重要性质

前序 + 中序 可以唯一确定一棵二叉树
后序 + 中序 可以唯一确定一棵二叉树
前序 + 后序 不能唯一确定一棵二叉树（除非是满二叉树）
层序 + 中序 可以唯一确定一棵二叉树

原因：中序遍历能够区分左右子树，而前序/后序/层序能够确定根节点。

二叉树遍历可视化

如果对于上述过程还不是很清晰，那么可以来这里看看小动画：

选择遍历方式，点击「下一步」开始演示

📚 栈/队列状态

空

📝 遍历序列

尚未开始

例Cpt5.2

给定一棵二叉树的前序遍历为 ABDECFG，中序遍历为 DBEAFCG，请还原这棵树并写出后序遍历。

解题思路：

前序遍历的第一个元素一定是根节点 → 根是 A
在中序遍历中找到 A，它左边的 DBE 是左子树，右边的 FCG 是右子树
递归处理左子树：前序 BDE，中序 DBE → 根是 B，左子树 D，右子树 E
递归处理右子树：前序 CFG，中序 FCG → 根是 C，左子树 F，右子树 G

后序遍历：DEBFGCA

堆与优先队列

拓展阅读提醒

堆不在COMP2119的大纲范围内！本内容仅供拓展阅读。

堆 (Heap) 是一种特殊的完全二叉树，它满足堆性质：

最大堆 (Max-Heap)：每个节点的值 ≥ 其子节点的值。根节点是最大值。
最小堆 (Min-Heap)：每个节点的值 ≤ 其子节点的值。根节点是最小值。

数组实现堆

由于堆是完全二叉树，我们可以用数组高效地存储它（不需要指针！）：

📐堆的数组索引公式

假设数组索引从 0 开始：

节点 $i$ 的父节点索引：$\lfloor (i-1)/2 \rfloor$
节点 $i$ 的左子节点索引：$2i + 1$
节点 $i$ 的右子节点索引：$2i + 2$

假设数组索引从 1 开始：

节点 $i$ 的父节点索引：$\lfloor i/2 \rfloor$
节点 $i$ 的左子节点索引：$2i$
节点 $i$ 的右子节点索引：$2i + 1$

堆的核心操作

上浮 (Bubble Up / Percolate Up)
当插入新元素时，将其放在数组末尾，然后与父节点比较，如果违反堆性质就交换，重复直到满足堆性质。

下沉 (Bubble Down / Percolate Down)
当删除根节点时，将最后一个元素移到根位置，然后与子节点比较，与较大（最大堆）或较小（最小堆）的子节点交换，重复直到满足堆性质。

堆操作的时间复杂度

操作	时间复杂度
插入	$O(\log n)$
删除最大/最小值	$O(\log n)$
获取最大/最小值	$O(1)$
建堆（从数组）	$O(n)$

⚠注意

建堆的时间复杂度是 $O(n)$，而不是 $O(n \log n)$！这是因为大部分节点都在树的底部，它们下沉的距离很短。这是一个常见的考点。

优先队列

优先队列 (Priority Queue) 是一种抽象数据类型，支持：

插入元素
删除并返回优先级最高（或最低）的元素

堆是实现优先队列最常用的数据结构。最大堆实现的优先队列总是返回最大元素，最小堆则返回最小元素。

例Cpt5.4

将数组 [4, 10, 3, 5, 1] 构建成最大堆。

初始数组视为完全二叉树：

从最后一个非叶子节点开始（索引 1，值为 10），向前遍历执行下沉操作：

索引 1（值 10）：子节点是 5 和 1，10 > 5 > 1，无需调整
索引 0（值 4）：子节点是 10 和 3，10 > 4，交换 4 和 10

继续下沉 4：子节点是 5 和 1，5 > 4，交换：

最终最大堆数组：[10, 5, 3, 4, 1]

树结构的对比总结

数据结构	查找	插入	删除	特点
普通二叉树	$O(n)$	$O(n)$	$O(n)$	无特殊性质
BST（平均）	$O(\log n)$	$O(\log n)$	$O(\log n)$	可能退化
BST（最坏）	$O(n)$	$O(n)$	$O(n)$	退化为链表
AVL 树	$O(\log n)$	$O(\log n)$	$O(\log n)$	自平衡，严格平衡
堆	$O(n)$	$O(\log n)$	$O(\log n)$	只关心最值