一、二叉树的基本概念与性质1. 二叉树的分类树由节点和边组成的层次结构每个节点可以有多个子节点。二叉树每个节点最多有两个子节点左孩子和右孩子。完全二叉树除最后一层外其他层的节点数都达到最大值且最后一层的节点从左到右连续排列。满二叉树所有层的节点数都达到最大值即每层节点数为 2^{i-1}其中 i 是层数。2. 二叉树的重要性质第 i 层最多节点数2^{i-1}根节点层数为 1。深度为 h 的二叉树最大节点数2^h - 1。叶节点数与度为 2 的节点数关系对任何二叉树若叶节点数为 n_0度为 2 的分支节点数为 n_2则 n_0 n_2 1。总节点数N n_0 n_1 n_2n_1 为度为 1 的节点数。3. 二叉树的深度计算满二叉树高度 h log_2(N1)2 为底。完全二叉树高度 h 满足 {2^(h-1) n (2^h)-1} n是节点个数4. 完全二叉树的节点编号从 0 开始父亲下标若节点下标为 i则父亲下标为 (i-1)/2i0。左孩子下标2i1若 2i1 N否则无左孩子。右孩子下标2i2若 2i2 N否则无右孩子。二、堆的概念与性质1. 堆的定义堆是一种特殊的完全二叉树分为两种类型大堆每个节点的值都大于或等于其子节点的值堆顶是最大值。小堆每个节点的值都小于或等于其子节点的值堆顶是最小值。2. 堆的性质结构性堆是完全二叉树满足完全二叉树的所有性质。有序性大堆中父节点值 ≥ 子节点值小堆中父节点值 ≤ 子节点值。3. 堆的操作无非增删查改增将新元素添加到堆的末尾然后向上调整以维持堆性质。删删除堆顶元素将堆尾元素移至堆顶然后向下调整以维持堆性质。后面删除操作以此图为例子挡住对应的值然后模拟三、搜索二叉树BST的实现1. BST 的定义左子树所有节点的键值小于根节点的键值。右子树所有节点的键值大于根节点的键值。左右子树也分别是搜索二叉树。2. BST 的节点结构templateclassKstructBSTreeNode{BSTreeNode*_leftnullptr;BSTreeNode*_rightnullptr;K _key;BSTreeNode(constKkey):_key(key){}};3. BST 的核心操作3.1 插入操作实现原理使用双指针cur遍历parent记录父节点找到插入位置然后创建新节点并连接到父节点。只存在尾插不存在中间插入。如int a[] {5,6,7,2,3,1,5,9,55,2};代码实现boolInsert(constKkey){if(_rootnullptr){_rootnewNode(key);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){parentcur;if(cur-_keykey)curcur-_right;elseif(keycur-_key)curcur-_left;elseif(cur-_keykey)returnfalse;// 不允许重复键}curnewNode(key);if(keyparent-_key)parent-_leftcur;elseparent-_rightcur;returntrue;}3.2 遍历查找操作实现原理从根节点开始根据键值大小向左或右子树遍历直到找到目标节点或遍历结束。核心区别前 / 中 / 后序的唯一差异是根结点的访问时机左子树永远优先于右子树前序遍历:“根 → 左 → 右”中序遍历:“左 → 根 → 右” (升序)后序遍历:“左 → 右 → 根”代码实现void_InOrder(Node*root){if(rootnullptr)return;_InOrder(root-_left);coutroot-_key root-_val ;// 取根_InOrder(root-_right);}voidInOrder(){_InOrder(_root);coutendl;}void_PreOrder(Node*root){if(rootnullptr)return;coutroot-_key root-_val ;// 取根_PreOrder(root-_left);_PreOrder(root-_right);}voidPreOrder(){_PreOrder(_root);coutendl;}void_PostOrder(Node*root){if(rootnullptr)return;_PostOrder(root-_left);_PostOrder(root-_right);coutroot-_key root-_val ;// 取根}voidPostOrder(){_PostOrder(_root);coutendl;}3.2 补 非递归实现遍历非递归遍历的优势避免递归栈溢出对于深度较大的树递归可能导致栈溢出非递归实现更稳定。性能优化减少递归调用的开销如函数调用栈的压栈/弹栈。灵活性可根据需要调整遍历逻辑例如添加额外的处理步骤。非递归遍历通过栈来模拟递归过程避免递归栈溢出的风险同时提高性能。以下是三种遍历的非递归实现前序遍历非递归实现思路初始化将根节点压入栈。循环处理弹出栈顶节点并访问然后依次压入右孩子、左孩子先压右保证左孩子先被处理。结束条件栈为空。代码实现voidPreOrderNonRecursive(){if(_rootnullptr)return;stackNode*st;st.push(_root);while(!st.empty()){Node*curst.top();st.pop();coutcur-_key cur-_val ;// 访问根节点if(cur-_right)st.push(cur-_right);// 先压右孩子if(cur-_left)st.push(cur-_left);// 后压左孩子}coutendl;}中序遍历非递归实现思路初始化从根节点开始将所有左孩子依次压入栈。循环处理弹出栈顶节点并访问若该节点有右孩子将右孩子及其所有左孩子依次压入栈。结束条件栈为空且当前节点为 nullptr。代码实现voidInOrderNonRecursive(){if(_rootnullptr)return;stackNode*st;Node*cur_root;while(cur||!st.empty()){// 压入所有左孩子while(cur){st.push(cur);curcur-_left;}// 弹出并访问curst.top();st.pop();coutcur-_key cur-_val ;// 访问根节点// 处理右子树curcur-_right;}coutendl;}后序遍历非递归实现思路使用一个栈 访问标记标记节点是否已被访问。初始化将根节点压入栈标记为未访问。循环处理弹出栈顶节点若未访问则重新压入标记为已访问然后依次压入右孩子、左孩子未访问若已访问则访问该节点。结束条件栈为空。代码实现voidPostOrderNonRecursive(){if(_rootnullptr)return;stackpairNode*,boolst;// 节点, 是否已访问st.push({_root,false});while(!st.empty()){auto[cur,visited]st.top();st.pop();if(!visited){// 未访问重新压入标记为已访问然后压入右、左孩子未访问st.push({cur,true});if(cur-_right)st.push({cur-_right,false});if(cur-_left)st.push({cur-_left,false});}else{// 已访问输出coutcur-_key cur-_val ;}}coutendl;}查找示例查找 3从根节点 5 开始3 5进入左子树。左子树节点 23 2进入右子树。右子树节点 3找到目标返回 true。查找 10从根节点 5 开始10 5进入右子树。右子树节点 610 6进入右子树。右子树节点 910 9进入右子树。右子树节点 5510 55进入左子树为空返回 false。代码实现boolFind(constKkey){Node*cur_root;while(cur){if(cur-_keykey)curcur-_right;elseif(keycur-_key)curcur-_left;elseif(cur-_keykey)returntrue;}returnfalse;}3.3、删除操作与需要注意的关键细节实现原理根据目标节点的子节点情况分三种情况处理左子树为空用右子树替换目标节点。右子树为空用左子树替换目标节点。左右子树均非空找到右子树的最小节点最左节点替换目标节点的值然后删除该最小节点。1. 父节点指针的及时正确的更新注意点 parent cur; 放里面放外面会被同步为子节点。代码实现while(cur){if(keycur-_key){parentcur;// 重要更新父节点curcur-_left;}elseif(keycur-_key){parentcur;// 重要更新父节点curcur-_right;}elseif(keycur-_key){// 删除逻辑}}2. 边界情况删除根节点注意点当目标节点是根节点时需要特殊处理直接更新根节点指针。原因根节点没有父节点无法通过parent指针进行操作必须直接修改_root指针。忽略后果删除普通值不存在问题但oj通不过根节点删不动调试会报错。代码实现// 情况1左子树为空if(cur-_leftnullptr){if(cur_root)_rootcur-_right;//此处直接赋值else{if(parent-_leftcur)parent-_leftcur-_right;elseparent-_rightcur-_right;}// ...}// 情况2右子树为空elseif(cur-_rightnullptr){if(cur_root)_rootcur-_left;else{if(parent-_leftcur)parent-_leftcur-_left;elseparent-_rightcur-_left;}}3. 左右子树均非空时的处理注意点当目标节点左右子树均非空时需要找到右子树的最小节点最左节点进行替换然后删除该最小节点。原因右子树的最小节点是右子树中键值最小的节点替换目标节点后仍能保持 BST 性质。必须根据minRight是父节点的左还是右孩子进行处理否则会导致树结构损坏。代码实现else{Node*minRightPerentcur;Node*minRightcur-_right;while(minRight-_left){minRightPerentminRight;minRightminRight-_left;}cur-_keyminRight-_key;// 关键根据 minRight 是父节点的左还是右孩子进行处理if(minRightPerent-_leftminRight)minRightPerent-_leftminRight-_right;elseminRightPerent-_rightminRight-_right;deleteminRight;minRightnullptr;}4. 内存管理注意点删除节点后必须释放内存并将指针置空避免内存泄漏和野指针。deletecur;curnullptr;整体代码实现voidErase(constKkey){Node*cur_root;Node*parentcur;while(cur){if(keycur-_key){parentcur;curcur-_left;}elseif(keycur-_key){parentcur;curcur-_right;}elseif(keycur-_key){// 情况1左子树为空if(cur-_leftnullptr){if(cur_root)_rootcur-_right;else{if(parent-_leftcur)parent-_leftcur-_right;elseparent-_rightcur-_right;}deletecur;curnullptr;}// 情况2右子树为空elseif(cur-_rightnullptr){if(cur_root)_rootcur-_left;else{if(parent-_leftcur)parent-_leftcur-_left;elseparent-_rightcur-_left;}deletecur;curnullptr;}// 情况3左右子树均非空else{Node*minRightPerentcur;Node*minRightcur-_right;while(minRight-_left){minRightPerentminRight;minRightminRight-_left;}cur-_keyminRight-_key;if(minRightPerent-_leftminRight)minRightPerent-_leftminRight-_right;elseminRightPerent-_rightminRight-_right;deleteminRight;minRightnullptr;}}}}4. BST 的遍历中序遍历BST 的中序遍历结果是升序序列这是 BST 的重要特性。代码实现void_InOrder(Node*root){if(rootnullptr)return;_InOrder(root-_left);coutroot-_key ;_InOrder(root-_right);}voidInOrder(){_InOrder(_root);coutendl;}四、代码测试与示例测试代码voidFunc15(){BSTreeintt;inta[]{5,6,7,2,3,1,5,9,55,2};for(autoe:a){coute ;t.Insert(e);}coutendl;t.InOrder();coutFind 3: t.Find(3)endl;coutFind 10: t.Find(10)endl;t.Erase(1);t.InOrder();t.Erase(5);t.InOrder();t.Erase(55);t.InOrder();}运行结果5 6 7 2 3 1 5 9 55 2 1 2 3 5 6 7 9 55 Find 3: 1 Find 10: 0 2 3 5 6 7 9 55 2 3 6 7 9 55 2 3 6 7 9五、总结与常见问题1. 二叉树的应用场景堆优先队列、堆排序。搜索二叉树高效的查找、插入、删除操作平均时间复杂度 O(log n)。平衡二叉树如 AVL 树、红黑树解决 BST 在极端情况下退化为链表的问题。2. 常见问题与解决方案BST 插入重复键BST 不允许重复键插入时遇到重复键直接返回 false。BST 删除操作需要分三种情况处理特别是左右子树均非空的情况需要找到右子树的最小节点进行替换。堆的调整插入和删除操作后需要通过上浮或下沉调整堆以维持堆的性质。搜索二叉树效率问题一、BST 效率低的核心原因树退化为链表BST 的效率依赖于树的高度高度平衡的 BST 才能发挥其 O(log n) 的时间复杂度优势。当插入的键值是递增或递减的有序序列时BST 会退化成单支树链表。如12345呈现结果如下二、为什么退化会导致效率低BST 的操作查找、插入、删除时间复杂度与树的高度直接相关平衡情况树的高度为 O(log n)操作时间复杂度为 O(log n)。退化情况树的高度为 O(n)操作时间复杂度退化为 O(n)。例如查找一个键值时需要从根节点开始根据键值大小向左或右子树遍历。当树退化为链表时每次查找都需要遍历几乎所有节点效率与线性表如链表相同失去了 BST 的优势。三、如何避免 BST 退化为了避免 BST 退化通常使用平衡二叉树如 AVL 树、红黑树它们通过自平衡机制保证树的高度始终保持在 O(log n) 级别。BST 效率低的根本原因是树结构退化特别是插入有序或逆序序列时会退化为链表导致操作时间复杂度从 O(log n) 退化为 O(n)。为了避免这种情况实际应用中通常使用平衡二叉树如 AVL 树、红黑树来保证树的高度平衡从而维持高效的操作性能。练习题二叉树创建字符串。OJ二叉树的分层遍历1。OJ二叉树的分层遍历2。OJ给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 。OJ二叉树搜索树转换成排序双向链表。OJ根据一棵树的前序遍历与中序遍历构造二叉树。OJ根据一棵树的中序遍历与后序遍历构造二叉树。OJ