> For the complete documentation index, see [llms.txt](https://datastructure-1.gitbook.io/datastructure-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://datastructure-1.gitbook.io/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/05-binary-tree-basics.md). # 第 5 章：二叉树基础与遍历 [<- 第 4 章　字符串匹配（KMP）](/datastructure-docs/di-san-bu-fen-chuan/04-string-matching-kmp.md) | [课程目录](/datastructure-docs/readme.md) | [第 6 章　二叉搜索树 ->](/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/06-binary-search-tree.md) > 所属模块：第四部分：树与二叉树\ > 对应实现：binary\_tree.cpp ### 本章导航 * [5.1 从线性到分层：树结构的诞生与核心术语](#c05-5-1) * [5.2 二叉树的五大经典数学性质与严格证明](#c05-5-2) * [5.3 三大特殊二叉树形态辨析：满、完全、完美](#c05-5-3) * [5.4 二叉树的物理存储：链式 vs 数组索引映射](#c05-5-4) * [5.5 深度优先遍历（DFS）：前序、中序、后序的递归本质](#c05-5-5) * [5.6 非递归遍历的显式栈统一模板与工程实现](#c05-5-6) * [5.6.1 前序与中序的单栈迭代模板](#c05-5-6-1) * [5.6.2 后序遍历单栈迭代法（lastVisited 状态机）](#c05-5-6-2) * [5.7 广度优先遍历（BFS）：层序遍历与快照分层](#c05-5-7) * [5.8 经典问题：二叉树的唯一重构算法与反例分析](#c05-5-8) * [本章小结](#c05-summary) * [思考题与经典大厂面试题](#c05-exercises) *** ## 第 5 章　二叉树基础与遍历 > 难度：★★☆☆☆ | 代码：[binary\_tree.cpp](https://github.com/Huo0077/DataStructure/blob/main/binary_tree.cpp) **前置知识**：[第 2 章](/datastructure-docs/di-er-bu-fen-xian-xing-jie-gou/02-linear-list.md) 链表指针操作，[第 3 章](/datastructure-docs/di-er-bu-fen-xian-xing-jie-gou/03-stacks-and-queues.md) 栈（DFS）与队列（BFS）。 **学习目标**： 1. 建立层次化拓扑结构思维，准确掌握树与二叉树的标准术语； 2. 掌握二叉树五大数学性质的推导（重点：(n\_0 = n\_2 + 1) 的边数平衡法）； 3. 深刻理解递归遍历背后的系统调用栈行为； 4. 熟练手写前序、中序、后序的非递归（显式栈）与层序遍历代码； 5. 掌握通过遍历序列唯一重构二叉树的充要条件。 *** ### 5.1 从线性到分层：树结构的诞生与核心术语 线性表表达的是“一对一”的前驱后继关系；然而自然界与计算机系统中充斥着大量的“一对多”层次关系（如文件目录系统、DOM 树、组织架构、决策分类树）。**树（Tree）** 应运而生。 ``` A (根节点 Root) / │ \ B C D (分支节点) / \ \ E F G (叶节点 Leaf) ``` #### 核心术语定义： * **节点的度（Degree）**：节点拥有的子树个数（如 (A) 的度为 3，(B) 的度为 2，(E) 的度为 0）； * **树的度**：树中所有节点度的最大值（上图树的度为 3）； * **叶节点（Leaf）/ 终端节点**：度为 0 的节点； * **节点的层次（Level）**：根为第 1 层，其子为第 2 层，以此类推； * **节点的高度（Height）**：从该节点到最远叶子节点的最长路径边数（叶节点高度为 0）； * **节点的深度（Depth）**：从根节点到该节点的唯一路径边数（根节点深度为 0）； * **二叉树（Binary Tree）**：每个节点至多有两棵子树（度 (\le 2)），且子树有严格的**左右之分，次序不能颠倒**。 *** ### 5.2 二叉树的五大经典数学性质与严格证明 以下性质是二叉树理论的基石，也是算法分析与各类考试的必考考点： #### 性质 1：层节点数上界 **在二叉树的第 (i) 层上至多有 (2^{i-1}) 个节点（(i \ge 1)）。**\ *证明*：通过数学归纳法。第 1 层只有根节点（(2^0 = 1)）；设第 (i-1) 层最多有 (2^{i-2}) 个节点，因每个节点最多 2 个孩子，第 (i) 层最多有 (2 \times 2^{i-2} = 2^{i-1}) 个节点。 #### 性质 2：树总节点数上界 **深度为 (k) 的二叉树至多有 (2^k - 1) 个节点（(k \ge 1)）。**\ *证明*：利用等比数列求和：(\sum\_{i=1}^k 2^{i-1} = \frac{1 \cdot (1 - 2^k)}{1 - 2} = 2^k - 1)。 #### 性质 3：叶子节点与度为 2 节点的关系（核心定理） **对任何非空二叉树，若叶子节点数为 (n\_0)，度为 2 的节点数为 (n\_2)，则必有：(n\_0 = n\_2 + 1)。** ``` 【边数平衡证明法（双向数边）】 设二叉树总节点数为 n，度为 1 的节点数为 n1，总边数为 E。 1. 从下往上看: 除根节点外，每个节点上方均有一条入边连接其父节点: E = n - 1 = (n0 + n1 + n2) - 1 2. 从上往下看: 度为 2 的节点发出 2 条出边，度为 1 的发出 1 条，叶子发出 0 条: E = 2 * n2 + 1 * n1 + 0 * n0 = 2n2 + n1 3. 联立两式: (n0 + n1 + n2) - 1 = 2n2 + n1 两边消去 n1，移项得: n0 - 1 = n2 ===> n0 = n2 + 1 ■ (Q.E.D.) ``` #### 性质 4：完全二叉树的深度 **具有 (n) 个节点的完全二叉树的深度为 (\lfloor \log\_2 n \rfloor + 1)。** #### 性质 5：完全二叉树的数组下标父子关系（0-based） 对于从 0 开始连续编号的 (n) 个节点： * 若 (2i + 1 < n)，则节点 (i) 的左孩子为 (2i + 1)；否则无左孩子； * 若 (2i + 2 < n)，则节点 (i) 的右孩子为 (2i + 2)；否则无右孩子； * 若 (i > 0)，则节点 (i) 的双亲节点为 (\lfloor (i - 1) / 2 \rfloor)。 *** ### 5.3 三大特殊二叉树形态辨析：满、完全、完美 这三个概念在各大教材中极易混淆，其严格工业级界定如下： ``` 【满二叉树 (Full Binary Tree)】 【完全二叉树 (Complete)】 【完美二叉树 (Perfect)】 每个节点度为 0 或 2 (无单分支) 除最底层外全满，底层节点紧靠左 所有分支节点均有两子，叶子全同层 1 1 1 / \ / \ / \ 2 3 2 3 2 3 / \ / \ / / \ / \ 4 5 4 5 6 4 5 6 7 ``` *** ### 5.4 二叉树的物理存储：链式 vs 数组索引映射 #### 1. 链式二叉树（二叉链表） ```cpp struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; ``` 在通用场景下最为常用。若需要频繁寻找父节点，还可增加 `TreeNode* parent` 构成三叉链表。 #### 2. 顺序存储（数组连续映射） 仅在**完全二叉树**（如堆、优先队列、线段树）中推荐使用。若用于普通二叉树，必须在缺失节点处填充占位符，面对倾斜树时会造成毁灭性的内存浪费（如深度为 (k) 的右单斜树仅有 (k) 个节点，却需分配 (2^k - 1) 个空间！）。 *** ### 5.5 深度优先遍历（DFS）：前序、中序、后序的递归本质 三种 DFS 遍历在代码结构上**完全一致**，唯一的差别在于**处理（访问）根节点的时机**： ```cpp void traverse(TreeNode* root) { if (!root) return; // 1. 在此访问 root->val ===> 前序遍历 (Preorder: Root -> Left -> Right) traverse(root->left); // 2. 在此访问 root->val ===> 中序遍历 (Inorder: Left -> Root -> Right) traverse(root->right); // 3. 在此访问 root->val ===> 后序遍历 (Postorder: Left -> Right -> Root) } ``` ``` 4 / \ 2 6 / \ / \ 1 3 5 7 前序遍历 (NLR): 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7 (自顶向下，适合树的序列化与深拷贝) 中序遍历 (LNR): 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 (在 BST 中必然产生严格升序序列!) 后序遍历 (LRN): 1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4 (自底向上，适合由叶及根的计算与内存析构释放) ``` *** ### 5.6 非递归遍历的显式栈统一模板与工程实现 递归虽美，但当树高达到数万层时会引发操作系统栈溢出（Stack Overflow）。使用显式 `std::stack` 可将递归扁平化。 #### 5.6.1 前序与中序的单栈迭代模板 前序与中序有着极其优美的一体化模板——**“一路向左入栈，无路可走弹出转向右”**： ```cpp // 中序遍历的统一非递归实现 std::vector inorderTraversal(TreeNode* root) { std::vector res; std::stack st; TreeNode* curr = root; while (curr != nullptr || !st.empty()) { // 1. 一路向左深入，沿途节点全部压栈 while (curr != nullptr) { st.push(curr); curr = curr->left; } // 2. 走到最左端，弹出栈顶 curr = st.top(); st.pop(); res.push_back(curr->val); // 访问节点 (若为前序，则在第 1 步压栈前访问即可) // 3. 转向右子树 curr = curr->right; } return res; } ``` #### 5.6.2 后序遍历单栈迭代法（lastVisited 状态机） 后序遍历要求左、右子树都访问完毕后才能访问根节点。当从栈顶看到一个节点时，我们无法立即判断其右子树是否已经被访问过。\ **解决方案**：维护一个 `lastVisited` 指针，记录上一个被弹出的节点。若 `curr->right == nullptr || curr->right == lastVisited`，说明右子树已处理完毕，当前节点方可出栈！ ```cpp std::vector postorderTraversal(TreeNode* root) { std::vector res; std::stack st; TreeNode* curr = root; TreeNode* lastVisited = nullptr; while (curr != nullptr || !st.empty()) { while (curr != nullptr) { st.push(curr); curr = curr->left; } curr = st.top(); // 若右子树存在且尚未被访问过，则转向右子树 if (curr->right != nullptr && curr->right != lastVisited) { curr = curr->right; } else { // 右子树为空或已被访问过，安全访问当前节点并弹出 res.push_back(curr->val); lastVisited = curr; st.pop(); curr = nullptr; // 必须置空，防止下轮重新向左下压入 } } return res; } ``` *** ### 5.7 广度优先遍历（BFS）：层序遍历与快照分层 层序遍历借助队列实现逐层从左到右扫描。\ **“快照（Snapshot）分层技巧”**：在处理每一层前，先记录 `int levelSize = q.size()`，一次性处理恰好 `levelSize` 个节点，这样可以严格区分层与层的边界。 ```cpp std::vector> levelOrder(TreeNode* root) { std::vector> levels; if (!root) return levels; std::queue q; q.push(root); while (!q.empty()) { int levelSize = q.size(); // 核心：快照当前层节点数 std::vector currentLevel; for (int i = 0; i < levelSize; ++i) { TreeNode* node = q.front(); q.pop(); currentLevel.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } levels.push_back(currentLevel); } return levels; } ``` *** ### 5.8 经典问题：二叉树的唯一重构算法与反例分析 **定理**： 1. **前序 + 中序** $\implies$ **唯一确定** 一棵二叉树； 2. **后序 + 中序** $\implies$ **唯一确定** 一棵二叉树； 3. **前序 + 后序** $\implies$ **不能唯一确定** 二叉树！ #### 为什么前序+后序无法确定？ ``` 前序: [1, 2] 后序: [2, 1] 形态 A: 1 形态 B: 1 / \ 2 2 ``` 在前序中 1 在 2 前，后序中 2 在 1 前。由于缺少中序遍历作为左右子树的“分割边界”，我们无法判断节点 2 究竟是 1 的左孩子还是右孩子！ *** ### 本章小结 1. **二叉树的不变量**：(n\_0 = n\_2 + 1) 是二叉树最重要的拓扑特征定理，其证明深刻揭示了入度与出度的图论守恒。 2. **DFS 的时机决定语义**：前序重在“分发与自顶向下”，中序在 BST 中保证“单调升序”，后序重在“汇聚与自底向上释放”。 3. **显式栈与状态追踪**：非递归后序遍历引入 `lastVisited` 是用状态机管理回溯边界的经典实践。 4. **层序快照**：`levelSize = q.size()` 巧妙将连续流式的队列拆解为清晰的二维层次切片。 *** ### 思考题与经典大厂面试题 1. **Morris 遍历（神级算法）**：如何在 (O(n)) 时间复杂度、且仅占用 (O(1)) 辅助空间（不使用栈，不破坏树结构）的前提下完成二叉树的中序遍历？（提示：利用叶子节点的空闲右指针建立线索）。 2. **二叉树最近公共祖先（LCA）**：给定一棵二叉树和其中的两个节点 (p, q)，如何使用后序遍历自底向上在 (O(n)) 时间内找到它们的最近公共祖先？ 3. **完全二叉树的节点个数统计**：对于一棵完全二叉树，如何利用其高度特性，在 (O(\log^2 n)) 时间内（优于 (O(n)) 暴力遍历）求出总节点个数？