C++进阶(03)：二叉树

💬 ：如果你在阅读过程中有任何疑问或想要进一步探讨的内容，欢迎在评论区畅所欲言！我们一起学习、共同成长~！

👍 ：如果你觉得这篇文章还不错，不妨顺手点个赞、加入收藏，并分享给更多的朋友噢~！

1. 树

1.1 树的定义

树是由n(n≥0)个节点组成的非线性层次结构，根节点无前驱，其余节点分属互不相交的子树。因此，树是递归定义的。

核心特征：子树不相交（如图，B与C或F与G间均不能相连），除根外每个节点仅有一个父节点，n个节点有n-1条边。

1.2 核心术语

• 度：一个节点含有的子树个数称为该节点的度（上图A的度为2）

• 叶节点：度为 0 的节点/终端节点（如上图的H、I）

• 非叶子节点：度不为 0 的节点

• 层次：根为第 1 层，根的子节点为第2层，以此类推

• 高度/深度= 层数（上图高度=4）

• 森林：m(m>0)棵不相交树的集合

1.3 树的表示

主要了解孩子兄弟表示法

template<class T> struct TreeNode { T _data; // 节点存储的数据 TreeNode<T>* _firstChild; // 指向当前节点的第一个直接子节点 TreeNode<T>* _nextBrother; // 指向与当前节点拥有同一个父节点的下一个节点 };

以上图的节点B为例：

• _data：'B'
• _firstChild：指向D
• _nextBrother：指向C

孩子兄弟表示法的本质：通过_firstChild（纵向连接子树）和_nextBrother（横向连接兄弟），将多叉树转化为二叉树结构：

• 纵向：访问子树时，遍历_firstChild链（如B → D，D → 无；B → E，E → H）。
• 横向：访问兄弟时，遍历_nextBrother链（如B → C，D → E，E → F，H → I）。

2. 二叉树基础

2.1 二叉树的定义

二叉树是节点的有限集合，要么为空，要么由“根节点+左子树+右子树”组成（左、右子树均为二叉树）。

特性：节点度<=2；子树有左右次序（因此二叉树是有序树）。

2.2 特殊二叉树（高频考点）

2.2.1 满二叉树

一棵二叉树每一层的节点都达最大值，即一棵二叉树第k层的节点总数为，那么它就是满二叉树。

2.2.2 完全二叉树

除了最后一层外其他层全满；最后一层节点从左到右连续排列，可缺右部节点。满二叉树是一种特殊的完全二叉树。

根节点索引为 0 时，节点 i 的：

• 父节点索引：(i - 1) / 2（整数除法）
• 左子节点索引：2 * i + 1
• 右子节点索引：2 * i + 2

2.3 二叉树的性质

1. 第k层最多个节点（排满）；
   
2. 深度h的二叉树最多个节点；
   
3. 核心公式（计算题高频）：
   （1）对任意非空二叉树，若
   =度为0的叶节点数，
   =度为1的节点数，
   =度为2的节点数，
   0 ≤ 二叉树节点的度 ≤ 2 ➡
   总边数 ==➡。
   如上图完全二叉树的=5，=4。
   
   （2）节点总数n，根节点为第 1 层时，完全二叉树的高度h满足：

1、在具有 2n 个节点的完全二叉树中，叶子节点个数为（ ）
(A) n (B) n+1 (C) n-1 (D) n/2

• 解析：由题和及得，那么这里为非偶数。而完全二叉树中度为 1 的节点只能是 0 或 1，所以=1，从而得=n 。

2、一棵完全二叉树的节点数为 531，那么这棵树的高度为（ ）
(A) 11 (B) 10 (C) 8 (D) 12

• 解析：运用。

2.4 存储结构

• 顺序存储：用数组存节点，把节点按层序从上到下、从左到右依次塞进数组，靠下标关系找父子。仅适合完全二叉树。普通二叉树会大量空缺节点，数组连空位也占，浪费空间。
• 链式存储：二叉链（面试主流）与三叉链（含父节点指针）

3. 二叉树的顺序结构：堆（面试核心）

3.1 堆基础概念

堆 = 完全二叉树 + 堆序性，用数组顺序存储，额外满足一个堆序性：

• 最大堆：每个节点的值 ≥ 其左右孩子的值 → 根节点是最大值。
• 最小堆：每个节点的值 ≤ 其左右孩子的值 → 根节点是最小值。

根节点元素 = 数组首元素 = 堆顶元素。

3.2 堆排序（必考）

1. 核心规则

标准堆排序升序：初始建大顶堆；降序排序建小顶堆

2. 完整流程

1. 建堆：数组从最后一个非叶子节点向前遍历，依次向下调整
2. 排序循环：堆顶与末尾元素交换 → 移除末尾最大值 → 对剩余数组向下调整堆

3. 复杂度

时间：(O(nlog n))；空间：(O(1))（原地排序）

例题

序列5,11,7,2,3,17升序堆排序，初始建大堆结果：[17,11,7,2,3,5]

3.3 堆四大核心操作（代码底层逻辑）

1. 初始化建堆

数组复制到底层容器，从最后一个非叶子节点(size-2)/2倒序执行向下调整

2. 插入元素 Push

尾部追加新节点 → 对新节点执行向上调整

3. 删除堆顶 Pop（标准写法）

堆顶与数组最后一位交换 → 删除尾部元素 → 对根节点执行向下调整

4. 获取堆顶 Top

直接返回数组首元素arr[0]

调整函数逻辑（小堆为例）

1. 向下调整 AdjustDown (parent) 找左右孩子中小值 child；若孩子值小于父，交换，更新父下标循环；否则终止
2. 向上调整 AdjustUp (child) 求父节点；若子值小于父，交换，更新子下标循环；否则终止

3.4 C++ 极简堆模板（0 下标小堆）

template<class T> class Heap { private: vector<T> _a; void AdjustDown(int parent){ int child = 2*parent+1; while(child < _a.size()){ if(child+1<_a.size() && _a[child+1]<_a[child]) child++; if(_a[child]<_a[parent]){ swap(_a[child],_a[parent]); parent=child; child=2*parent+1; }else break; } } void AdjustUp(int child){ int parent=(child-1)/2; while(child>0){ if(_a[child]<_a[parent]){ swap(_a[child],_a[parent]); child=parent; parent=(child-1)/2; }else break; } } public: Heap(const vector<T>& a):_a(a){ for(int i=(_a.size()-2)/2;i>=0;i--) AdjustDown(i); } void Push(const T& x){_a.push_back(x); AdjustUp(_a.size()-1);} void Pop(){swap(_a[0],_a.back()); _a.pop_back(); AdjustDown(0);} T Top()const{return _a[0];} };

3.5 高频考点：堆删除堆顶过程

例：小根堆[8,15,10,21,34,16]删除堆顶 8

1. 堆尾 12 替换堆顶，数组变为[12,15,10,21,34,16]
2. 向下调整比较次数：3 次 ① 15 vs 10 找更小孩子；② 12 vs 10 交换；③ 12 vs 16 无需交换

3.6 堆经典应用

1. 堆排序：升序建大堆，降序建小堆
2. TopK 问题
   • 求前 K 大元素：建容量 K 的小顶堆，剩余元素大于堆顶则替换调整
   • 求前 K 小元素：建容量 K 的大顶堆，剩余元素小于堆顶则替换调整

4. 二叉树的链式结构（遍历是核心）

4.1 遍历方式（面试必考）

二叉树的遍历是按照某种特定规则，依次对二叉树中的节点进行相应操作，且每个节点只操作一次。遍历是二叉树所有操作的基础，面试中无论是递归还是非递归实现，都需要熟练掌握。

4.1.1 递归遍历（简单但需理解）

递归遍历的核心思想是将大问题分解为小问题：遍历整棵树 = 访问根节点 + 遍历左子树 + 遍历右子树，三者执行顺序不同，形成了前序、中序、后序三种遍历方式。终止条件为遇到空节点（nullptr）。

前序遍历（根→左→右）：

void PreOrder(Node* root) { if (!root) return; // 递归终止条件：空节点无需处理 cout << root->_data << " "; // 第一步：先访问根节点 PreOrder(root->_left); // 第二步：递归遍历左子树 PreOrder(root->_right); // 第三步：递归遍历右子树 }

示例：对于二叉树1(2(3),4(5,6))（左子树 2 含左 3，右子树 4 含左 5、右 6），前序遍历结果为1 2 3 4 5 6。

中序遍历（左→根→右）：

void InOrder(Node* root) { if (!root) return; InOrder(root->_left); // 第一步：先递归遍历左子树 cout << root->_data << " "; // 第二步：再访问根节点 InOrder(root->_right); // 第三步：最后递归遍历右子树 }

示例：同上二叉树，2(3)→1→4(5,6)，而对于2(3)，3（左）→2（中）；对于4(5,6)，5（左）→4（中）→6（右）。那么中序遍历结果为3 2 1 5 4 6。

后序遍历（左→右→根）：

void PostOrder(Node* root) { if (!root) return; PostOrder(root->_left); // 第一步：先递归遍历左子树 PostOrder(root->_right); // 第二步：再递归遍历右子树 cout << root->_data << " "; // 第三步：最后访问根节点 }

示例：同上二叉树，后序遍历结果为3 2 5 6 4 1。

• 三种遍历的区别仅在于访问根节点的时机，左子树始终比右子树先遍历。

4.1.2 非递归遍历（笔试重点，用栈模拟）

递归遍历虽然简洁，但在某些场景下可能因递归深度过深导致栈溢出。非递归遍历的核心是用手动维护的栈模拟递归调用栈，通过控制节点的入栈、出栈顺序，实现与递归相同的访问逻辑。

前序非递归（根→左→右）：

void PreOrderNonR(Node* root) { stack<Node*> st; // 用栈保存待处理的节点（主要是父节点） Node* cur = root; // 用于遍历的当前节点指针 // 循环条件：当前节点非空 或 栈非空（还有未处理的节点） while (cur || !st.empty()) { // 第一步：遍历左路节点，边访问边入栈（前序要求先访问根） while (cur) { cout << cur->_data << " "; // 访问当前节点（根） st.push(cur); // 入栈记录，后续需通过它找右子树 cur = cur->_left; // 继续向左移动，处理左子树 } // 第二步：左路节点处理完，弹出栈顶节点（父节点），转向其右子树 Node* top = st.top(); // 取出最近的父节点 st.pop(); // 父节点的左子树已处理完，出栈 cur = top->_right; // 开始处理父节点的右子树 } }

以1(2(3),4)为例：

1. cur=1入栈，访问 1；cur=2入栈，访问 2；cur=3入栈，访问 3；cur=3->_left=nullptr，退出内层循环。
2. 弹出 3，cur=3->_right=nullptr；再弹出 2，cur=2->_right=nullptr；再弹出 1，cur=1->_right=4。
3. cur=4入栈，访问 4；cur=4->_left=nullptr，弹出 4，cur=4->_right=nullptr；栈空，循环结束。
   结果：1 2 3 4。

中序非递归（左→根→右）：

void InOrderNonR(Node* root) { stack<Node*> st; Node* cur = root; while (cur || !st.empty()) { // 第一步：左路节点全部入栈（中序要求先处理左子树，暂不访问根） while (cur) { st.push(cur); // 入栈暂存，等待左子树处理完后再访问 cur = cur->_left; // 继续向左移动 } // 第二步：弹出栈顶节点（左子树已处理完），访问根，再转向右子树 Node* top = st.top(); st.pop(); cout << top->_data << " "; // 此时左子树为空，访问根节点 cur = top->_right; // 处理右子树（重复上述过程） } }

以1(2(3),4)为例：

1. cur=1入栈→cur=2入栈→cur=3入栈→cur=3->_left=nullptr，退出内层循环。
2. 弹出 3，访问 3；cur=3->_right=nullptr；弹出 2，访问 2；cur=2->_right=nullptr；弹出 1，访问 1；cur=1->_right=4。
3. cur=4入栈→cur=4->_left=nullptr，弹出 4，访问 4；cur=4->_right=nullptr；栈空，循环结束。
   结果：3 2 1 4。

后序非递归（左→右→根，标记法）：
后序遍历的难点在于：必须先处理完左右子树，才能访问根节点。因此需要用标记法记录节点是否已处理过左右子树（未处理则暂存，处理完则访问）。

void PostOrderNonR(Node* root) { // 栈中存储 pair：<节点指针，是否已访问标记>（false=未访问，true=已访问） stack<pair<Node*, bool>> st; st.push({root, false}); // 初始压入根节点，标记为未访问 while (!st.empty()) { auto [cur, visited] = st.top(); // 取出栈顶元素（结构化绑定，C++17） st.pop(); if (!cur) continue; // 空节点直接跳过 if (!visited) { // 未访问：需先处理左右子树，根节点暂存 st.push({cur, true}); // 根节点标记为“已准备好”，重新入栈 st.push({cur->_right, false}); // 右子树入栈（后入先出，保证左子树先处理） st.push({cur->_left, false}); // 左子树入栈 } else { // 已访问：左右子树均处理完，可访问根节点 cout << cur->_data << " "; } } }

以1(2(3),4)为例：

1. 压入(1,false)→弹出，因未访问，压入(1,true)→(4,false)→(2,false)。
2. 弹出(2,false)→未访问，压入(2,true)→(nullptr,false)（2 的右子树）→(3,false)。
3. 弹出(3,false)→未访问，压入(3,true)→(nullptr,false)（3 的右）→(nullptr,false)（3 的左）。
4. 弹出空节点→弹出空节点→弹出(3,true)，访问 3。
5. 弹出空节点→弹出(2,true)，访问 2。
6. 弹出(4,false)→未访问，压入(4,true)→(nullptr,false)（4 的右）→(nullptr,false)（4 的左）。
7. 弹出空节点→弹出空节点→弹出(4,true)，访问 4。
8. 弹出(1,true)，访问 1。
   结果：3 2 4 1。

4.1.3 层序遍历（用队列，求高度 / 宽度）

void LevelOrder(Node* root) { if (!root) return; // 空树直接返回 queue<Node*> q; q.push(root); // 根节点入队，作为第一层的起点 while (!q.empty()) { int size = q.size(); // 关键：记录当前层的节点数（队列中现有元素数） // 遍历当前层的所有节点 for (int i = 0; i < size; ++i) { Node* cur = q.front(); // 取出队头节点 q.pop(); cout << cur->_data << " "; // 访问当前节点 // 将当前节点的左右孩子入队（为下一层准备） if (cur->_left) q.push(cur->_left); if (cur->_right) q.push(cur->_right); } } }

以1(2(3),4(5,6))为例：

1. 初始队列：[1]，size=1→处理 1，入队 2、4→队列变为[2,4]。
2. 第二层：size=2→处理 2（入队 3）→处理 4（入队 5、6）→队列变为[3,5,6]。
3. 第三层：size=3→处理 3（无孩子）→处理 5（无孩子）→处理 6（无孩子）→队列空。
   结果：1 2 4 3 5 6。

5. 二叉搜索树（面试高频）

5.1 核心特性

二叉搜索树简称BST（Binary Search Tree），

1. 非空左子树所有节点值 < 根节点值 <非空右子树所有节点值
   这里的 “左子树” 指根节点左侧的整个子树，“右子树”同理
2. 左、右子树均为 BST
3. 中序遍历结果为严格升序（面试判断 BST 的关键）
   中序遍历的顺序是 “左子树 → 根节点 → 右子树”，而 BST “左小右大”

5.2 核心操作（笔试手写）

5.2.1 插入

• 树空直接插根：如果树是空的（无任何节点），新节点就直接作为整棵树的根节点。
• 非空则按 BST 特性找 “叶子位置” 插入：
  • 具体步骤：从根节点出发，用新节点的键值与当前节点比较。若新键值更小，则向左子树移动；若更大，则向右子树移动。重复此过程，直到当前节点为叶子节点。
  • 记录父节点：过程中需要用一个变量（如parent）记录当前节点的父节点，因为新节点最终要挂在父节点的左或右指针上。
  • 禁止重复节点：若比较过程中发现新键值与某个节点的键值相等，则插入失败（BST 不允许重复节点）。

bool Insert(const K& key, const V& value) { if (!_root) { _root = new Node(key, value); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { parent = cur; if (key < cur->_key) cur = cur->_left; else if (key > cur->_key) cur = cur->_right; else return false; // 不允许重复 } cur = new Node(key, value); (key < parent->_key) ? parent->_left = cur : parent->_right = cur; return true; }

5.2.2 删除（难点、面试重点）

删除操作的难点是在移除节点后仍需保持 BST 的特性。

操作前需先查找目标节点，找到后按以下 3 种情况处理：

情况 1：待删节点左子树为空

• 含义：此时它可能只有右子树，或左右子树都为空。
• 处理方式：直接让待删节点的父节点 “跳过” 待删节点，指向待删节点的右子树。
  • 若待删节点是根节点（无父节点），则让根节点直接变为待删节点的右子树。
  • 若待删节点是父节点的左孩子，则父节点的左指针改为指向待删节点的右子树；若待删节点是父节点的右孩子，则父节点的右指针改为指向待删节点的右子树。
• 最后释放待删节点的内存。

情况 2：待删节点右子树为空

• 含义：此时它可能只有左子树，或左右子树都为空。
• 处理方式：类似情况 1，让待删节点的父节点指向待删节点的左子树。
  • 若待删节点是根节点，则根节点变为待删节点的左子树。
  • 若待删节点是父节点的左孩子，父节点左指针指向待删节点的左子树；若为右孩子，父节点右指针指向待删节点的左子树。
• 最后释放待删节点的内存。

情况 3：待删节点左右子树都非空（替换法）

• 含义：待删节点既有左子树也有右子树，此时直接删除会破坏 BST 结构，需用 “替换法” 处理。
• 核心思路：找一个合适的节点替换待删节点的值，再删除这个 “替换节点”（替换节点的结构一定符合情况 1 或 2，便于删除）。
• 具体步骤：
  1. 找替换节点：选择待删节点右子树中 “值最小的节点”（即右子树中最左侧的节点，因为右子树的最左节点是该子树中最小的，且它的左子树一定为空）。
  2. 替换值：将替换节点的键值和值复制到待删节点中，覆盖原有值（此时待删节点的值已更新，BST 特性暂时保持）。
  3. 删除替换节点：由于替换节点是右子树的最左节点，其左子树为空（符合情况 1），直接按情况 1 的方式删除即可（让替换节点的父节点指向它的右子树）。
  4. 最后释放替换节点的内存（原待删节点已被 “间接删除”）。

bool Erase(const K& key) { Node* cur = _root; Node* parent = nullptr; // 查找节点 while (cur && cur->_key != key) { parent = cur; cur = (key < cur->_key) ? cur->_left : cur->_right; } if (!cur) return false; // 未找到 // 情况1：左空 if (!cur->_left) { if (cur == _root) _root = cur->_right; else (parent->_left == cur) ? parent->_left = cur->_right : parent->_right = cur->_right; } // 情况2：右空 else if (!cur->_right) { if (cur == _root) _root = cur->_left; else (parent->_left == cur) ? parent->_left = cur->_left : parent->_right = cur->_left; } // 情况3：左右非空（右子树最小节点替换） else { Node* minParent = cur; Node* minNode = cur->_right; while (minNode->_left) { // 找右子树最左节点（最小） minParent = minNode; minNode = minNode->_left; } cur->_key = minNode->_key; // 替换值 cur->_value = minNode->_value; // 删除minNode（左空，直接调整） (minParent->_left == minNode) ? minParent->_left = minNode->_right : minParent->_right = minNode->_right; cur = minNode; // 最后释放minNode } delete cur; return true; }