引言：
北京时间：2023/5/2/9:18，五一放假第四天，昨天本来想要发奋图强将该篇博客写完，但是摆烂了一天，导致已经好几天没有码字，敲代码了，此时难受的感觉涌上心头，但是摆烂的时候确实是快乐的，所以快乐总是建立在痛苦之上这句话是非常的正确的，谁让我们生而为人呢？这就是生活嘛，快乐可以建立在当前痛苦之上，那是属于别人的痛苦，也可以建立在未来痛苦之上，透支时间的痛苦（反之亦成立），学习新知识的本质并不是痛苦的，痛苦的是开始学习的过程，比如现在的我，一想起昨天的摆烂，我就很痛苦，哈哈哈！但是好在我乐观并且稍稍有点自律，所以现在我们不管那么多，管它昨天学没学，今天学了就行，今天让我们一起走进搜索二叉树的世界吧！ 深入了解一下有关二叉树的知识，为我们以后学习红黑树这种高级数据结构打下一丢丢的基础吧！
搜索二叉树基础接口实现（循环）
此时我们正式进入搜索二叉树的学习，从以前的知识，此时我们知道二叉树结构是一个非线性结构的数据结构，并且明白二叉树是不适合用来存储数据的（相比于用顺序表和链表），但是我们又非学不可，因为树状结构是一个非常优秀的数据结构（以红黑树为例），例：假如让我们学完链表相关知识直接去学习红黑树，那么此时就等于让一个小学生去参加高考，考是肯定可以考的，只是结果显而易见，所以我们需要更多时间去学习相关基础知识，所以有初中和高中需要依次度过，否则结局一定悲惨，所以无论是今天我们学习的搜索二叉树还是以前学习的二叉树，本质都是在向红黑树这棵珠穆朗玛峰挺近而已，并且明白，虽然二叉树不适用于存储数据，但是像二叉树这样的树状结构是具有非常优先的效率优势（时间复杂度低），所以此时我们就可以利用这个优势，构造出非存储功能的数据结构，例如：搜索二叉树、AVL树、红黑树……
所以今天我们就接着以前学习过的有关优先级队列的知识，来学习一下第二个带有特性的数据结构（不单单只是简单的用于存储数据）：搜索二叉树
并且此时通过以前学习过的知识，无论是初阶数据结构中的顺序表、链表、栈、队列、二叉树，还是之后学习C++中STL库时的vector，string，list，priority_queue，deque，此 时我们都应该明白，对于一类数据结构来说最重要的就是 插入、删除、查找 ，所以让我们带着这三大不败天王的名号，来看看它们在搜索二叉树中是如何实现的吧！
构建结点和基础模板
在实现搜索二叉树的插入、删除、查找之前，此时我们先来搞定数据结构的一个经典问题，数据存储和结点创建问题，这个问题无论是在链表还是二叉树中，都是一个容易让人混乱的问题，所以这里我们再强调一遍：如下
数据存储使用堆区不使用栈区究极理解
由于栈区的生命周期会被限制在当前函数的执行期间，当函数执行完毕时，该函数中定义的变量和函数参数所占用的内存空间将会随着栈帧的销毁而销毁，此外，栈区的内存空间是有限的，并且由于分配和释放栈内存的速度非常快速，所以导致栈上的空间是无法动态地调整大小，因此，如果需要动态地分配大量的内存空间，或者需要在函数之外访问已经分配的内存空间，则不能使用栈而必须使用堆区或全局存储区。
总的来说，虽然数据可以存储在栈上，但是由于其生命周期的限制和内存空间的限制，常见的数据结构和动态分配内存等需要使用堆区来存储。
把上述问题搞清晰了之后，此时我们就正式开始搜索二叉树的学习
搜索二叉树结点构建如下图所示：
学过二叉树都知道，二叉树的正常结点就是一个左指针指向左子树，一个右指针指向右子树，最后带一个数值key，并且注意，学习了C++之后，为了可以更好的使用该结点，一般都会对该结构体添加一个构造函数，但此时要 注意，struct的使用和class的使用，当时在学习类和对象的时候，由于没有特殊的场景，对于该知识点的理解并不是很到位，并且随着时间的推移，此时类似这样的细节就很容易忘记，导致使用上出现错误，具体原因：由于struct不存在类域，所以此时该结构体默认是一个公共结构体，谁都可以直接使用，但class不一样，此时它是存在类域的，如果你不标明访问限定符，那么此时该结构体默认是私有，不允许被外部接口使用，所以必须指明 public 的访问限定符，此时该结点结构体才可以被搜索树直接调用，具体如下图所示：
总：类和对象的知识总是在无形中影响着我们编码，这也许就是细节和不细节的区别吧！So，我们一定要当一个细节的男人，懂得都懂！
搞定了这个小知识点，此时我们搜索二叉树的结点就构建出来啦！但是单单构建出来是没有用的，此时还需要有数据进行初始化，并且真真正正的将对应的数据存在起来（真实存在，随时可以访问），此时想要实现这个目的，用屁股想我都知道，肯定需要实现插入接口，具体如下文所述，new（在堆区创建结点）就留到插入接口中学习。
搜索二叉树插入接口实现
同理，通过以前的知识，我们都知道，想要实现一个数据结构，最重要的接口就是如何向这个数据结构中插入数据，所以无论是从那个角度理解，插入接在任何一个数据结构中都是最重要的存在，并且此时要注意的是，插入接口虽然具有得天独厚的重要地位，但在搜索二叉树中从代码实现难度去理解，插入接口并不是最重要的，删除接口才是最重要的，所以插入接口我们不详细讲解，具体如下图所示：
搜索二叉树查找接口实现
搞定了上述的插入接口，明白，当大量的数据利用上述接口被插入时，此时这些数据并不是单纯的只需要插入就完成任务了，如上文所说，树状结构并不适用于存储数据，单单存储数据直接使用vector和list之流就行了，何必这么麻烦的搞这个什么搜索二叉树，搞得你头痛，我也头痛，目的只是为了利用该数据结构的搜索特性，也就是遍历效率高（特殊情况暂时忽略，谁让我们还没那个实力搞红黑树），所以谈到搜索，此时肯定就需要我们实现一个查找接口，注：同理，删除接口的代码难度才是重点，查找接口不详解，如下图所示：
搜索二叉树删除接口实现
多的不说少的不唠，行文到现在，一直都在强调搜索树中删除接口是最重要的，代码实现是最复杂的（相对而言），所以屁话不多说，直接开造……
删除的前提是显而易见的，首先要让该搜索二叉树中存在数据，所以此时我们需要先调用上述的插入接口向该搜索二叉树中插入对应的数据（const），如下代表此时我们需要插入的数据：
按照上述a数组中的数据插入到搜索二叉树中，此时根据插入代码原理，可以得到如下图所示的搜索二叉树：
此时我们就在此搜索二叉树的基础上展开学习搜索二叉树删除接口的实现，并且此时要明白，从初阶数据结构过渡之后，高阶数据结构不再是普普通通的一种场景就能解决的，例如此时的搜索二叉树，它一个接口的代码量不再像顺序表、链表那样，而是需要解决更加复杂的场景问题，从一个一个场景的判断，解决可能存在的所有问题，进而将一个适用于所有搜索二叉树的删除接口编写出来，所以越往后学习，插入、查找、删除这些接口代码本质都没有太大的变化（结构大致相同），需要搞定的只是各种场景的问题，一个接口通过条件判断（if）语句进行一个场景一个场景的编码，所以结构越复杂，需要控制的场景越多，此时编码就越繁琐，代码就越长，结构就越稳定，实现起来就越难，学习成本就越高，记忆下来就越难（以红黑树为例），所以在目前的我看来（我也不知道红黑树具体如何实现）红黑树的实现，就是在规定条件下，将所有可能存在的场景通过if语句给控制住而已（通过搜索二叉树实现给我的感觉）
脑海中有了上述概念，首先不管它在红黑树理论上对不对，反正在搜索树上肯定是对的，所以此时我们只需要在删除接口中将几个特殊的场景给控制住就行，如下图所示：
上述是比较正规的删除接口理论实现原理，但是理论永远是理论，只是让入门学习搜索树的时候更快理解具体原理，但是此时的我们，对搜索二叉树不敢说全部搞懂，但反正不是入门，肯定有自己的一点独到见解，所以当我们编写代码的时候，删除接口可以总结成三个场景：托孤场景，请保姆场景、究极场景
托孤场景：
托孤场景理论理解就是上述情况a，b，c，因为该场景上述三个场景都适用，字面意思理解，托孤托孤意思就表示将自己的孩子结点托付给别人，详解：当我们要删除一个根结点的时候，如果此时这个根结点有且仅有一个孩子结点，那么此时就需要把这个孩子结点交给该根结点的父结点管理，当然，如果该根结点没有孩子结点（也就是叶子结点），那此时按照该原理，也就是默认将nullptr（空）交给该结点的父结点管理，同理，该根结点被删除之后，该父结点管理的也是空，所以叶子结点同样适用托孤场景， 具体代码如下图所示：
唯一注意点： 不要疑问为什么根结点的父结点可以直接链接根结点的孩子结点，而不要比较大小，如果大就链接在父结点的右边，小就链接到父结点的左边（如果有这个想法，说明没有很好的吃透插入接口），此时根据插入结构代码，如果一个数据想要插入到父结点的右边，那么此时这个数据一定比父结点大，也就是说明，只要数据是在父结点的右边（左边亦成立），那么此时这个数据就一定比父结点大，所以在托孤的时候，根本不需要判断key值，只需要判断被删除结点是在父结点的左边还是右边就可以了，是左边就让父结点的左边直接链接，是右边就让父结点的右边直接链接（插入原理得到）
请保姆场景：
请保姆场景理论上理解就是上图情况d，字面理解就是去寻找一个结点来代替被删除结点，因为当我们将上述场景搞定，此时一棵树中的结点就剩下那种同时具有两个孩子结点的根结点的情况，所以此时只需要把最后这种情况搞定，那么所有搜索树的任意结点删除，我们就搞定了，具体如下图代码所示：
注意：保姆结点一般是左子树的最大结点或者是右子树的最小结点，也就是左子树最右结点或者右子树最左结点
究极场景：
搞定了上述知识，删除接口90%我们都搞定了，此时只需要把这个究极场景搞定，那么搜索二叉树的基础实现我们就搞定了，然后再把搜索二叉树的递归实现和现实生活中的应用场景看一看，搜索二叉树我们就算学完啦！究极场景详解如下图所示：
ok，行文来到这里，删除接口就完全搞定了，也就是表明搜索二叉树循环基础实现也已经都搞定了，接下来，就让我们再深入研究一下搜索二叉树，该篇博客就结束啦！
搜索二叉树的时间复杂度
正常情况下是O（log2N），但是有特殊情况，就是搜索树的左子树和右子树极度不平衡或者极度对称的情况下，如下图所示：
此时就会导致该搜索二叉树的时间复杂度变成O（N），所以此时为了避免这种情况的发生，就需要对代码进行优化，进而控制左右子树，让它们尽量保持在平衡范围，这个知识也就是我们之后将要学习的AVL树和红黑树的有关知识，该篇博客不做深入讲解
搜索二叉树现实生活应用
此时分为两种场景：
1.key模型 （在不在场景？）
门禁系统（通过校园卡上的信息和学校数据库里的信息进行匹配，判断在不在就行）
车库系统（同理，略有不同，可以通过条件判断来区分停放车辆是否需要按时收费）
检查一篇文章中单词拼写是否正确（将词库中所有的英文单词插入到一棵搜索二叉树中，然后通过遍历该搜索二叉树进行判断是否包含文章中的单词，包含则视为正确，不包含则视为错误），此时借助的就是搜索二叉树的搜索能力很强，时间复杂度O（log2N）
2.key/value模型 （通过一个东西寻找另一个东西场景？）
中英文互译字典
通过电话号码查询快递信息
通过电话号码获取到验证码，进而进行的一系列使用
统计水果出现的次数
样例代码实现：
英汉互译
水果出现的次数
搜索二叉树完整代码和注释详解（循环实现）
#include<iostream> #include<cassert> #include<stdio.h> using namespace std; //什么是搜索二叉树，不就是很多的函数接口实现和一个结点结构体吗？ //本质就是把结构体搞出来（数据，左节点，右节点而已） //结构体搞出来之后，就是利用这个结点去实现搜索二叉树而已 template<class K> struct BinarySearchTreeNode//这个表示的意思是结构体，二叉树专用结构体 { BinarySearchTreeNode<K>* _left; BinarySearchTreeNode<K>* _right; K _key; BinarySearchTreeNode(const K& key)//学了C++之后，这种结点一定要配套一个构造函数使用 :_left(nullptr),_right(nullptr),_key(key) {} }; template<class K> class BinarySearchTree//这个表示的是一个类，C++为了进行封装实现的类，如果使用C语言，就可以不需要这个类，但是上面那个结构体类是必须要存在 { typedef BinarySearchTreeNode<K> Node;//这个就是属于继承里面组合的知识，将不同的类组合在一起使用，所以此时就可以对这个类进行一定的重定义 public: BinarySearchTree()//每个类都必须有的构造函数而已 :_root(nullptr) {} bool Insert(const K& key) { if (_root == nullptr)//如果此时根结点为空，也就是表示此时这棵树是空树，此时数据插入位置就是根的位置 { _root = new Node(key);//小小的一个定位new而已，想要存储数据就一定要在堆区上搞，所以结点单单只是有结构体不行，还要自己new一个，不然存不了数据 return true;//表示插入成功 } Node* parent = nullptr;//用于记录当前位置的前一个位置 Node* cur = _root; while (cur != nullptr)//这个条件成立表示的是这棵树中有数据 { if (cur->_key > key) { parent = cur;//此时这个位置不要多想，正常的把指针的地址给给另一个指针就行，只要把该指针的地址给给了它，此时依然可以找打指针指向的地址 cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { return false; } } //这个循环结束，此时表示的就是我们已经找到了那个可以插入数据的位置，简简单单再来一个定位new就行(但是此时这个想法是错误的) //cur = new Node(key);//典型的内存泄露，并且没有将这个结点链接到二叉树中，哈哈哈 //return true; //所以此时就要把该结点的父结点也给找到，不然链接不上去 cur = new Node(key); //找到父结点之后，开始链接 if (parent->_key < key)//这个判断条件的前提是，此时cur已经找到了合适的结点位置，只需要判断是链接在根结点的左边还是右边就行 { parent->_right = cur; } else { parent->_left = cur; } return true; } bool Find(const K& key) { Node* cur = _root; while (cur != nullptr) { 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) { // 8 // 3 10 // 1 6 14 // 7 13 //删除在这块算是有难度的，删除的场景非常的多，删除叶子结点是比较容易的，但是删除跟结点就比较不一样了 //如果想要删除6或者是14，那么此时因为根结点只有一个孩子，想要删这个根结点，只要把这个单独的孩子结点交给根结点的根结点（3，10）领养就行 //但是如果此时你想要删除3或者8，那么按照上述的托孤已经不行了，现在就需要直接按照请保姆的方法去删除(此时这个保姆就是左子树的最大结点，或者是右子树的最小结点) //并且注意：此时左子树的最大结点就是最右结点，右子树的最小结点就是最左结点 Node* parent = nullptr;//此时这个parent初始化是空指针（nullptr），此时就一定要小心，可能会有的场景下，循环进不去，导致parent一直都是空指针，然后又使用它 Node* cur = _root; while (cur != nullptr) { if (cur->_key < key)//cur不为空的前提下，就让cur去迭代 { parent = cur; cur = cur->_right; } else if (cur->_key > key)//cur不为空的前提下，就让cur去迭代 { parent = cur; cur = cur->_left; } else { //此时一定要明白这个else条件是干嘛的，此时这个else条件表示的就是找到了我要删除的数据，因为上述迭代的是大和小，如果都不满足，此时当然表示的就是等于，等于，那么此时该值我们就需要删除 //然后下述就是删除时的各个场景（注意：此时的cur就是我要删除的数据） //删除场景1：托孤+叶子结点 // 8 // 3 10 // 1 6 14 // 4 7 16 //此时删除4/7/16位置就是搜索二叉树的最简单删除场景，叶子结点，找到直接删就行 + 托孤场景 //此时托孤场景就类似于删除14这个根结点（想要删除14就一定要把16进行收养） //什么是收养：收养就是类似于插入数据的写法，只不过此时是把该结点交给被删除结点的父节点收养，所以代码编写的时候就要像插入数据一样，把父节点的位置给记录下来 if (cur->_left == nullptr)//满足这个条件表示此时该根结点就只有一个孩子结点，此时这个孩子结点收养起来没那么复杂 { if (cur == _root)//也就是注意根没有parent的情景 { _root = _root->_right;//更新更结点 } else { if (parent->_left == cur)//这个条件用于判断谁被删除，就接收的是谁的孩子 { parent->_left = cur->_right;//此时这个场景实现就是一个经典的托孤场景 } else { parent->_right = cur->_right; } } delete cur;//叶子结点也同样适用，因为叶子结点的本质是两个孩子结点都为空，并且托孤场景由于该结点被删除之后本来就是空，所以依然置空是没有问题的 } // 8 //此时一来就删除8，并且此时8的右边一来就是空（终极场景） // 3 // 1 6 // 4 7 // 此时如果是上述这个场景，那么就一定需要更新_root(也就是直接让左子树成为独立的一棵树)，当然也可以是当右子树全为空的时候，去左子树找一个保姆，同理，左子树全为空的时候，去右子树找一个保姆 else if (cur->_right == nullptr)//结合上图，可以看出，上述两个迭代找等于都没有进去（因为我一来就是8，就找到了），所以导致parent并没有被赋值，还是nullptr，所以此时代码来到这里，就等于是对nullptr进行使用，代码出问题 { if (cur == _root) { _root = _root->_left;//更新根结点 } else { if (parent->_left == cur)//删谁领养谁的孩子 { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } //以上代码直接就可以搞定托孤根结点和叶子结点，但是此时搜索二叉树还有一个最麻烦的场景，就是删除不止一个孩子结点的根结点 // 8 // 3 10 // 1 6 14 // 4 7 16 // 13 //例如：此时想要删除10或者8 //所以搜索二叉树删除代码的第二个场景就是请保姆场景，此时如果把这种不止一个孩子结点的根结点删除，就会导致整棵树报废 //因为搜索二叉树的本质就是要满足左结点小于根结点，右结点大于根结点的规则 //所以此时如果想要删除就不只是单单的收养剩余结点的事情了，因为不是孤儿结点根本收养不明白，也不可以直接重新链接（效率太低） //所以此时就只可以找人替代被删除结点（合适的值） //所以这也就是删除的第二个场景请保姆场景，具体如下： else//此时这个else的条件一定要很清楚（就是我们要删除的结点不是叶子结点也不是只有一个孩子结点的根结点，而是有两个孩子结点的根结点） { //删除场景2：请保姆(左子树的最大结点就是最右结点，右子树的最小结点就是最左结点) //两个结点选一个进行替换，此时下述代码表示我们选的是右子树的最左结点 //Node* pminRight = nullptr;//因为我们要替换的是cur位置，所以此时该结点就不能乱给，需要把cur位置给给它，这样才可以实现替换 Node* pminRight = cur;//此时因为要删除的就是cur位置，所以cur位置是不可以乱动的（由上述遍历已经找到），所以此时就需要有替死鬼去帮cur移动，所以pminRight直接从cur开始就行 Node* minRight = cur->_right; while (minRight->_left != nullptr)//找右子树的最小结点（也就是右子树最左结点） {// 也就是找最左结点 pminRight = minRight;//此时这个位置的pminRight如果给nullptr，此时要防止该循环进入不了的情况，如果进入不了该循环，就会导致pminRight出现很严重的问题 minRight = minRight->_left; } // 代码走到这个位置，也就是跳出循环之后，表示的就是找到了右子树的最小结点（也就是找到了可以替换被删除结点的保姆结点） // 找到之后，把这个值赋值到被删除结点就行（也就是完成请保姆这个步骤） cur->_key = minRight->_key;//因为cur的位置就是我要删除的位置，并且位置并没有发生改变，所以直接赋值就行，此时的这个赋值就是等于删除，由于会覆盖数据，所以此时就可以把想要删除的结点使用覆盖的方法删除掉了 // *************************************** // 究极场景（被删除结点的右结点没有左结点） // *************************************** // //该场景会导致该结点直接被替换为保姆结点 // 此时来到搜索二叉树的第三个场景，基于第二场景发现的问题（无法进入上述循环问题），也就是被删除结点的下一个结点没有左孩子结点，直接被当成保姆问题 // 也就是上述循环的一个场景问题 // 8 // 3 10 // 1 6 14 // 13 // 如上图，此时如果我们想要删除的是8（直接用13去覆盖），那么此时就会导致minRight->_left一来就是nullptr，直接导致循环进不去，间接证明如果pminRight给nullptr是不合理的 // 但是主要是想说明：此时直接导致找不到右子树的最左结点13（此时13已经失效），所以此时就导致10直接就是cur位置，就是直接就用10去覆盖8 // 用10去覆盖8，也就导致，如果想要重新链接后面的数据，此时一定是链接在minRight右边，因为此时右子树的最左结点已经失去作用了 // 本质还是因为搜索二叉树的特性，就是左结点一定要比根结点小，右结点一定要比根结点大（不允许相等） // 所以此时如果把这个保姆结点替换到被删除结点之后，该保姆结点也一定需要删除掉 // 所以同理想要删除该保姆结点，就会遇到问题，就是该保姆结点会有孩子结点 // 所以此时一定要进行收养代码的编写，如下： // 但是由于该保姆结点是右子树的最左结点，此时就不存在有两个以上的孩子结点需要收养（最多只是有一个右孩子结点） // 所以此时该场景就又只是一个托孤场景或者叶子结点场景而已 // pminRight->_left = minRight->_right;//但是注意不能单单只考虑一种场景（测试用例），直接把孤儿结点就给给父节点的左结点 //所以此时编码如下： if (pminRight->_left == minRight)//此时这个代码是通过上述的究极场景得出的，所以要结合上述场景来看（删除8的时候） { pminRight->_left = minRight->_right;//此时注意，这个写法是因为已经不可能有左孩子了，所以只能是收养该左结点的右孩子结点，因为此时该结点已经是我们要找的最左结点 } else//此时的这个else条件表示的就是pminRight->_right==minRight;具体就是因为上述删除8的场景，此时10作为根结点之后，就是在右结点收养14这个叶子结点（所以并不一定每次都是左节点接收数据），删8的这个究极场景就是右结点接收数据 { pminRight->_right = minRight->_right;//这个场景此时需要画一个图出来，不然不好搞 } delete minRight;//最后将保姆结点删除就行 } return true; } } return false; } //下面这个接口只是一个递归打印的接口而已 void InOrder()//这种写法，可以很好的避免传私有对象的问题 { _InOrder(_root); } void _InOrder(Node* root)//这个位置不要傻傻的以为给一个缺省值可以，因为缺省值必须是一个全局变量或者常量，这边给一个_root当缺省值是无效的 { if (root == nullptr) { return; } _InOrder(root->_left);//要明白，这个是一个中序打印，先左子树然后根结点，最后右子树（直接就可以实现排序） cout << root->_key << " ";//一个简简单单的递归打印，不敢不会，多写就行（并且要知道，这个搜索二叉树想要直接排序只要按照中序遍历就行了），原理就是搜索二叉树的原理 _InOrder(root->_right);//所以最终明白，一个搜索二叉树只要按照中序去遍历，此时该搜索二叉树就是有序的 } private: Node* _root = nullptr;//一棵树最重要的部分，根结点（给了缺省值初始化的，也可以不给，但是要写构造函数，因为非内置类型不会默认生成构造函数） }; void Treetest1() { int arr[] = { 8,3,1,10,6,4,7,14,13 }; BinarySearchTree<int> tree; for (auto e : arr) { tree.Insert(e);//注意:如果直接使用中序遍历搜索二叉树，可以直接将该搜索二叉树排序完成 } //tree.InOrder(GetRoor());//这种写法非常的恶心，所以场景一，一般写成递归形式的代码，我们都套一层子代码，这样可以很好的解决这个问题 tree.InOrder();//这种写法一定要多练 cout << endl; tree.Erase(8); tree.InOrder(); cout << endl; tree.Erase(3); tree.InOrder(); cout << endl; tree.Erase(10); tree.InOrder(); cout << endl; tree.Erase(14); tree.InOrder(); cout << endl; for (auto e : arr) { tree.Erase(e); tree.InOrder(); cout << endl; } tree.InOrder(); cout << endl; } #include<iostream> using namespace std; int main() { //测试代码 Treetest1(); return 0; } //明白最重要的一点，就是构建搜索二叉树的本质就是为了方便搜索，并不是存储数据，如果单单只是存储数据，用vector和list就行了
搞定了上述的知识，此时我们一起看一看如何使用递归的方法实现搜索二叉树，代码如下所示：
搜索二叉树完整代码和注释详解（递归实现）
#include<iostream> #include<cassert> #include<stdio.h> using namespace std; template<class K> struct BinarySearchTreeNode { BinarySearchTreeNode<K>* _left; BinarySearchTreeNode<K>* _right; K _key; BinarySearchTreeNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) {} }; //搜索二叉树的递归版本 template<class K> class BinarySearchTree { typedef BinarySearchTreeNode<K> Node; public: BinarySearchTree() :_root(nullptr) {} //此时明白一个比较重要的点：在类中写递归一般都套一层（套一个子函数），目的：方便使用类对象（直接为空就无法进行递归） //并且注意：此时使用类中的函数，存在this指针，这个this指针是不需要进行递归的，所以如果包含一个子函数是非常好的 bool InsertR(const K& key) { return _InsertR(_root, key); } bool _InsertR(Node*& root, const K& key)//因为使用了引用，所以此时的root和parent（循环写法）一样，都是真实存在在堆区上的，所以不管是root->_left，还是root->_right，它们都是真实存在在堆区的 { if (root == nullptr)//只能找空位置插入数据（因为使用的是递归写法，所以root一直都在更新），所以一定可以在对应的地方找到对应的空位置 { //这个位置的代码就是该插入代码的经典地方（涉及到如何将父结点和新插入的结点链接到一起） //第一种解决方法：将父结点的位置获取到 //第二种解决方法：判断父结点的下一个位置是否为空 //最好的方法：如下 root = new Node(key);//但是注意，此时这种写法一定要使用引用传参（因为使用引用就可以直接帮我们将该结点和对应的父结点链接） return true; //因为此时root参数不再是形参，而是一个真正的root，所以root->_right,此时表示的就是对应插入数据的位置 } //如果没有使用引用，root起的是迭代寻找对应插入位置的作用，如果使用的引用，那么此时起的是直接链接数据的作用 if (root->_key < key)//往右树插入 { return _InsertR(root->_right, key);//注意：此时使用了引用，所以这个结点就是对应搜索树的结点 } else if (root->_key > key)//往左树插入 { return _InsertR(root->_left, key);//使用了引用，可以直接进行结点的链接（不需要像循环写法那样通过parent判断，因为此时的root和parent一样，都是真实存在在堆区上的，所以不管是root->_left，还是root->_right，它们都是真实存在在堆区的） } else { return false; } } bool FindR(const K& key) { return _FindR(_root, key); } bool _FindR(Node* root, const K* key) { if (root == nullptr)//此时像什么删除和查找的时候，如果该树都没有数据，就不需要删除和查找，所以直接返回就行 { return false; } if (root->_key == key)//递归停止的条件 { return true;//此时代码写到这里，我就想起来，要注意if语句是以分号结尾，所以有没有括号不是重点，主要是有没有分号 } if (root->_key < key)//此时表示我们可以直接递归右子树 { return _FindR(root->_right, key); } else { return _FindR(root->_left, key); } } bool EraseR(const K& key) { return _EraseR(_root, key);//经典的外包子函数写法（可以直接使用类对象进行传参，省了从外部获取类对象，然后又传过来的步骤） } bool _EraseR(Node*& root, const K& key)//删除数据的时候一定要传引用删除，不能会导致删不掉，因为形参不会改变实参，所以除了查找这一类方法，别的方法大部分都需要优先考虑是否需要使用引用 {//递归一定要使用引用，因为它是递归（会一直展开，一直传参，如果不使用引用，传的就一直是形参，最终导致删不掉） if (root == nullptr) { return false;//两个意思，一个是一进来，这棵树就是空，一个是递归到了空都没有找到对应的结点，也就是该树没有该结点 } if (root->_key > key) { return _EraseR(root->_left, key); } else if (root->_key < key) { return _EraseR(root->_right, key); } else {//此时代码如果走到这里，表示的就是找到对应要删除的数据了，也就是等于key的时候 //但是要注意：找到归找到，但是想要删，那么就有很多的场景需要考虑（和循环写法类似） Node* delenode = root;//注意：按照下面这个写法，此时root被新的数据覆盖了，所以就不可以继续删root了，所以原来的root需要保存一下，不然会导致内存泄露问题 if (root->_left == nullptr) { root = root->_right;//这个写法又是一个经典的覆盖数据写法（使用覆盖数据的写法来同时实现收养和删除），本质原因还是因为使用引用传参 } else if (root->_right == nullptr) { root = root->_left;//覆盖删除法在有的地方真的很好用（特别是这种递归传引用写法），但是要注意内存泄露问题（先保存再覆盖就行） } //总：上述条件判断的就是叶子结点和托孤的写法，并且明白：托孤写法无论是该覆盖写法还是循环的父节点写法，都可以正常收养，不需要判断key值大小问题（因为要符合插入时的规则，能够插入，此时这个值就一定可以被收养） //注意：能够被插入就一定能够被收养（只需要判断收养的是左边还是右边就行，具体通过cur来判断就行） //第三种场景：请保姆，场景如下 // 8 // 3 10 // 1 6 14 // 7 13 // 6.5 // 此时要删除8，找左子树的最大结点（7）去替换，代码如下：（就是注意此时是递归写法和传引用） else {//此时明白，这个场景就是被删除结点有两个子结点的情况 Node* maxleft = root->_left;//同理，去找左子树的最大结点或者是右子树的最小结点进行请保姆替换方法 while (maxleft->_right != nullptr) { maxleft = maxleft->_right; } //代码来到这里，表示的就是找到了左子树的最大结点 //此时的场景也就是需要用7（maxleft）去覆盖8（要删除根结点），然后顺便把7也删除掉（防止内存泄露）但注意：此时就又涉及到上上述场景，也就是托孤和叶子结点（6.5） //root->_key = maxleft->_key; std::swap(root->_key , maxleft->_key); //将保姆结点完成替换之后（具体为什么用交换不用赋值原因：如下图） // 交换 7 赋值 7 // 3 10 3 10 // 1 6 14 1 6 14 // 8 13 7 13 // 6.5 6.5 //此时就需要把替换结点删除（也就是保姆结点） //删除方法两种： //1.保留父结点，托孤后删除（参考循环写法） //2.如下，再递归删除法 //return _EraseR(root->_left, maxleft->_key); return _EraseR(root->_left, key);//目的：删除替换结点，转换成直接去左子树中删除，因为此时我们找的保姆是左子树的最大结点，所以一定是去左子树中递归删除保姆结点 //return _EraseR(maxleft, key);//这个写法千万不可以有，因为此时的maxleft是一个我们自己定义的局部变量，它的存储位置是在栈帧上，区别于root->_left，它是真正存在于堆区上的，并且明白堆区上的数据使用传引用是非常合理的（因为它的改变并不会直接影响堆上的数据（因为给给引用的是栈帧上指向堆区的那个指针），所以进行迭代找保姆的时候并不会被修改，而是正常向后走），但是栈帧上的数据使用传引用就不合理（因为此时传过去的就是maxleft在栈帧上的地址，如果拿这个地址去迭代找保姆，那么此时这个根结点是会被直接覆盖掉的（修改），而不是迭代向后走） }//但是要明白，此时这个被删除的值是多少，如果使用直接赋值的方式，那么就不能使用key值，要使用maxleft->_key值，如果是使用交换，那么此时你就可以直接传key值 // 正常情况走完这个递归，此时该树如下图所示： // 交换 7 赋值 7 // 3 10 3 10 // 1 6 14 1 6 14 // 6.5 6.5 delete delenode;//注意：真正的删除对应位置数据是通过数据覆盖的方法，这个删除只是防止内存泄露而已 return true; } } void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } private: Node* _root = nullptr; }; void test1() { BinarySearchTree<int> tree; int arr[] = { 8,3,1,10,6,4,7,14,13 }; for (auto e : arr) { tree.InsertR(e); } tree.InOrder(); tree.EraseR(8); tree.InOrder(); tree.EraseR(10); tree.InOrder(); for (auto e : arr) { tree.EraseR(e); tree.InOrder(); } } int main() { test1(); }
key/value模型完整代码如下所示：
namespace key_value//key/val模型的搜索树 { template<class K, class V> struct BinarySearchTreeNode//注意：此时这边如果使用struct，此时就不需要设置访问限定符（默认公有），如果使用class就需要设置访问限定符（默认私有） { BinarySearchTreeNode<K, V>* _left; BinarySearchTreeNode<K, V>* _right; K _key; V _value; BinarySearchTreeNode(const K& key, const V& value) :_left(nullptr), _right(nullptr), _key(key), _value(value) {} }; //key/val模型写法 template<class K, class V> class BinarySearchTree { typedef BinarySearchTreeNode<K, V> Node; public: BinarySearchTree() :_root(nullptr) {} BinarySearchTree(const BinarySearchTree<K, V>& tree) { _root = DeepCopy(tree._root); } BinarySearchTree<K, V>& operator=(const BinarySearchTree<K, V> tree) { swap(_root, tree._root); return *this; } ~BinarySearchTree() { Destroy(_root); _root = nullptr; } Node* DeepCopy(Node* root) { if (root == nullptr) { return nullptr; } Node* newroot = new Node(root->_key); newroot->_left = DeepCopy(root->_left); newroot->_right = DeepCopy(root->_right); return newroot; } void Destroy(Node* root) { if (root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; } 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 != nullptr) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } 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 != nullptr) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return cur;//此时返回找打的那个key值结点，再利用这个结点去访问对应的value值 } } return nullptr; } bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur != nullptr) { 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 = _root->_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 = _root->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } else { Node* pminRight = cur; Node* minRight = cur->_right; while (minRight->_left != nullptr) { pminRight = minRight; minRight = minRight->_left; } cur->_key = minRight->_key; if (pminRight->_left == minRight) { pminRight->_left = minRight->_right; } else { pminRight->_right = minRight->_right; } delete minRight; } return true; } } return false; } void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } //统计水果写法 void InOrder1() { _InOrder1(_root); cout << endl; } void _InOrder1(Node* root) { if (root == nullptr) { return; } _InOrder1(root->_left); cout << root->_key << ": " << root->_value << endl; _InOrder1(root->_right); } private: Node* _root = nullptr; }; }
从上代码可以看出，key模型和key/value模型本质上没有很大的区别，但是使用上有一定的区别，这里不多做讲解
