如果你在阅读过程中有任何疑问或想要进一步探讨的内容欢迎在评论区畅所欲言我们一起学习、共同成长~ 如果你觉得这篇文章还不错不妨顺手点个赞、加入收藏并分享给更多的朋友噢~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(m0)棵不相交树的集合1.3 树的表示主要了解孩子兄弟表示法templateclass T struct TreeNode { T _data; // 节点存储的数据 TreeNodeT* _firstChild; // 指向当前节点的第一个直接子节点 TreeNodeT* _nextBrother; // 指向与当前节点拥有同一个父节点的下一个节点 };以上图的节点B为例_dataB_firstChild指向D_nextBrother指向C孩子兄弟表示法的本质通过_firstChild纵向连接子树和_nextBrother横向连接兄弟将多叉树转化为二叉树结构纵向访问子树时遍历_firstChild链如B → DD → 无B → EE → H。横向访问兄弟时遍历_nextBrother链如B → CD → EE → FH → I。2. 二叉树基础2.1 二叉树的定义二叉树是节点的有限集合要么为空要么由“根节点左子树右子树”组成左、右子树均为二叉树。特性节点度2子树有左右次序因此二叉树是有序树。2.2 特殊二叉树高频考点2.2.1 满二叉树一棵二叉树每一层的节点都达最大值即一棵二叉树第k层的节点总数为那么它就是满二叉树。2.2.2 完全二叉树除了最后一层外其他层全满最后一层节点从左到右连续排列可缺右部节点。满二叉树是一种特殊的完全二叉树。根节点索引为 0 时节点 i 的父节点索引(i - 1) / 2整数除法左子节点索引2 * i 1右子节点索引2 * i 22.3 二叉树的性质第k层最多个节点排满深度h的二叉树最多个节点核心公式计算题高频1对任意非空二叉树若度为0的叶节点数度为1的节点数度为2的节点数0 ≤ 二叉树节点的度 ≤ 2 ➡总边数 ➡。如上图完全二叉树的54。2节点总数n根节点为第 1 层时完全二叉树的高度h满足1、在具有 2n 个节点的完全二叉树中叶子节点个数为 (A) n (B) n1 (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. 完整流程建堆数组从最后一个非叶子节点向前遍历依次向下调整排序循环堆顶与末尾元素交换 → 移除末尾最大值 → 对剩余数组向下调整堆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]调整函数逻辑小堆为例向下调整 AdjustDown (parent) 找左右孩子中小值 child若孩子值小于父交换更新父下标循环否则终止向上调整 AdjustUp (child) 求父节点若子值小于父交换更新子下标循环否则终止3.4 C 极简堆模板0 下标小堆templateclass T class Heap { private: vectorT _a; void AdjustDown(int parent){ int child 2*parent1; while(child _a.size()){ if(child1_a.size() _a[child1]_a[child]) child; if(_a[child]_a[parent]){ swap(_a[child],_a[parent]); parentchild; child2*parent1; }else break; } } void AdjustUp(int child){ int parent(child-1)/2; while(child0){ if(_a[child]_a[parent]){ swap(_a[child],_a[parent]); childparent; parent(child-1)/2; }else break; } } public: Heap(const vectorT a):_a(a){ for(int i(_a.size()-2)/2;i0;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堆尾 12 替换堆顶数组变为[12,15,10,21,34,16]向下调整比较次数3 次 ① 15 vs 10 找更小孩子② 12 vs 10 交换③ 12 vs 16 无需交换3.6 堆经典应用堆排序升序建大堆降序建小堆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) { stackNode* 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)为例cur1入栈访问 1cur2入栈访问 2cur3入栈访问 3cur3-_leftnullptr退出内层循环。弹出 3cur3-_rightnullptr再弹出 2cur2-_rightnullptr再弹出 1cur1-_right4。cur4入栈访问 4cur4-_leftnullptr弹出 4cur4-_rightnullptr栈空循环结束。结果1 2 3 4。中序非递归左→根→右void InOrderNonR(Node* root) { stackNode* 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)为例cur1入栈→cur2入栈→cur3入栈→cur3-_leftnullptr退出内层循环。弹出 3访问 3cur3-_rightnullptr弹出 2访问 2cur2-_rightnullptr弹出 1访问 1cur1-_right4。cur4入栈→cur4-_leftnullptr弹出 4访问 4cur4-_rightnullptr栈空循环结束。结果3 2 1 4。后序非递归左→右→根标记法后序遍历的难点在于必须先处理完左右子树才能访问根节点。因此需要用标记法记录节点是否已处理过左右子树未处理则暂存处理完则访问。void PostOrderNonR(Node* root) { // 栈中存储 pair节点指针是否已访问标记false未访问true已访问 stackpairNode*, bool st; st.push({root, false}); // 初始压入根节点标记为未访问 while (!st.empty()) { auto [cur, visited] st.top(); // 取出栈顶元素结构化绑定C17 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,false)→弹出因未访问压入(1,true)→(4,false)→(2,false)。弹出(2,false)→未访问压入(2,true)→(nullptr,false)2 的右子树→(3,false)。弹出(3,false)→未访问压入(3,true)→(nullptr,false)3 的右→(nullptr,false)3 的左。弹出空节点→弹出空节点→弹出(3,true)访问 3。弹出空节点→弹出(2,true)访问 2。弹出(4,false)→未访问压入(4,true)→(nullptr,false)4 的右→(nullptr,false)4 的左。弹出空节点→弹出空节点→弹出(4,true)访问 4。弹出(1,true)访问 1。结果3 2 4 1。4.1.3 层序遍历用队列求高度 / 宽度void LevelOrder(Node* root) { if (!root) return; // 空树直接返回 queueNode* 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]size1→处理 1入队 2、4→队列变为[2,4]。第二层size2→处理 2入队 3→处理 4入队 5、6→队列变为[3,5,6]。第三层size3→处理 3无孩子→处理 5无孩子→处理 6无孩子→队列空。结果1 2 4 3 5 6。5. 二叉搜索树面试高频5.1 核心特性二叉搜索树简称BSTBinary Search Tree非空左子树所有节点值 根节点值 非空右子树所有节点值这里的 “左子树” 指根节点左侧的整个子树“右子树”同理左、右子树均为 BST中序遍历结果为严格升序面试判断 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便于删除。具体步骤找替换节点选择待删节点右子树中 “值最小的节点”即右子树中最左侧的节点因为右子树的最左节点是该子树中最小的且它的左子树一定为空。替换值将替换节点的键值和值复制到待删节点中覆盖原有值此时待删节点的值已更新BST 特性暂时保持。删除替换节点由于替换节点是右子树的最左节点其左子树为空符合情况 1直接按情况 1 的方式删除即可让替换节点的父节点指向它的右子树。最后释放替换节点的内存原待删节点已被 “间接删除”。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; }
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(m0)棵不相交树的集合1.3 树的表示主要了解孩子兄弟表示法templateclass T struct TreeNode { T _data; // 节点存储的数据 TreeNodeT* _firstChild; // 指向当前节点的第一个直接子节点 TreeNodeT* _nextBrother; // 指向与当前节点拥有同一个父节点的下一个节点 };以上图的节点B为例_dataB_firstChild指向D_nextBrother指向C孩子兄弟表示法的本质通过_firstChild纵向连接子树和_nextBrother横向连接兄弟将多叉树转化为二叉树结构纵向访问子树时遍历_firstChild链如B → DD → 无B → EE → H。横向访问兄弟时遍历_nextBrother链如B → CD → EE → FH → I。2. 二叉树基础2.1 二叉树的定义二叉树是节点的有限集合要么为空要么由“根节点左子树右子树”组成左、右子树均为二叉树。特性节点度2子树有左右次序因此二叉树是有序树。2.2 特殊二叉树高频考点2.2.1 满二叉树一棵二叉树每一层的节点都达最大值即一棵二叉树第k层的节点总数为那么它就是满二叉树。2.2.2 完全二叉树除了最后一层外其他层全满最后一层节点从左到右连续排列可缺右部节点。满二叉树是一种特殊的完全二叉树。根节点索引为 0 时节点 i 的父节点索引(i - 1) / 2整数除法左子节点索引2 * i 1右子节点索引2 * i 22.3 二叉树的性质第k层最多个节点排满深度h的二叉树最多个节点核心公式计算题高频1对任意非空二叉树若度为0的叶节点数度为1的节点数度为2的节点数0 ≤ 二叉树节点的度 ≤ 2 ➡总边数 ➡。如上图完全二叉树的54。2节点总数n根节点为第 1 层时完全二叉树的高度h满足1、在具有 2n 个节点的完全二叉树中叶子节点个数为 (A) n (B) n1 (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. 完整流程建堆数组从最后一个非叶子节点向前遍历依次向下调整排序循环堆顶与末尾元素交换 → 移除末尾最大值 → 对剩余数组向下调整堆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]调整函数逻辑小堆为例向下调整 AdjustDown (parent) 找左右孩子中小值 child若孩子值小于父交换更新父下标循环否则终止向上调整 AdjustUp (child) 求父节点若子值小于父交换更新子下标循环否则终止3.4 C 极简堆模板0 下标小堆templateclass T class Heap { private: vectorT _a; void AdjustDown(int parent){ int child 2*parent1; while(child _a.size()){ if(child1_a.size() _a[child1]_a[child]) child; if(_a[child]_a[parent]){ swap(_a[child],_a[parent]); parentchild; child2*parent1; }else break; } } void AdjustUp(int child){ int parent(child-1)/2; while(child0){ if(_a[child]_a[parent]){ swap(_a[child],_a[parent]); childparent; parent(child-1)/2; }else break; } } public: Heap(const vectorT a):_a(a){ for(int i(_a.size()-2)/2;i0;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堆尾 12 替换堆顶数组变为[12,15,10,21,34,16]向下调整比较次数3 次 ① 15 vs 10 找更小孩子② 12 vs 10 交换③ 12 vs 16 无需交换3.6 堆经典应用堆排序升序建大堆降序建小堆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) { stackNode* 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)为例cur1入栈访问 1cur2入栈访问 2cur3入栈访问 3cur3-_leftnullptr退出内层循环。弹出 3cur3-_rightnullptr再弹出 2cur2-_rightnullptr再弹出 1cur1-_right4。cur4入栈访问 4cur4-_leftnullptr弹出 4cur4-_rightnullptr栈空循环结束。结果1 2 3 4。中序非递归左→根→右void InOrderNonR(Node* root) { stackNode* 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)为例cur1入栈→cur2入栈→cur3入栈→cur3-_leftnullptr退出内层循环。弹出 3访问 3cur3-_rightnullptr弹出 2访问 2cur2-_rightnullptr弹出 1访问 1cur1-_right4。cur4入栈→cur4-_leftnullptr弹出 4访问 4cur4-_rightnullptr栈空循环结束。结果3 2 1 4。后序非递归左→右→根标记法后序遍历的难点在于必须先处理完左右子树才能访问根节点。因此需要用标记法记录节点是否已处理过左右子树未处理则暂存处理完则访问。void PostOrderNonR(Node* root) { // 栈中存储 pair节点指针是否已访问标记false未访问true已访问 stackpairNode*, bool st; st.push({root, false}); // 初始压入根节点标记为未访问 while (!st.empty()) { auto [cur, visited] st.top(); // 取出栈顶元素结构化绑定C17 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,false)→弹出因未访问压入(1,true)→(4,false)→(2,false)。弹出(2,false)→未访问压入(2,true)→(nullptr,false)2 的右子树→(3,false)。弹出(3,false)→未访问压入(3,true)→(nullptr,false)3 的右→(nullptr,false)3 的左。弹出空节点→弹出空节点→弹出(3,true)访问 3。弹出空节点→弹出(2,true)访问 2。弹出(4,false)→未访问压入(4,true)→(nullptr,false)4 的右→(nullptr,false)4 的左。弹出空节点→弹出空节点→弹出(4,true)访问 4。弹出(1,true)访问 1。结果3 2 4 1。4.1.3 层序遍历用队列求高度 / 宽度void LevelOrder(Node* root) { if (!root) return; // 空树直接返回 queueNode* 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]size1→处理 1入队 2、4→队列变为[2,4]。第二层size2→处理 2入队 3→处理 4入队 5、6→队列变为[3,5,6]。第三层size3→处理 3无孩子→处理 5无孩子→处理 6无孩子→队列空。结果1 2 4 3 5 6。5. 二叉搜索树面试高频5.1 核心特性二叉搜索树简称BSTBinary Search Tree非空左子树所有节点值 根节点值 非空右子树所有节点值这里的 “左子树” 指根节点左侧的整个子树“右子树”同理左、右子树均为 BST中序遍历结果为严格升序面试判断 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便于删除。具体步骤找替换节点选择待删节点右子树中 “值最小的节点”即右子树中最左侧的节点因为右子树的最左节点是该子树中最小的且它的左子树一定为空。替换值将替换节点的键值和值复制到待删节点中覆盖原有值此时待删节点的值已更新BST 特性暂时保持。删除替换节点由于替换节点是右子树的最左节点其左子树为空符合情况 1直接按情况 1 的方式删除即可让替换节点的父节点指向它的右子树。最后释放替换节点的内存原待删节点已被 “间接删除”。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; }
