一.二叉搜索树的概念二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:若它的左子树不为空则左⼦树上所有结点的值都小于等于根结点的值若它的右子树不为空则右⼦树上所有结点的值都大于等于根结点的值它的左右子树也分别为⼆叉搜索树⼆叉搜索树中可以⽀持插⼊相等的值也可以不⽀持插⼊相等的值具体看使⽤场景定义后续我们学习map/set/multimap/multiset系列容器底层就是⼆叉搜索树其中map/set不⽀持插⼊相等值multimap/multiset⽀持插⼊相等值举例子图示如下代码实现如下struct BSTNode { K _key; // 存储的键值 BSTNodeK* _left; // 左子树指针 BSTNodeK* _right; // 右子树指针 BSTNode(const K key) // 构造函数 :_key(key) // 初始化 _key , _left(nullptrptr) , _right(nullptrptr) {} };二.二叉搜索树的性能分析最优情况下⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)其⾼度为 log2 N最差情况下⼆叉搜索树退化为单⽀树(或者类似单⽀)其⾼度为 N所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为 O(N)那么这样的效率显然是⽆法满⾜我们需求的我们后续内容需要继续讲解⼆叉搜索树的变形平衡叉搜索树AVL树和红⿊树才能适⽤于我们在内存中存储和搜索数据。另外需要说明的是⼆分查找也可以实现 O(log2 N) 级别的查找效率但是⼆分查找有两⼤缺陷1. 需要存储在⽀持下标随机访问的结构中并且有序。2. 插⼊和删除数据效率很低因为存储在下标随机访问的结构中插⼊和删除数据⼀般需要挪动数据这⾥也就体现出了平衡⼆叉搜索树的价值。三.二叉搜索树的插入插⼊的具体过程如下1. 树为空则直接新增结点赋值给root指针2. 树不空按⼆叉搜索树性质插⼊值⽐当前结点⼤往右⾛插⼊值⽐当前结点⼩往左⾛找到空位置插⼊新结点。3.如果⽀持插⼊相等的值插⼊值跟当前结点相等的值可以往右⾛也可以往左⾛找到空位置插⼊新结点。要注意的是要保持逻辑⼀致性插⼊相等的值不要⼀会往右⾛⼀会往左⾛先提供一个数组int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};插入这个16的过程就是比8大往右同理后续一直到成为14的右子树插入这个13的过程就是比8小往左和三一样左右都可以比6小往左再小往左同理后续一直到成为4的左子树bool Insert(const K key) { if (_root nullptr) { _root new Node(key); 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; } } cur new Node(key); if (parent-_key key) { parent-_right cur; } else { parent-_left cur; } return true; }四.⼆叉搜索树的查找1. 从根开始⽐较查找xx⽐根的值⼤则往右边⾛查找x⽐根值⼩则往左边⾛查找。2. 最多查找⾼度次⾛到到空还没找到这个值不存在。3. 如果不⽀持插⼊相等的值找到x即可返回4. 如果⽀持插⼊相等的值意味着有多个x存在⼀般要求查找中序的第⼀个x。如下图查找3要找到1的右孩⼦的那个3返回bool 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 true; } } return false; }五.二叉搜索树的删除⾸先查找元素是否在⼆叉搜索树中如果不存在则返回false。如果查找元素存在则分以下四种情况分别处理假设要删除的结点为N1. 要删除结点N左右孩⼦均为空2. 要删除的结点N左孩⼦位空右孩⼦结点不为空3. 要删除的结点N右孩⼦位空左孩⼦结点不为空4. 要删除的结点N左右孩⼦结点均不为空对应以上四种情况的解决⽅案1. 把N结点的⽗亲对应孩⼦指针指向空直接删除N结点情况1可以当成2或者3处理效果是⼀样的2. 把N结点的⽗亲对应孩⼦指针指向N的右孩⼦直接删除N结点3. 把N结点的⽗亲对应孩⼦指针指向N的左孩⼦直接删除N结点4. ⽆法直接删除N结点因为N的两个孩⼦⽆处安放只能⽤替换法删除。找N左⼦树的值最⼤结点R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N因为这两个结点中任意⼀个放到N的位置都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换转⽽变成删除R结点R结点符合情况2或情况3可以直接删除。图示如下a.情况1删除1左为空 - cur-_left nullptr// 删除 1叶子节点左为空 if (cur-_left nullptr) // 1的左孩子为空 { if (cur _root) // 1不是根节点 { _root cur-_right; } else // 进入这里 { if (parent-_left cur) // 3的左孩子是1 { parent-_left cur-_right; // 3的左孩子 1的右孩子(nullptr) } else { parent-_right cur-_right; } } delete cur; // 释放节点1的内存 }大致过程cur 1, parent 31 是 3 的左孩子所以parent-_left cur-_right (nullptr)最后再delete cur。b.情况2删除10左为空 - cur-_left nullptr// 删除 10左为空右有14 if (cur-_left nullptr) // 10的左孩子为空 { if (cur _root) // 10不是根节点 { _root cur-_right; } else // 进入这里 { if (parent-_left cur) // 13的左孩子是10 { parent-_left cur-_right; // 13的左孩子 10的右孩子(14) } else { parent-_right cur-_right; } } delete cur; // 释放节点10的内存 }大致过程1.cur 10, parent 132.10 是 13 的左孩子3.parent-_left cur-_right (14)4.最后再delete cur.//情况3删除14右为空 - 左有孩子 else if (cur-_right nullptr) // 14的右孩子为空 { if (cur _root) // 14不是根节点 { _root cur-_left; } else // 进入这里 { if (parent-_left cur) // 13的左孩子是14? { parent-_left cur-_left; } else // 13的右孩子是14为rue进入这里 { parent-_right cur-_left; // 13的右孩子 14的左孩子(10) } } delete cur; // 释放节点14的内存 }大致过程1.cur 3, replaceParent 3, replace 42.while (replace-_left) 不执行4的左孩子为空3.cur-_key replace-_key (3变成4)4.replaceParent-_right replace-_right (nullptr)5.delete replace (删除原节点4)。情况4删除3左右都不为空 - 找右子树最左节点// 删除 8左右都不为空右子树最左节点是10 else // 左右都不为空就进入这里 { // 找右子树的最左节点中序后继 // 右子树最左节点就是比cur大的所有节点中最小的那个 Node* replaceParent cur; // replaceParent 3 Node* replace cur-_right; // replace 43的右孩子 while (replace-_left) // 4的左孩子为空那么循环不执行 { replaceParent replace; replace replace-_left; } // 用replace的key覆盖cur的key3变成4 cur-_key replace-_key; // 注意key_value版本还应该复制_value这里代码没做有bug // 处理replace的右子树用replace的右孩子顶替replace if (replaceParent-_left replace) { replaceParent-_left replace-_right; } else { replaceParent-_right replace-_right; // 3的右孩子 4的右孩子(nullptr) } delete replace; // 释放原节点4 }大致过程1.cur 8, replaceParent 8, replace 132.while (replace-_left) 执行replaceParent 13, replace 1010的左孩子为空退出循环3.cur-_key replace-_key (8变成10)4.replaceParent-_left replace-_right (13的左孩子指向nullptr)5.delete replace (删除原节点10)完整 Erase 函数代码bool Erase(const K key) { 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 { // 删除 // 左为空 if (cur-_left nullptr) { if (cur _root) { _root cur-_right; } else { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; } else if (cur-_right nullptr) { if (cur _root) { _root cur-_left; } else { if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; } else { // 左右都不为空 // 右子树最左节点 Node* replaceParent cur; Node* replace cur-_right; while (replace-_left) { replaceParent replace; replace replace-_left; } cur-_key replace-_key; if (replaceParent-_left replace) replaceParent-_left replace-_right; else replaceParent-_right replace-_right; delete replace; } return true; } } return false; }六.二叉搜索树的实现代码#pragma once #includeiostream using namespace std; namespace key { templateclass K struct BSTNode { K _key; BSTNodeK* _left; BSTNodeK* _right; BSTNode(const K key) :_key(key) , _left(nullptr) , _right(nullptr) { } }; // Binary Search Tree // Key templateclass K class BSTree { //typedef BSTNodeK Node; using Node BSTNodeK; public: bool Insert(const K key) { if (_root nullptr) { _root new Node(key); 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; } } cur new Node(key); if (parent-_key key) { parent-_right cur; } else { parent-_left cur; } return true; } bool 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 true; } } return false; } bool Erase(const K key) { 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 { // 删除 // 左为空 if (cur-_left nullptr) { if (cur _root) { _root cur-_right; } else { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; } else if (cur-_right nullptr) { if (cur _root) { _root cur-_left; } else { // 右为空 if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; } else { // 左右都不为空 // 右子树最左节点 Node* replaceParent cur; Node* replace cur-_right; while (replace-_left) { replaceParent replace; replace replace-_left; } cur-_key replace-_key; if (replaceParent-_left replace) replaceParent-_left replace-_right; else replaceParent-_right replace-_right; delete replace; } return true; } } return false; } void InOrder() { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_key ; _InOrder(root-_right); } private: Node* _root nullptr; }; }//test.cpp #define _CRT_SECURE_NO_WARNINGS 1 #includeBinarySearch.h int main() { key::BSTreeint t; int a[] { 8, 3, 1, 10, 1, 6, 4, 7, 14, 13 }; // 插入数据 printf(插入数据: ); for (auto e : a) { if (t.Insert(e)) printf(%d , e); } printf(\n当前树: ); t.InOrder(); // 插入16和3 printf(\n插入16: %s\n, t.Insert(16) ? 成功 : 失败); printf(插入3: %s\n, t.Insert(3) ? 成功 : 失败(已存在)); printf(当前树: ); t.InOrder(); // 删除3 printf(\n删除3: %s\n, t.Erase(3) ? 成功 : 失败); printf(当前树: ); t.InOrder(); // 删除8 printf(\n删除8: %s\n, t.Erase(8) ? 成功 : 失败); printf(当前树: ); t.InOrder(); // 循环删除所有 printf(\n循环删除:\n); for (auto e : a) { if (t.Erase(e)) printf(删除%d成功 当前树: , e); else printf(删除%d失败 当前树: , e); t.InOrder(); } return 0; }运行结果如下七.⼆叉搜索树key和key/value使⽤场景1. key搜索场景只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查但是不⽀持修改修改key破坏搜索树结构了。场景1⼩区⽆⼈值守⻋库⼩区⻋库买了⻋位的业主⻋才能进⼩区那么物业会把买了⻋位的业主的⻋牌号录⼊后台系统⻋辆进⼊时扫描⻋牌在不在系统中在则抬杆不在则提⽰⾮本⼩区⻋辆⽆法进⼊。场景2检查⼀篇英⽂⽂章单词拼写是否正确将词库中所有单词放⼊⼆叉搜索树读取⽂章中的单词查找是否在⼆叉搜索树中不在则波浪线标红提⽰。2.key/value搜索场景每⼀个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value增/删/查还是以key为关键字⾛⼆叉搜索树的规则进⾏⽐较可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改但是不⽀持修改key修改key破坏搜索树性质了可以修改value。场景1简单中英互译字典树的结构中(结点)存储key(英⽂)和vlaue(中⽂)搜索时输⼊英⽂则同时查找到了英⽂对应的中⽂。场景2商场⽆⼈值守⻋库⼊⼝进场时扫描⻋牌记录⻋牌和⼊场时间出⼝离场时扫描⻋牌查找⼊场时间⽤当前时间-⼊场时间计算出停⻋时⻓计算出停⻋费⽤缴费后抬杆⻋辆离场。场景3统计⼀篇⽂章中单词出现的次数读取⼀个单词查找单词是否存在不存在这个说明第⼀次出现单词1单词存在则单词对应的次数。3.key/value⼆叉搜索树代码实现简单实现一个英译汉字典的demo//BinarySearch.h #pragma once #includeiostream using namespace std; namespace key_value { templateclass K, class V struct BSTNode { K _key; V _value; BSTNodeK, V* _left; BSTNodeK, V* _right; BSTNode(const K key, const V value) :_key(key) , _value(value) , _left(nullptr) , _right(nullptr) {} }; // Binary Search Tree // Key/value templateclass K, class V class BSTree { //typedef BSTNodeK Node; using Node BSTNodeK, V; public: // 强制生成构造 BSTree() default; BSTree(const BSTree t) { _root Copy(t._root); } BSTree operator(BSTree tmp) { swap(_root, tmp._root); return *this; } ~BSTree() { Destroy(_root); _root nullptr; } 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; } } cur new Node(key, value); if (parent-_key key) { parent-_right cur; } else { parent-_left cur; } return true; } 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; } } return nullptr; } bool Erase(const K key) { 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 { // 删除 // 左为空 if (cur-_left nullptr) { if (cur _root) { _root cur-_right; } else { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; } else if (cur-_right nullptr) { if (cur _root) { _root cur-_left; } else { // 右为空 if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; } else { // 左右都不为空 // 右子树最左节点 Node* replaceParent cur; Node* replace cur-_right; while (replace-_left) { replaceParent replace; replace replace-_left; } cur-_key replace-_key; if (replaceParent-_left replace) replaceParent-_left replace-_right; else replaceParent-_right replace-_right; delete replace; } return true; } } return false; } void InOrder() { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_key : root-_value endl; _InOrder(root-_right); } void Destroy(Node* root) { if (root nullptr) return; Destroy(root-_left); Destroy(root-_right); delete root; } Node* Copy(Node* root) { if (root nullptr) return nullptr; Node* newRoot new Node(root-_key, root-_value); newRoot-_left Copy(root-_left); newRoot-_right Copy(root-_right); return newRoot; } private: Node* _root nullptr; }; }//test.cpp #define _CRT_SECURE_NO_WARNINGS 1 #include BinarySearch.h int main() { key_value::BSTreestring, string dict; //BSTreestring, string copy dict; dict.Insert(left, 左边); dict.Insert(right, 右边); dict.Insert(insert, 插入); dict.Insert(string, 字符串); string str; while (cin str) { auto ret dict.Find(str); if (ret) { cout - ret-_value endl; } else { cout 无此单词请重新输入 endl; } } return 0; }运行结果