数据结构 | 二叉搜索树

一、二叉搜索树定义1. 标准定义二叉搜索树Binary Search Tree简称BST是在普通二叉树基础上增加有序约束的特殊二叉树由 nn≥0个节点构成。空BST无任何节点非空BST所有节点关键字不允许重复且必须遵守全局有序规则。2. 核心性质整棵树统一有序判定规则任意节点其左子树内所有节点关键字 当前节点关键字 其右子树内所有节点关键字。补充考点对二叉搜索树进行中序遍历输出序列一定是升序该特征是区分普通二叉树与BST最直观判定依据考试高频出题点。3. 专业基础名词直接前驱、直接后继直接前驱 指中序遍历序列里当前节点的前一个节点分三类查找情况情况 1当前节点左子树不为空前驱为左子树中数值最大的节点持续向右遍历左子树末端即可情况 2当前节点左子树为空向上回溯父节点若回溯节点关键字小于当前节点继续向上回溯若回溯节点关键字大于当前节点该节点即为前驱情况 3持续回溯直至父节点为 NULL代表该节点无直接前驱序列第一个元素直接后继 指中序遍历序列里当前节点的下一个节点分三类查找情况情况 1当前节点右子树不为空后继为右子树中数值最小的节点持续向左遍历右子树末端即可情况 2当前节点右子树为空向上回溯父节点若回溯节点关键字小于当前节点继续向上回溯若回溯节点关键字大于当前节点该节点即为后继情况 3持续回溯直至父节点为 NULL代表该节点无直接后继序列最后一个元素二、BST 存储结构1. 存储设计思路普通二叉树二叉链表仅存储左右孩子指针无法向上回溯祖先节点获取前驱、后继逻辑繁琐。本文采用三叉链表存储结构在原有左、右孩子指针基础上新增parent父节点指针支持双向查找大幅简化删除、前驱后继查询逻辑。2. 结构体定义分为两层结构体BSTNode为单个节点单元BSTree封装根节点指针统一管理整棵树。// 保持原样使用前置声明 typedef int ELEMTYPE; // 假设元素类型为int struct BSTNode { ELEMTYPE data; BSTNode* leftchild; BSTNode* rightchild; BSTNode* parent; }; struct BSTree { BSTNode* root; };3. 三叉链表优缺点优点支持向上回溯父节点快速获取前驱、后继删除双分支节点逻辑简化无需递归遍历查找父节点。缺点每个节点多存储一根父指针内存开销更大增删节点时需同步维护parent指针操作不当极易出现野指针、指针指向错乱。适配范围频繁执行删除、查找前驱 / 后继的业务场景仅做单纯查找、遍历场景推荐使用二叉链表节省内存。三、底层工具函数工具函数为业务操作提供底层支撑仅由普通对外函数内部调用不对外提供使用。1. BuyNode 创建新节点实现思路动态分配节点内存使用 C new 创建节点构造函数自动初始化左右孩子、父指针全部置空返回新节点地址。代码实现// 申请新节点 BSTNode* BuyNode() { BSTNode* pnewnode new BSTNode; return pnewnode; }2. Get_PreNode 获取当前节点直接前驱实现思路断言校验节点非空分两大分支处理左子树存在取左子树最大值左子树不存在则向上回溯父节点匹配前驱规则。代码实现BSTNode* Get_PreNode(BSTNode* node) { assert(node ! nullptr); BSTNode* p node; //当前节点左子树不为空找左子树最大值 if (node-leftchild ! nullptr) { p p-leftchild; while (p-rightchild ! nullptr) p p-rightchild; } //当前节点左子树为空向上回溯父节点 else { p p-parent; while (p ! nullptr p-data node-data) { p p-parent; } //循环退出两种情况找到前驱 / 回溯至nullptr无先驱 } return p; }3. Get_NextNode 获取当前节点直接后继实现思路断言校验节点非空分两大分支处理右子树存在取右子树最小值右子树不存在则向上回溯父节点匹配后继规则。代码实现BSTNode* Get_NextNode(BSTNode* node) { assert(node ! nullptr); BSTNode* p node; //当前节点右子树不为空找右子树最小值 if (node-rightchild ! nullptr) { p p-rightchild; while (p-leftchild ! nullptr) p p-leftchild; } //当前节点右子树为空向上回溯父节点 else { p p-parent; while (p! nullptrp-datanode-data) { p p-parent; } //循环退出两种情况找到后继 / 回溯至nullptr无后继 } return p; }四、BST 五大基础操作1. 初始化二叉搜索树实现思路断言校验树结构体指针合法将根指针置空代表空树。代码实现BSTNode* Init_BST(BSTree* pTree) { assert(pTree ! nullptr); pTree-root nullptr; return pTree-root; }2. 插入节点实现思路断言校验树指针单独处理空树场景直接新建节点作为根节点双指针遍历p 遍历查找插入位置pp 记录 p 的父节点遍历过程匹配有序规则待插入值小于当前节点往左走大于则往右走若循环找到等值节点BST不允许重复值直接返回创建新节点根据大小关系挂载至父节点左 / 右分支绑定父子指针代码实现bool Insert_BST(BSTree* pTree, ELEMTYPE val) { assert(pTree ! nullptr); //空树直接创建根节点 if (pTree-root nullptr) { BSTNode* pnewnode BuyNode(); pnewnode-data val; pTree-root pnewnode; pnewnode-parent nullptr; return true; } //双指针遍历寻找插入位置 BSTNode* ppTree-root; BSTNode* ppnullptr; while (p!nullptrp-data!val) { pp p; if (p-data val) p p-leftchild; else p p-rightchild; } //存在重复节点插入失败 if (p ! nullptr p-data val) return false; BSTNode* pnewnode BuyNode(); pnewnode-data val; //挂载到父节点对应分支绑定父指针 if (pnewnode-datapp-data) pp-rightchild pnewnode; else pp-leftchild pnewnode; pnewnode-parent pp; return true; }3. 循环查找节点实现思路断言校验根节点非空指针 p 从根节点开始遍历循环判定当前指针不为空且关键字不匹配按大小规则向左 / 右子树查找循环退出两种分支p 为 nullptr 代表查找失败p 不为 nullptr 代表找到目标节点代码实现BSTNode* Search_BST(BSTNode* root,ELEMTYPE val) { assert(root!nullptr); BSTNode* p root; while (p!nullptrp-data!val) { if (val p-data) { p p-leftchild; } else { p p-rightchild; } } return p; }4. 删除节点1三类删除场景对比零孩子叶子节点直接断开父指针释放当前节点逻辑最简单单孩子仅左 / 右子树唯一子节点直接顶替当前节点位置更新父指针双孩子左右子树均存在无法直接替换子树采用狸猫换太子方案转换为前两种场景2狸猫换太子核心原理直接前驱、直接后继节点的固有特性二者最多只存在单侧子树不存在同时拥有左右两个孩子的情况。将后继节点数据覆盖到待删节点删除逻辑转移至后继节点规避复杂双分支替换操作大幅降低代码复杂度。补充考点前驱、后继均可替换二者效果完全一致工程中常用后继实现。5. 中序遍历打印实现思路利用栈模拟递归流程BST中序遍历输出严格升序tag 标记控制左子树持续入栈逻辑弹出节点打印后处理右子树。代码实现void Show_InOrder_BST(BSTNode* root) { assert(root ! nullptr); std::stackBSTNode* st; st.push(root); bool tag true; while (!st.empty()) { while (tagst.top()-leftchild ! nullptr) { st.push(st.top()-leftchild); } BSTNode* tmp st.top(); st.pop(); printf(%d , tmp-data); if (tmp-rightchild ! nullptr) { st.push(tmp-rightchild); tag true; } else { tag false; } } }五、BST 删除逻辑专项解析1. 仅处理 0 个子节点实现思路先查找目标节点存在且无左右孩子断开父节点对应分支指针释放目标节点内存。代码实现bool Delete_BST0(BSTree* pTree, ELEMTYPE val) { assert(pTree ! nullptr); BSTNode* p Search_BST(pTree-root, val); if (p nullptr) return false; //仅处理叶子节点 if (p-leftchild ! nullptr || p-rightchild ! nullptr) return false; BSTNode* father p-parent; if (father nullptr) pTree-root nullptr; else { if (p-datafather-data) father-leftchild nullptr; else father-rightchild nullptr; } delete p; p nullptr; return true; }2. 处理 0/1 个子节点实现思路查找目标节点判定至多只有单侧子节点取出唯一子节点直接顶替待删节点位置同步修改父指针后释放内存。代码实现bool Delete_BST1(BSTree* pTree, ELEMTYPE val) { assert(pTree ! nullptr); BSTNode* p Search_BST(pTree-root, val); if (p nullptr) return false; //存在两个子节点不处理 if(p-leftchild ! nullptr p-rightchild ! nullptr) return false; BSTNode* father p-parent; //取出唯一存在的子节点 BSTNode* child p-leftchild ! nullptr ? p-leftchild : p-rightchild; if (father nullptr) pTree-root child; else { if (p-data father-data) { father-leftchild child; } else { father-rightchild child; } } delete p; p nullptr; return true; }3. 整合全场景删除实现思路查找待删除节点无节点直接返回场景 1零 / 单分支直接复用单分支删除逻辑场景 2存在左右双孩子执行狸猫换太子获取当前节点直接后继用后继关键字覆盖待删节点数据将删除目标转移至后继节点后继最多仅单分支复用单分支删除逻辑完成释放代码实现bool Delete_BST(BSTree* pTree, ELEMTYPE val) { assert(pTree ! nullptr); BSTNode* p Search_BST(pTree-root, val); if (p nullptr) return false; //零分支直接释放 if (p-leftchild nullptr p-rightchild nullptr) { Delete_BST0(pTree, val); return true; } //双分支节点狸猫换太子 if (p-leftchild ! nullptr p-rightchild ! nullptr) { BSTNode* cat Get_NextNode(p); p-data cat-data; p cat; } //统一处理单分支/转换后的单分支节点 BSTNode* father p-parent; BSTNode* child p-leftchild ! nullptr ? p-leftchild : p-rightchild; if (father nullptr) pTree-root child; else { if (p-data father-data) { father-leftchild child; } else { father-rightchild child; } } delete p; p nullptr; return true; }六、总结1. 结构本质区别普通二叉树无数值约束仅限制节点度≤2BST强制全局有序、数值唯一左小右大是带排序规则的特殊二叉树。2. 遍历特性区别普通二叉树所有遍历无序BST独有中序升序特性可快速完成有序输出先 / 后序遍历不具备有序效果。3. 性能与工程选型理想平衡BST增删查为O(logn)斜树退化O(n)三叉链表适配高频删改、取前驱后继场景普通刷题、简单遍历优先用二叉链表减少指针维护 bug。对比维度普通二叉树二叉搜索树BST节点规则仅限制度≤2无数值大小约束左小右大、数值不重复、全局有序中序遍历序列无序严格升序标志性特征查找效率O(n)平衡 O (logn)、斜树 O (n)核心用途层级存储、遍历排序、检索、动态增删