教师个人网站建设请打开网站

教师个人网站建设,请打开网站,郑州做网站多少钱,衡阳做网站ss0734一. 二叉搜索树的核心概念#xff1a;什么是 BST#xff1f; 二叉搜索树又称二叉排序树#xff0c;它要么是空树#xff0c;要么是满足以下值分布规则的二叉树#xff1a; 若左子树不为空#xff0c;则左子树中所有节点的值 ≤ 根节点的值#xff1b;若右子树不为空什么是 BST二叉搜索树又称二叉排序树它要么是空树要么是满足以下值分布规则的二叉树若左子树不为空则左子树中所有节点的值 ≤ 根节点的值若右子树不为空则右子树中所有节点的值 ≥ 根节点的值左、右子树也分别是二叉搜索树递归定义。二叉搜索树可以支持插入相等的值也可以不支持插入相等的值具体看使用场景定义后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树其中map/set不支持插入相等值,multimap/multiset支持插入相等值关键特性中序遍历为有序序列二叉搜索树的核心价值在于“中序遍历结果是升序序列”。例如下图 BST 的中序遍历结果为1 3 4 6 7 8 10 13 14天然具备 “排序” 属性这也是其 “二叉排序树” 名称的由来。关于 “相等值” 的约定BST 对相等值的处理可灵活定义具体取决于场景不支持相等值插入如map/set底层插入时若值已存在直接返回失败支持相等值插入如multimap/multiset底层相等值需统一插入左子树或右子树保持逻辑一致避免后续查找混乱。本文实现的BST默认不支持相等值插入。二. 二叉搜索树的性能分析理想与最差情况BST 的操作效率直接取决于树的 “高度”而高度由节点插入顺序决定存在两种极端情况场景树的形态高度增删查时间复杂度典型插入顺序核心影响因素理想情况完全二叉树接近平衡log2​NO(log2​N)随机插入如8,3,10,1,6插入顺序无序节点均匀分布在左右子树最差情况单支树退化为链表NO(N)有序插入如1,3,6,8,10插入顺序严格递增/递减节点仅向单侧延伸综合来看二叉搜索树增删查改时间复杂度与 “二分查找” 的对比二分查找虽也能实现O(log₂N)的查找效率但存在明显缺陷依赖支持随机访问的结构如数组且需提前排序插入 / 删除效率低数组中插入 / 删除元素需挪动大量数据时间复杂度为O(N)。而 BST 无需提前排序且插入 / 删除时仅需修改节点指针避免了数据挪动这也是其在动态数据场景中更具优势的原因。三. 二叉搜索树的实战实现基于 BinarySearchTree.h采用 C 模板实现支持泛型K核心包含节点结构定义与BST 类的三大操作插入、查找、删除同时提供中序遍历接口验证有序性。3.1 节点结构定义BSTreeNodeBST 的节点需存储 “值” 与 “左右子树指针”模板化设计使其可适配 int、string 等多种类型#includeiostream using namespace std; templateclass K struct BSTreeNode { BSTreeNodeK* _left; // 左子树指针 BSTreeNodeK* _right; // 右子树指针 K _key; // 节点键值 // 构造函数初始化指针为空键值为传入值 BSTreeNode(const K key) : _left(nullptr) , _right(nullptr) , _key(key) {} };3.2 BST 类核心操作Insert、Find、EraseBST 类封装了树的根节点_root并通过私有辅助函数_InOrder实现中序遍历。以下是三大核心操作的详细实现与解析3.2.1 插入操作Insert插入的核心逻辑是 “按 BST 规则找到空位置创建新节点并链接”步骤如下若树为空_root nullptr直接创建根节点树非空时用cur指针遍历树若cur-_key 插入值向右子树移动cur cur-_right若cur-_key 插入值向左子树移动cur cur-_left若值相等不支持插入返回false找到空位置后通过parent指针记录cur的父节点将新节点链接到树中。代码实现BinarySearchTree.htemplateclass K class BSTree { typedef BSTreeNodeK Node; public: bool Insert(const K key) { // 情况1树为空直接创建根节点 if (_root nullptr) { _root new Node(key); return true; } // 情况2树非空遍历找插入位置 Node* parent nullptr; // 记录cur的父节点用于后续链接新节点 Node* cur _root; while (cur) { if (cur-_key key) { parent cur; cur cur-_right; // 比当前节点大向右走 } else if (cur-_key key) { parent cur; cur cur-_left; // 比当前节点小向左走 } else { // 键值已存在不支持插入返回false return false; } } // 创建新节点并链接到parent的左/右孩子 cur new Node(key); if (parent-_key key) { parent-_right cur; // 插入值比parent大作为右孩子 } else { parent-_left cur; // 插入值比parent小作为左孩子 } return true; } // 中序遍历验证BST的有序性 void InOrder() { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); // 遍历左子树 cout root-_key ; // 访问当前节点 _InOrder(root-_right); // 遍历右子树 } Node* _root nullptr; // 树的根节点初始为空 };3.2.2 查找操作Find查找的逻辑与插入类似按 BST 规则遍历树步骤如下从根节点_root开始用cur指针遍历若cur-_key 目标值向右走若cur-_key 目标值向左走找到目标值返回true遍历到空节点未找到返回false。代码实现BinarySearchTree.hbool Find(const K key) { Node* cur _root; while (cur) { if (cur-_key key) { cur cur-_right; // 目标值大向右找 } else if (cur-_key key) { cur cur-_left; // 目标值小向左找 } else { // 找到目标值返回true return true; } } // 遍历到空未找到 return false; }如果支持插入相等的值意味着有多个x存在一般要求查找中序的第⼀个x。如下图查找3要找到1的右孩子的那个3返回3.2.3 删除操作Erase最复杂的核心操作删除的难点在于 “删除节点后需保持 BST 的规则不变”。根据删除节点记为cur的子节点数量分为 4 种情况其中前 3 种可合并处理第 4 种需用 “替换法” 删除情况子节点状态处理方案关键注意事项1左右子树均为空叶子节点直接删除cur节点将parent指向cur的孩子指针置空可归为情况2或3统一处理需判断cur是否为根节点若为根直接将_root置空无需处理parent2左子树为空右子树非空将parent指向cur的孩子指针修改为指向cur-_right随后删除cur节点若cur是根节点直接让_root cur-_right跳过parent判断3右子树为空左子树非空将parent指向cur的孩子指针修改为指向cur-_left随后删除cur节点与情况2对称根节点处理逻辑为_root cur-_left4左右子树均非空1. 找cur右子树的“最小节点”最左节点或左子树的“最大节点”最右节点2. 将替换节点的键值及值若为key-value模型赋给cur3. 删除替换节点替换节点满足情况2或3直接处理替换节点的父节点指针需正确修改如替换节点是父节点左孩子需将父节点左指针指向替换节点的右子树代码实现BinarySearchTree.hbool Erase(const K key) { Node* parent nullptr; Node* cur _root; // 第一步找到要删除的节点cur while (cur) { if (cur-_key key) { parent cur; cur cur-_right; } else if (cur-_key key) { parent cur; cur cur-_left; } else { // 第二步找到节点按子节点情况处理删除 // 情况2左子树为空右子树非空 if (cur-_left nullptr) { // 若cur是根节点直接让根指向右子树 if (cur _root) { _root cur-_right; } else { // 判断cur是parent的左/右孩子链接对应子树 if (cur parent-_left) parent-_left cur-_right; else parent-_right cur-_right; } delete cur; // 释放节点内存 return true; } // 情况3右子树为空左子树非空 else if (cur-_right nullptr) { if (cur _root) { _root cur-_left; } else { if (cur parent-_left) parent-_left cur-_left; else parent-_right cur-_left; } delete cur; return true; } // 情况4左右子树均非空替换法删除 else { // 找cur右子树的最小节点最左节点作为替换节点 // 还可以找左子树的最大节点(最右节点) // 这里是找右子树最左节点 Node* replaceParent cur; // 替换节点的父节点 Node* replace cur-_right; while (replace-_left) // 一直向左走直到左子树为空 { replaceParent replace; replace replace-_left; } // 替换将replace的键值赋给cur值替换指针不变 cur-_key replace-_key; // 删除replace节点replace的左子树为空符合情况2 if (replaceParent-_left replace) replaceParent-_left replace-_right; else replaceParent-_right replace-_right; delete replace; return true; } } } // 未找到要删除的节点 return false; }关键说明情况 4 中选择 “右子树最小节点” 作为替换节点是因为该节点的值是cur右子树中最小的替换后仍满足 BST 规则左子树≤根≤右子树同理选择 “左子树最大节点” 也可逻辑对称四. 实战测试基于实战代码验证 BST 操作test.cpp通过引入BinarySearchTree.h实现 BST 的插入、删除与中序遍历验证代码如下#includeBinarySearchTree.h int main() { // 测试数据插入序列 int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; BSTreeint t; // 1. 插入所有元素 for (auto e : a) { t.Insert(e); } cout 插入后中序遍历应有序; t.InOrder(); // 输出1 3 4 6 7 8 10 13 14 // 2. 删除测试逐步删除节点验证有序性 t.Erase(3); // 删除左子树非空、右子树非空的节点情况4 cout 删除3后中序遍历; t.InOrder(); // 输出1 4 6 7 8 10 13 14 t.Erase(8); // 删除根节点左右子树非空情况4 cout 删除8后中序遍历; t.InOrder(); // 输出1 4 6 7 10 13 14 t.Erase(1); // 删除叶子节点左右子树为空情况1 cout 删除1后中序遍历; t.InOrder(); // 输出4 6 7 10 13 14 t.Erase(10); // 删除右子树非空、左子树非空的节点情况4 cout 删除10后中序遍历; t.InOrder(); // 输出4 6 7 13 14 // 3. 清空树删除所有元素 for (auto e : a) { t.Erase(e); } cout 清空后中序遍历空行; t.InOrder(); // 输出空行 return 0; }结果符合预期证明 BST 的插入、删除操作均保持了“中序遍历有序”的核心特性。五. BST 的扩展key/value 模型支持映射场景上述实现是 “key 模型”仅存储键值用于判断 “存在性”不能修改但实际场景中常需 “key-value 模型”键值对应数据如字典、统计次数,可以修改valueBinarySearchTree.h可扩展为模板templateclass K, class V节点同时存储_key和_value。5.1 key-value 模型节点与类实现// key-value模型节点 templateclass K, class V struct BSTreeNode { K _key; V _value; BSTreeNodeK, V* _left; BSTreeNodeK, V* _right; BSTreeNode(const K key, const V value) : _key(key) , _value(value) , _left(nullptr) , _right(nullptr) {} }; // key-value模型BST类 templateclass K, class V class BSTree { typedef BSTreeNodeK, V Node; public: // 插入需传入key和value bool Insert(const K key, const V value) { if (_root nullptr) { _root new Node(key, value); return true; } Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_key key) { parent cur; cur cur-_right; } else if (cur-_key key) { parent cur; cur cur-_left; } else { return false; // 不支持重复key } } cur new Node(key, value); if (parent-_key key) parent-_right cur; else parent-_left cur; return true; } // 查找返回节点指针可通过节点访问value Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_key key) cur cur-_right; else if (cur-_key key) cur cur-_left; else return cur; // 返回节点后续可操作value } return nullptr; } //erase跟上面没区别这里就不展示了 // 中序遍历输出key和value void InOrder() { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout root-_key : root-_value ; _InOrder(root-_right); } Node* _root nullptr; };5.2 key-value 模型实战场景场景 1简单字典中英互译int main() { //简单字典 key_value::BSTreestring, string dict; dict.Insert(sort, 排序); dict.Insert(string, 字符串); dict.Insert(insert, 插入); dict.Insert(erase, 删除); dict.Insert(move, 移动); dict.Insert(tree, 树); dict.Insert(tree, 树*****);//插入失败可以看看插入的逻辑主要是key判断 // 内置类型转换成类类型 - 构造函数 // 类类型转换成内置类型 - operator 内置类型 string str; int i 0; //while ((cin str).operator bool()) while(cinstr) { auto* node dict.Find(str); if (node) { cout - node-_value endl; } else { cout 无此单词请重新输入 endl; } } return 0; }场景 2单词统计统计水果出现次数int main() { string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 }; key_value::BSTreestring, int CountTree; for (auto str : arr) { //BSTreeNodestring, int* ret countTree.Find(str); auto ret CountTree.Find(str); // 第一次出现插入水果, 1 if (ret nullptr) { CountTree.Insert(str, 1); } else { // 已出现次数1 ret-_value; } } // 中序遍历按水果名称升序输出次数 CountTree.InOrder(); return 0; }