树

在数据结构的学习中，我们已经掌握了数组、链表、栈和队列等线性数据结构。这些结构中的元素按照线性顺序排列，每个元素（除首尾外）都有唯一的前驱和后继。然而，许多实际问题中的关系无法用简单的线性关系表示，需要更复杂的层次化结构。

树（Tree） 是一种重要的非线性数据结构，用于表示具有层次关系的数据集合。树结构在计算机科学中应用广泛，包括文件系统、数据库索引、表达式解析、决策树算法等领域。

树的定义与基本概念

形式化定义

设 $T = (V, E)$ 是一个有向图，其中 $V$ 是节点的有限集合，$E \subseteq V \times V$ 是边的集合。如果 $T$ 满足以下条件，则称 $T$ 为一棵树：

1. 连通性：对于任意两个节点 $u, v \in V$，存在从 $u$ 到 $v$ 的唯一路径。
2. 无环性：$T$ 中不存在回路。
3. 根节点存在性：存在唯一的节点 $r \in V$，使得对于所有 $$，存在从 到 的路径，且 的入度为 0。

在树 $T = (V, E)$ 中，如果存在边 $(u, v) \in E$，则称 $u$ 是 $v$ 的父节点（Parent），$v$ 是 的。节点 称为。

基本术语

对于树 $T = (V, E)$ 中的节点，我们定义以下术语：

• 根节点（Root）：入度为 0 的唯一节点，记为 $r$。
• 叶子节点（Leaf）：出度为 0 的节点集合，即 $L = \{v \in V : \text{deg}^+(v) = 0\}$。
• 内部节点（Internal Node）：非叶子节点的集合，即 $V\setminus L$。

路径与距离

路径（Path）：从节点 $u$ 到节点 $v$ 的路径是一个节点序列 $P = (v_0, v_1, \ldots, v_k)$，其中 ，，且对于 ，。路径的长度为 ，即路径上边的数量。

深度（Depth）：节点 $v$ 的深度 $\text{depth}(v)$ 定义为从根节点 $r$ 到 $v$ 的路径长度。根节点的深度为 0，即 $\text{depth}(r) = 0$。

高度（Height）：树 $T$ 的高度 $\text{height}(T)$ 定义为所有节点深度的最大值，即： $`\text{height}(T) = \max_{v \in V} \text{depth}(v)`$

子树（Subtree）：对于节点 $v \in V$，以 $v$ 为根的子树 $T_v = (V_v, E_v)$ 定义为： 包含 及其所有后代节点， 是 中连接 中节点的边的子集。

树的基本性质

定理 1：对于包含 $n$ 个节点的树 $T = (V, E)$，有 $|E| = |V| - 1$。

证明：使用数学归纳法。当 $n = 1$ 时，树只有一个根节点，边数为 0，结论成立。假设对于 $n = k$ 的树结论成立。对于 $n = k + 1$ 的树，移除一个叶子节点及其连接的边，得到 $k$ 个节点的树，根据归纳假设有 $k - 1$ 条边。因此原树有 条边，即 。

二叉树

定义

二叉树（Binary Tree）是一种特殊的树结构，其中每个节点最多有两个子节点，分别称为左子节点（Left Child）和右子节点（Right Child）。

形式化地，二叉树 $T = (V, E)$ 满足：对于任意节点 $v \in V$，其子节点数量 $|\text{children}(v)| \leq 2$，且子节点被明确标记为左子节点或右子节点。

二叉树的分类

完美二叉树（Perfect Binary Tree）

定义：高度为 $h$ 的完美二叉树满足以下条件：

1. 所有内部节点都有两个子节点。
2. 所有叶子节点都在第 $h$ 层。

性质：高度为 $h$ 的完美二叉树包含 $2^{h+1} - 1$ 个节点，其中第 $i$ 层（$0 \leq i \leq h$）有 $$ 个节点。

满二叉树（Full Binary Tree）

定义：满二叉树满足：对于任意节点 $v$，要么 $|\text{children}(v)| = 0$（叶子节点），要么 $|\text{children}(v)| = 2$（内部节点）。

性质：满二叉树不要求所有叶子节点在同一层，但要求所有非叶子节点都有两个子节点。

完全二叉树（Complete Binary Tree）

定义：高度为 $h$ 的完全二叉树满足：

1. 前 $h$ 层（层 0 到层 $h-1$）的所有节点都存在。
2. 第 $h$ 层的节点从左到右连续排列，不存在空缺。

性质：完全二叉树适合用数组表示。对于索引为 $i$（从 0 开始）的节点：

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

树的遍历

树的遍历（Tree Traversal）是指按照某种规则访问树中每个节点且仅访问一次的过程。根据访问顺序的不同，遍历算法可分为两大类：深度优先遍历（Depth-First Search, DFS）和广度优先遍历（Breadth-First Search, BFS）。

深度优先遍历（DFS）

深度优先遍历采用递归策略，优先访问深层节点。对于二叉树，根据根节点访问时机的不同，DFS 可分为三种标准遍历方式。

前序遍历（Pre-order Traversal）

定义：对于以节点 $v$ 为根的子树，前序遍历的访问顺序为：

1. 访问根节点 $v$
2. 递归遍历左子树
3. 递归遍历右子树

算法正确性：使用结构归纳法可证明前序遍历访问每个节点恰好一次。对于空树，算法正确。假设对于高度小于 $h$ 的树算法正确，对于高度为 $h$ 的树，根节点被访问一次，左右子树（高度小于 $h$）按归纳假设正确遍历，因此整个树被正确遍历。

应用场景：

• 树的序列化：前序遍历序列可用于重建树结构
• 表达式求值：前缀表达式（波兰表示法）对应表达式树的前序遍历
• 目录结构复制：需要先创建目录再复制子目录

中序遍历（In-order Traversal）

定义：对于以节点 $v$ 为根的子树，中序遍历的访问顺序为：

1. 递归遍历左子树
2. 访问根节点 $v$
3. 递归遍历右子树

重要性质：对于二叉搜索树（BST），中序遍历产生严格递增的有序序列。

应用场景：

• 二叉搜索树排序：中序遍历 BST 得到有序序列，时间复杂度 $O(n)$
• 表达式树：中序遍历对应中缀表达式，需考虑运算符优先级
• BST 性质验证：验证树是否为有效的二叉搜索树

后序遍历（Post-order Traversal）

定义：对于以节点 $v$ 为根的子树，后序遍历的访问顺序为：

1. 递归遍历左子树
2. 递归遍历右子树
3. 访问根节点 $v$

应用场景：

• 内存管理：删除树结构时必须采用后序遍历，确保子节点先于父节点释放
• 目录大小计算：需要先计算子目录大小再计算父目录
• 表达式求值：后缀表达式（逆波兰表示法）对应表达式树的后序遍历
• 树高计算：递归计算子树高度的标准方法

广度优先遍历（BFS）

广度优先遍历，也称为层序遍历（Level-order Traversal），按照树的层次逐层访问节点。

算法描述：

1. 初始化队列 $Q$，将根节点入队
2. 当 $Q$ 非空时：
   • 出队节点 $v$ 并访问
   • 将 $v$ 的所有子节点按顺序入队
3. 重复步骤 2 直到 $Q$ 为空

形式化描述：设 $Q$ 为队列，$\text{levelorder}(T)$ 的伪代码为：

|
Q.enqueue(root(T))
while not Q.empty():
    v = Q.dequeue()
    visit(v)
    for each child c of v:
        Q.enqueue(c)

复杂度分析

时间复杂度：对于包含 $n$ 个节点的树，所有遍历算法的时间复杂度均为 $O(n)$，因为每个节点被访问恰好一次。

空间复杂度分析：

深度优先遍历（递归实现）：

• 最坏情况：树退化为链状结构，递归深度为 $n$，空间复杂度 $O(n)$
• 最好情况：平衡二叉树，高度 $h = \lfloor \log_2 n \rfloor$，空间复杂度 $O(\log n)$

深度优先遍历（迭代实现）：

• 使用显式栈，空间复杂度与递归实现相同

广度优先遍历：

• 最坏情况：完美二叉树，最后一层包含 $\lceil n/2 \rceil$ 个节点，队列最大大小为 $O(n)$
• 最好情况：链状树，队列最大大小为 1，空间复杂度 $O(1)$
• 平均情况：对于随机树，空间复杂度 $O(n)$

定理 2：对于包含 $n$ 个节点的二叉树，层序遍历的空间复杂度为 $\Omega(n)$，时间复杂度为 $O(n)$。

证明：考虑完美二叉树，最后一层包含 $\lceil n/2 \rceil$ 个节点，这些节点会同时出现在队列中，因此空间复杂度下界为 $\Omega(n)$。每个节点入队和出队各一次，时间复杂度为 $O(n)$。$\square$

遍历可视化

遍历算法的实现

递归实现

递归实现简洁直观，直接反映遍历的数学定义。

|
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
 
using namespace std;
 
// 二叉树节点定义
template <typename T>
struct TreeNode {
    T data;
    TreeNode* left;
    TreeNode* right;
 
    TreeNode(T val) : data(val), 

迭代实现

迭代实现使用显式栈模拟递归调用，避免递归调用的函数调用开销。

|
// 前序遍历（迭代）
template <typename T>
void preorderIterative(TreeNode<T>* root, vector<T>& result) {
    if (root == nullptr) return;
    
    stack<TreeNode<T>*> stk;
    stk.push(root);

主函数示例

|
int main() {
    // 构建示例树：
    //        F
    //       / \
    //      B   G
    //     / \   \
    //    A   D   I
    //       / \ /
    //      C   E H
    
    TreeNode<string>* root = new TreeNode<string>("F");
    root->left = new TreeNode<string>("B");
    root->right =

小练习

4. 二叉树遍历序列推导练习

给定以下二叉树，请写出四种遍历方式的访问序列：

要求：分别写出前序遍历、中序遍历、后序遍历和层序遍历的序列。

|
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
using namespace std;
 
// 二叉树节点
struct TreeNode
{
    char val;
    TreeNode* left;
    TreeNode* right;
 
    TreeNode(char v) : val(v), left(nullptr), right(

5. 根据遍历序列重建树练习

已知某二叉树的遍历序列如下：

• 前序遍历：1, 2, 4, 5, 3, 6, 7
• 中序遍历：4, 2, 5, 1, 6, 3, 7

要求：

1. 根据前序和中序遍历序列重建二叉树
2. 推导后序遍历序列
3. 推导层序遍历序列

|
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <sstream>
using namespace std;
 
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
 
    TreeNode(int v) : val(v), left(nullptr), right

6. 二叉树遍历的复杂度分析练习

分析以下三种特殊形状的二叉树在不同遍历方式下的空间复杂度：

• 情况A：链状树（高度 n-1）
• 情况B：完全二叉树（高度 ⌊log₂n⌋）
• 情况C：满二叉树（高度 ⌊log₂n⌋）

要求：对于每种情况，分别分析DFS（递归实现）、DFS（迭代实现）和BFS的空间复杂度。

|
#include <iostream>
using namespace std;
 
int main()
{
    cout << "=== 二叉树遍历的空间复杂度分析 ===" << endl << endl;
 
    cout << "情况A：链状树（高度 n-1）" << endl;
    cout << "  - DFS（递归实现）: O(n)" << endl;
    cout << "    原因：递归调用栈的深度等于树的高度 n-1" << endl;
    cout << "  - DFS（迭代实现）: O(n)" << endl;

说明：

• 前序遍历（PreOrder）：F, B, A, D, C, E, G, I, H
  • 访问顺序：根 -> 左 -> 右
  • 先访问根节点F，然后遍历左子树，最后遍历右子树
• 中序遍历（InOrder）：A, B, C, D, E, F, I, G, H
  • 访问顺序：左 -> 根 -> 右
  • 先遍历左子树，然后访问根节点，最后遍历右子树
• 后序遍历（PostOrder）：A, C, E, D, B, I, H, G, F
  • 访问顺序：左 -> 右 -> 根
  • 先遍历左子树，然后遍历右子树，最后访问根节点
• 层序遍历（LevelOrder）：F, B, G, A, D, I, H, C, E
  • 访问顺序：按层从左到右
  • 使用队列实现，先访问根节点，然后逐层访问

说明：

• 重建过程：
  1. 前序遍历的第一个元素 1 是根节点
  2. 在中序遍历中找到 1 的位置，左边 [4, 2, 5] 是左子树，右边 [6, 3, 7] 是右子树
  3. 递归构建左子树和右子树
• 后序遍历序列：4, 5, 2, 6, 7, 3, 1
  • 左子树：4, 5, 2
  • 右子树：6, 7, 3
  • 根节点：1
• 层序遍历序列：1, 2, 3, 4, 5, 6, 7
  • 按层从左到右访问
• 唯一性：前序遍历和中序遍历序列可以唯一确定二叉树的结构
  • 前序遍历确定根节点
  • 中序遍历确定左右子树的范围

说明：

• 链状树（情况A）：
  • DFS（递归）：O(n)，递归调用栈深度为 n-1
  • DFS（迭代）：O(n)，显式栈需要存储所有节点
  • BFS：O(n)，队列需要存储所有节点
• 完全二叉树（情况B）：
  • DFS（递归）：O(log n)，递归调用栈深度为树的高度
  • DFS（迭代）：O(log n)，显式栈存储一条路径
  • BFS：O(n)，队列需要存储最后一层的所有节点
• 满二叉树（情况C）：
  • 与完全二叉树类似，空间复杂度相同
• 关键点：
  • DFS的空间复杂度主要取决于树的高度
  • BFS的空间复杂度主要取决于最宽层的节点数
  • 对于平衡树，DFS的空间复杂度更优（O(log n) vs O(n)）