【c++进阶系列】：万字详解二叉搜索树（附源码实现）

🔥 本文专栏：c++
🌸作者主页：努力努力再努力wz

在这里插入图片描述

💪 今日博客励志语录： 你可以走得慢，但别回头

1.概念

二叉搜索树，从其名字我们就能知道该数据结构是一个特殊的二叉树，而二叉搜索树这个数据结构的核心不是在于存储数据，而是在于高效的查找数据，那么如何高效的查找数据呢，那么就和二叉搜索树结构本身的性质有关：

左孩子节点的值小于根节点的值，右孩子节点的值大于根节点的值，并且对于其左右子树也递归的满足该性质

所以从二叉搜索树开始往后的数据结构的学习，那么我们就要更多接触到关联式容器而不是序列式容器，那么所谓的关联式容器，就是存储在容器中的数据之间是有联系的，比如这里的二叉搜索树中存储在节点中的值的关系是左小右大，也就是左子树中所有节点的值一定都是小于右子树中所有节点的值，而所谓序列式容器就是存储在容器中的元素彼此之间没有任何联系，那么序列式容器的代表就包括底层采取动态数组实现的vector以及底层采取带头双向循环链表实现的list

那么二叉搜索树之所以要满足这个性质，目的就是为了方便查找，接下来我将引入一个场景，来让读者认识到二叉搜索树的这个性质的意义：

假设现在有一个二叉搜索树，其节点中存储的数据的类型是整形，那么这里我们要查找该二叉搜索树中是否存在值为80的节点，那么此时要查找这个值，那么我们就要遍历这棵二叉树，而如果这里我采取的是传统的二叉树来存储数据，那么要查找该值是否存在，那么我就只能深度优先遍历，依次访问该二叉树中的所有的节点，而如果这里采取的是二叉搜索树来实现的话，那么这里我就可以利用二叉搜索树的性质，先从根节点往下遍历，遍历之前，我会先比较该值与根节点的大小，因为二叉搜索树的性质是左小右大，左孩子的值是小于根节点，右孩子的值是大于根节点，所以如果当前该值大于根节点，那么意味着我们接下来要去往右子树遍历，而如果小于根节点，那么意味着我们则要去往左子树往下遍历，而二叉树是一个递归的结构，每一个子树又可以视作看成由根节点和左子树和右子树三部分组成的二叉树，那么接下来就重复上面的步骤，继续比较根节点，确定遍历的分支，直到找到匹配值的节点或者遍历到空节点结束，而遍历到空节点意味着当前二叉搜索树中没有该值的节点存在

那么在回顾上面的过程，我们可以发现二叉搜索树能够实现高效查找的原因就是因为其左小右大的性质，那么我们每一次遍历都可以排除一个子树分支，那么相比于传统的二叉树的遍历，那么这里二叉搜索树能够极大的减少我们的搜索量，并且我们可以发现这个过程其实和我们的二分查找是一样的，二分查找的思想就是在一个有序序列中，将查找的目标值与中间位置的值相比较，如果大于就到右侧(假设为升序的有序序列），小于就到左侧，每次比较，都会将查找的范围给减半，所以二叉搜索树的查询的核心就是一个二分的思想，通过其结构本身的性质来实现

那么这里有的读者可能会疑惑，那么他知道这里二叉搜索树的优势不在于存储数据，而是在于查找数据，并且它理解到了二叉搜索树查找数据的核心思想就是二分，那么这里为什么不直接选取数组作为底层存储数据的容器，然后将数组中的元素排成有序，然后最后借助二分查找来实现元素的查找，这种方式也可以实现高效的查找，但是我们会发现很多关联式容器底层并没有采取这种方式，而是采取的是二叉搜索树，那么原因或者说二叉搜索树相比于刚才的这种实现方式的优点在哪里呢？

选择数组作为底层的容器，那么首先你得将数组中存储的所有元素给排序，那么如果采取的是快排来实现，那么快排的时间复杂度是o(N*logN)，而排序倒不是影响该实现方式的时间效率的主要因素，因为排序只用排一次，那么其付出的时间代价可以分摊到每一次的查找以及插入和删除操作当中去，而真正影响效率的其实是插入和删除操作
那么在插入和删除某个元素之前，那么你得首先找到插入以及删除的元素的位置，那么这个查找的时间代价就是o(logN)，也就是二分查找的时间复杂度，那么查找到元素的位置之后，那么接下来你要做的，就是插入以及删除元素，由于是数组，那么必然要涉及大量元素的挪动，那么这部分的时间代价则是O(N),所以插入以及删除总的时间代价是O(N+logN)

而对于二叉搜索树来说，那么其也有元素的插入以及删除操作，那么同样在删除之前，也得先找到目标元素在该二叉搜索树中的位置，而这里的查找的次数最多就是二叉树的高度次，所以很多读者会误认为这里的查找的时间复杂度是O(logN)，因为二叉树的高度是logN,但事实上这里的时间复杂度是O(N)，因为如果二叉树中存储的节点的值是一个单调递增或者递减的一个序列，那么在这种情况下，会使该二叉搜索树的结构成为一个类似于单链表的结构，那么其高度就是节点个数

而时间复杂度是估计最坏情况，所以这里的查找的时间复杂度应该是O(N),那么一旦查找到目标元素的位置，那么接下来由于二叉树的节点之间直接是通过指针来连接，那么这里的插入和删除只需要修改指针之间的链接关系即可，那么这部分的时间代价为O(1)，所以对于二叉搜索树来说，那么插入和删除的总代价就是O(N)，那么相比于上面的这种方式来说，综合来说还是二叉搜索树的效率更高

通过刚才的讲解，那么读者知道了，二叉搜索树的查找效率其实取决于二叉树的形态，那么我们更希望二叉树的形态是趋近于扁平的形态而不是一种高瘦的形态，所以后面我们还会学习AVL树以及红黑树，那么这两个数据结构就是在传统的二叉搜索树的基础上进行改善，来调整二叉搜索树的结构

介绍完了二叉搜索树的概念，那么接下来我们便要自己来尝试实现一个二叉搜索树，其中核心便是实现查找以及删除和插入这三个操作，那么在写代码实现之前，那么我们还是会先认识原理，然后再来动手实现

2.实现

那么由于二叉搜索树不一定是一棵完全二叉树，所以这里底层实现该二叉搜索树的时候，那么底层只能采取链式的二叉树来实现，除非像堆这样的特殊的二叉树，那么其结构一定满足是一棵完全二叉树，那么其采取的就是数组方式实现

那么既然是链式结构，那么这里我们就要首先先定义出二叉树的节点，那么该节点有两个指针域，分别指向其左右孩子，还包括一个数据域，那么这里我们可以定义成一个struct BinaryTreenode结构体，也可以将其定义为BinaryTreenode类，但要注意类里面的成员变量以及构造函数都得是public修饰，因为接下来我们要再定义一个BinarysearchTree类，里面会封装一个指向根节点的指针，那么我们会在该类的成员函数中比如insert插入函数以及remove删除函数，直接访问该节点的指向左右孩子节点的指针来遍历该二叉搜索树，以及修改节点之间的链接关系，需要在类外部直接访问到Binarytreenode类中的指针成员变量

那么你也完全可以将该BinaryTreenode类中的所有成员变量设置为私有，然后对类外部提供一个公有的接口来访问，而这里我们其实只需将BinarysearchTree类中将成员变量也就是指向根节点的指针以及将指向BinaryTreenode节点的指针类型的typedef的别名都设置为私有，那么你也不用担心类外部能够直接访问以及创建该节点，所以建议还是将节点类的中成员变量设置为公有

template<typename T>
class  BinaryTreeNode
{
public:BinaryTreeNode<T>* left;BinaryTreeNode<T> * right;T key;BinaryTreeNode(T _key=T()):left(nullptr), right(nullptr), key(_key){}
};
template<typename T>
class BinarysearchTree
{private:typedef BinaryTreeNode<T>* Node;Node root;
};

那么接下来就是完善binarysearchTree类中的成员函数了，那么首先就是我们的构造函数

构造函数

那么这里二叉搜索树的构造函数分为无参以及带参的，那么带参的就是开辟根节点并且给根节点一个初始值，而无参的构造函数就是开辟一棵空树

BinarysearchTree():root(nullptr)
{}
BinarysearchTree(T key)
{root = new BinaryTreeNode<T>(key);
}

search函数

那么这里search函数就是该查找该二叉搜索树中是否存在目标值的节点，如果存在，那么就返回true，不存在就返回false，那么search函数的实现有两种方式，分别是递归以及非递归，那么这里我们先讲解search函数的递归实现，那么由于我们知道二叉搜索树的性质是左小右大，那么这里我们先比较目标值与根节点的值，然后确定递归的子树，如果小于就递归到左子树，大于就递归到右子树然后再重复该步骤，而如果值匹配就直接返回true，而如果到达了空节点，那么则说明二叉搜索树没有该目标值，直接返回false，而递归版本的search函数要从根节点开始往下遍历，也就是需要传递一个指向根节点的指针，而指向根节点的指针是给BinarysearchTree类中的私有成员变量，那么为了避免在类外面需要传递指向根节点的指针给改成员函数，所以这里我定义了一个共有的searchR成员函数，然后内部调用私有的SearchR成员函数，然后将指向根节点的指针直接传递给SearchR成员函数，那么后面的递归版本的插入以及删除成员函数也会采取这种方式

bool searchR(const T&val)
{return SearchR(root, val);
}
bool SearchR(Node _root, const T& val)
{if (_root == nullptr){return false;}if (val < _root->key){return SearchR(_root->left, val);}else if (val > _root->key){return SearchR(_root->right, val);}else{return true;}
}

而非递归版本的思路和递归的思路是一样的，就是利用二叉搜索树的性质，每次与根节点比较，然后确定遍历的子树，只不过这里我们需要定义一个指针，然后用该指针来往下依次遍历

bool search(const T& val)
{Node cur = root;while (cur){if (val < cur->key){cur = cur->left;}else if (val > cur->key){cur =cur->right;}else{return true;}}return false;
}

insert函数

那么insert函数就是向二叉搜索树中插入一个目标值的节点，我们也可以采取使用非递归以及递归两种方式来实现，那么我们先来说非递归的实现原理，那么insert函数的实现思路其实我们可以分为两个步骤，第一步我们得确定插入的节点在二叉搜索树的位置，不能随意插入，因为要维护二叉搜索树的左小右大的性质，那么这里就需要我们找到其新插入节点的父节点，找到父节点之后，第二步就是在开辟一个新节点，然后让父节点的左指针或者右指针连接该节点即可

那么第一个步骤的原理和刚才讲的search函数是一样的，那么这里我们定义一个cur指针和parent，那么cur指针则用于遍历，那么它最开始指向根节点，然后从根节点往下遍历，那么往下遍历之前，那么都需要将目标值与cur指向当前的根节点的值比较，确定下一次遍历的分支是左分支还是右分支，那么确定好分支之后，那么在cur移动到左孩子节点或者右孩子节点之前，那么它会将值先赋值给parent，那么等cur指向空节点的时候，无法往下遍历，那么此时parent指向的节点就是新插入节点的父节点，而如果cur指向的值与目标值匹配，那么说明该二叉搜索树中已经存在了该目标值的节点，那么就没必要往下遍历以及执行后续的插入工作，直接return返回即可

Node parent = nullptr;
Node cur = root;
while (cur) {if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else {return;}..................
}

那么第一个步骤结束，parentz会指向新插入节点的父节点，那么下一步就是开辟一个新的节点，然后让父节点左指针或者右指针指向新开辟的节点从而将其连接进二叉搜索树，但是这里有一个问题，就是新插入的节点究竟应该是父节点的左指针指向该节点还是右指针，所以这里就需要判断，那么判断方式的是利用二叉搜索树的性质，我们直接将目标值与parent指向的父节点的值比较，小于就说明用左指针链接，其应该位于父节点的左子树中，大于就用父节点的右指针连接

判断完之后就开辟节点，然后连接即可

void insert(const T& val)
{if (root == nullptr){root = new BinaryTreeNode<T>(val);return;}Node parent = nullptr;Node cur =root;while (cur) {if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else {return;}}cur = new BinaryTreeNode<T>(val);if (val < parent->key){parent->left = cur;}else{parent->right = cur;}
}

那么递归版本实现思路还是那两个步骤，首先是找到新插入节点的父节点，然后再开辟新节点与父节点连接，那么第一个步骤其实可以复用search函数的递归实现的代码，那么这里关键是第二个步骤，也就是连接，那么这里递归版本的InsertR函数接收两个参数，分别是指向当前根节点的指针_root以及目标值val，假设该二叉搜索树没有该目标值的节点，那么当遍历到空节点位置的时候，那么由于二叉树的每一个节点只保存指向左右孩子的两个指针，没有指针指向父节点，那么要找到新插入节点的父节点，那么第一种方式是需要额外增加一个参数来保存 _root移动到左右孩子节点之前的值，但是采取这种方式，那么就和非递归的思路是一模一样了，还不如直接用非递归

InsertR(Node* _root,const T& val)if (val < _root->key){return InsertR(_root->left, val);}else if (val > _root->key){return InsertR(_root->right, val);}else{return;}
.....................
}

而第二种方式则是最为推荐也是最巧妙的，那么就是将这里InsertR函数的第一个参数，也就是指向根节点的指针改为引用，因为这里每一次往下递归的时候，我传递的实参都是当前根节点的指向左孩子或者右孩子的指针，那么这里 _root引用就是父节点的左右指针的别名，那么对引用的修改就等同于对父节点的左右指针本身的修改，那么这里意味着我们要连接，直接将新开辟的节点赋值给该引用即可，那么就等同于将给父节点的左右指针赋值，甚至不用判断应该连接到父节点的左分支还是右分支

void InsertR(Node& _root, const T& val)
{if (_root == nullptr){Node newnode = new BinaryTreeNode<T>(val);_root = newnode;return;}if (val < _root->key){return InsertR(_root->left, val);}else if (val > _root->key){return InsertR(_root->right, val);}else{return;}
}

remove函数

那么remove函数就是删除二叉搜索树中任意一个节点的函数，那么同样也分为递归版本和非递归版本，那么插入和查找这两个成员函数的实现还是较为容易，而真正有一点难度的则是删除函数

那么这里要注意二叉搜索树的删除不是像链表那样直接删除某个节点，然后将后继节点直接链接到删除节点的前驱节点，那么这里二叉搜索树的某个节点的删除，那么删完还要保证二叉搜索树整体的一个性质，那么这里我们可以将二叉搜索树的节点的删除分为三种情况，那么第一种情况就是删除的节点的左子树为空，第二种情况是删除的节点的右子树为空，那么第三种情况就是删除的节点的左右子树都不为空

其中第一种以及第二种情况我们都可以归为一种方式来处理，那么该方式便是托孤，所谓的托孤，就是将该节点删除之后，而该删除的节点之后的子树我们可以直接连接到其被删除节点的父节点的原有分支上，那么这里我举一个例子：

假设删除的节点a的左子树不为空，删除的节点a的父节点为b，并且节点a是节点b的左孩子，那么这里我们可以直接删除节点a并且将节点a的左子树直接连接到节点b的左分支上，那么这种方式就是托孤

托孤这个名字就很形象的体现了如何处理被删除节点的左子树或者右子树，那么直接将其交给其父节点，也就是连接到父节点，原本父节点指向被删除的节点的指针，将其修改来指向其非空子树

那么这里我们再来说一下为什么这里能够采取托孤的做法来删除该节点，那么我们知道删除的该节点包括其左子树或者右子树的所有节点一定是属于其删除节点的父节点的某个分支，如果属于左分支，那么该删除的该节点包括之后的左子树或者右子树的所有节点都小于删除节点的父节点，而如果属于右分支，那么则是都大于其删除节点的父节点，而删除的要求就是不能破坏二叉搜索树的左小右大的性质，那么我们将被删除节点的子树还是连接到原有的分支上，那么这里局部还是满足左大右小的性质，所以此时整个二叉搜索树整体的性质并不会破坏，所以这里能够采取这种托孤的方式

而有的读者在想问那么这里为什么不讨论叶子节点的删除，那么其实叶子节点就可以归为第一种或者第二种情况的特例，也就是左子树为空或者右子树为空，那么采取的方式一样是托孤，只不过这里托付给被删除节点的父节点的子树是空

左子树为空：

右子树为空：

但是一旦删除的节点的左右子树都不为空，那么此时处理的方式就不同，那么这里我们就不能像上面那样继续采取托孤，因为删除的父节点的左分支或者右分支只能接收一个子树而不能同时接收左子树和右子树，如果可以那就成三叉树了，而我们知道二叉树结构最大的特点就是其是一个递归的结构，那么整棵二叉树是由根节点以及左子树和右子树这三部分组成，而对于左子树和右子树，那么其同样也可以视作由这三部分组成，而对于二叉搜索树来说，那么其性质也是递归满足的，整体满足左小右大，并且再其左右子树也满足该性质

所以只要我们能够让二叉搜索树的每一个局部都满足该性质，那么自然整体就能满足该性质，那么该思想其实就是分治的思想，所谓的分治可以将一个原问题给分解为若干个更小规模的子问题，那么只要将局部的子问题给解决，那么子问题的解作为下一个更大规模的子问题的解，那么最终将规模扩大到整个问题，那么原问题的解就能得出

所以这里我们可以将这里的删除节点的左子树和右子树重新构建出一颗满足性质的局部的二叉搜索树，那么再将其连接到删除的节点的父节点当中，而被删除的节点包括其左右子树中的所有节点都属于被删除节点的父节点的左分支或者右分支，那么这里构建完一棵局部的二叉搜索树之后再连接到被删除节点的所处的原分支下，那么此时这里更大规模的局部二叉搜索树依然满足其左小右大的性质，而其他部分都满足该性质，那么自然整体就满足该性质

而这里构建局部二叉搜索树方方式就是找到左子树最大的或者右子树最小的节点 来替换被删除的父节点，之所以选择这两个节点的原因就是替换之后该局部二叉搜索树就符合左小右大的性质

那么左子树最大的节点就是位于整个左子树的最右侧的节点，而右子树的最小的节点就是位于整棵子树的最左侧，那么我们将左子树的中最右侧节点的值或者右子树最左侧节点的值与删除节点的值交换

那么这种方式类似于堆的删除根节点的处理方式，但是这里替换完之后，那么我们还要删除被替换后的左子树的最右侧节点或者右子树的最左侧节点，而这里注意左子树的最右侧的节点一定要么是叶子节点要么是一个右子树为空但左子树不为空的节点，如果其还有右子树，那么必然与其是最右侧节点相矛盾，右子树的最左侧节点也同理，其一定是叶子节点或者只有右子树非空的节点

所以这里要删除替换之后的左子树的最右侧节点或者右子树的最左侧节点，那么就可以按照第一种方式，也就是托孤的方式来删除

左右子树都不为空：

那么接下来在说如何用代码来具体实现了，首先是非递归版本的实现，那么这里第一个步骤还是找到被删除的节点以及删除节点的父节点，那么这部分代码的逻辑的实现我们可以定义两个指针变量parent和cur，那么cur用来往下遍历，而每一次cur指向左孩子或者右孩子之前，那么都会现将值赋给parent，那么一旦找到目标值，那么此时cur指向的就是被删除节点，而parent指向的就是其父节点

void remove(const T& val){
Node parent = nullptr;
Node cur =root;
while (cur)
{if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else{break;}
}if(cur==nullptr){return;}.............................
}

而找到删除的目标阶段，下一步便是判断此时删除节点的情况，是左子树为空还是右子树为空还是左右子树都不为空，而对于左子树为空，那么处理方式就是将其右子树连接到删除节点的父节点，但是这里还是要额外判断一下是连接到父节点的左侧还是右侧，那么可以比较一下删除节点的值与父节点的值来确定，而右子树为空，则是将左子树连接到删除节点的父节点，连接之前一样判断其是连接父节点的左侧还是右侧

if (cur->left == nullptr)
{if (cur == root){root = cur->right;delete cur;return;}else {if (cur->key < parent->key){parent->left = cur->right;}else if (cur->key > parent->key){parent->right = cur->right;}delete cur;return;}
}
else if (cur->right == nullptr)
{if (cur == root){root = cur->left;delete cur;return;}else {if (cur->key < parent->key){parent->left = cur->left;}else if (cur->key > parent->key){parent->right = cur->left;}delete cur;return;}
}

那么这里要注意如果这里是删除的整个二叉搜索树的根节点，那么这里进入while循环后会直接break退出，那么此时parent还是nullptr，所以这里我们如果我们不判断当前删除的节点是否是根节点，那么就会解引用空指针

而如果此时删除的节点左右子树不为空，那么就可以找左子树的最右侧节点或者右子树的最左侧节点，这里我是找左子树的最右侧节点，那么这里我定义了一个leftMax指针来遍历找到左子树的最右侧节点，而leftMaxParent则是记录其父节点，找到之后，左子树的最右侧节点再与删除的节点进行值的交换，最后在删除leftMax指向的节点，那么采取的方式就是托孤

Node leftMaxParent=cur;
Node leftMax = cur->left;
while (leftMax->right)
{leftMaxParent = leftMax;leftMax = leftMax->right;
}
std::swap(leftMax->key, cur->key);
if (leftMaxParent->key > leftMax->key)
{leftMaxParent->left = leftMax->left;
}
if (leftMaxParent->key < leftMax->key)
{leftMaxParent->right = leftMax->left;
}
delete leftMax

那么这里再来说一下递归实现，那么递归实现的第一个步骤还是找到删除的目标节点与其父节点，那么递归的方式想必读者现在已经很熟悉了：

void RemoveR(Node& _root,const T& val)
{if (_root == nullptr)
{return;
}
if (val < _root->key)
{return RemoveR(_root->left, val);
}
else if (val > _root->key)
{return RemoveR(_root->right, val);
}.......................
}

那么接下来就是判断删除节点的情况，那么这里注意由于我们将参数设置为了引用，那么我们每次调用该递归函数传递的参数都是节点的左指针或者右指针，那么该引用就是节点的左指针或者右指针的别名，那么我们对引用的各种行为就是对节点的左右指针本身进行修改，所以这里我们不需要判被删除的节点的子树是连接在其父节点的左侧还是右侧，那么直接赋值即可，并且对于根节点这里也不需要特判，如果删除的是根节点，那么引用直接就是指向根节点的指针的别名

if (_root->left == nullptr)
{Node cur = _root;_root = _root->right;delete cur;return;
}
if (_root->right == nullptr)
{Node cur = _root;_root = _root->left;delete cur;return;
}

而如果删除的节点的左右子树都存在，那么这里还是定义一个变量leftMAx用来记录左子树的最右侧节点，然后遍历左子树，找到到左子树的最右侧节点，然后再交换值，但是这里我的代码并没有选择交换，而是直接将左子树的最右侧节点的值赋值给删除的节点，由于我接下来要删除左子树的最右侧节点，而上文我们就分析过，那么该节点要么是叶子节点，要么只有其左子树不为空，那么这里我们可以直接复用RemoveR函数来删除该节点，所以不能破坏其左子树的左小右大的性质，所以这里我没有选择交换，但要注意这里再一次调用RemoveR函数时，传递给该函数的参数不能是leftMax，因为如果被删除节点的左子树只有一个节点，那么这里引用指向的是leftMax这个局部变量的别名，而不是删除节点的左指针的别名，所以无法修改指针的连接关系，这点要注意

Node leftMax = _root->left;
while (leftMax->right)
{leftMax = leftMax->right;
}
_root->key = leftMax->key;
RemoveR(_root->left, leftMax->key);

拷贝构造函数

那么拷贝构造函数这里我们就是采取前序遍历来依次拷贝目标对象中节点中的值，至于前序遍历拷贝的这部分内容，我专门将其定义到了copy函数中

BinarysearchTree(const BinarysearchTree& T)
{copy(root, T.head);
}
void copy(Node& l1, const Node& l2)
{if (l2 == nullptr){l1=nullptr;return;}l1=new BinaryTreeNode<T>;l1->key = l2->key;copy(l1->left, l2->left);copy(l1->right, l2->right);return;
}

赋值运算符重载函数

那么赋值运算符重载函数，因为实参传递给形参会先将值拷贝给形参，那么这里我们直接与形参的head成员变量的值交换，那么一旦函数调用结束，那么形参被销毁，而形参内的值是被交换后的值，所以这里可以采取这种方式巧妙的实现赋值运算符重载函数

	BinarysearchTree& operator=(BinarysearchTree T){std::swap(root, T.root);return *this;}

析构函数

那么由于这里二叉搜索树中的每一个节点都是在堆上申请的，所以这里我们需要释放每一个节点，那么我们释放的顺序就是采取后序遍历，然后先释放释放左子树中的所有节点，然后再释放右子树中的所有节点，最后再释放根节点

~BinarysearchTree()
{destroyTree(root);
}
void destroyTree(Node _root)
{if (_root == nullptr){return;}destroyTree(_root->left);destroyTree(_root->right);delete _root;
}

源码

BinarysearchTree.h

#pragma once
#include<algorithm>
#include<iostream>
using std::cout;
using std::endl;
template<typename T>
class  BinaryTreeNode
{
public:BinaryTreeNode<T>* left;BinaryTreeNode<T> * right;T key;BinaryTreeNode(T _key=T()):left(nullptr), right(nullptr), key(_key){}
};
template<typename T>
class BinarysearchTree
{
public:BinarysearchTree():root(nullptr){}BinarysearchTree(T key){root = new BinaryTreeNode<T>(key);}BinarysearchTree(const BinarysearchTree& t){copy(root, t.root);}~BinarysearchTree(){destroyTree(root);}BinarysearchTree& operator=(BinarysearchTree T){std::swap(root, T.root);return *this;}void insert(const T& val){if (root == nullptr){root = new BinaryTreeNode<T>(val);return;}Node parent = nullptr;Node cur = root;while (cur) {if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else {return;}}cur = new BinaryTreeNode<T>(val);if (val < parent->key){parent->left = cur;}else{parent->right = cur;}}bool search(const T& val){Node cur = root;while (cur){if (val < cur->key){cur = cur->left;}else if (val > cur->key){cur =cur->right;}else{return true;}}return false;}void remove(const T& val){Node parent = nullptr;Node cur = root;while (cur){if (val < cur->key){parent = cur;cur = cur->left;}else if (val > cur->key){parent = cur;cur = cur->right;}else{break;}}if (cur == nullptr){return;}if (cur->left == nullptr){if (cur == root){root = cur->right;delete cur;return;}else {if (cur->key < parent->key){parent->left = cur->right;}else if (cur->key > parent->key){parent->right = cur->right;}delete cur;return;}}else if (cur->right == nullptr){if (cur == root){root = cur->left;delete cur;return;}else {if (cur->key < parent->key){parent->left = cur->left;}else if (cur->key > parent->key){parent->right = cur->left;}delete cur;return;}}Node leftMaxParent=cur;Node leftMax = cur->left;while (leftMax->right){leftMaxParent = leftMax;leftMax = leftMax->right;}std::swap(cur->key,leftMax->key);if (leftMaxParent->key > leftMax->key){leftMaxParent->left = leftMax->left;}if (leftMaxParent->key < leftMax->key){leftMaxParent->right = leftMax->left;}delete leftMax;}bool searchR(const T&val){return SearchR(root, val);}void insertR(const T& val){InsertR(root, val);}void removeR(const T& val){RemoveR(root, val);}void Inorder(){InorderTree(root);}
private:typedef BinaryTreeNode<T>* Node;Node root;void copy(Node& l1, const Node& l2){if (l2 == nullptr){l1 = nullptr;return;}l1 = new BinaryTreeNode<T>;l1->key = l2->key;copy(l1->left, l2->left);copy(l1->right, l2->right);return;}void InsertR(Node& _root, const T& val){if (_root == nullptr){Node newnode = new BinaryTreeNode<T>(val);_root = newnode;return;}if (val < _root->key){return InsertR(_root->left, val);}else if (val > _root->key){return InsertR(_root->right, val);}else{return;}}void InorderTree(Node cur){if (cur == nullptr){return;}InorderTree(cur->left);cout << cur->key << " ";InorderTree(cur->right);}void RemoveR(Node& _root, const T& val){if (_root == nullptr){return;}if (val < _root->key){return RemoveR(_root->left, val);}else if (val > _root->key){return RemoveR(_root->right, val);}else{if (_root->left == nullptr){Node cur = _root;_root = _root->right;delete cur;return;}if (_root->right == nullptr){Node cur = _root;_root = _root->left;delete cur;return;}Node leftMax = _root->left;while (leftMax->right){leftMax = leftMax->right;}_root->key = leftMax->key;RemoveR(_root->left, leftMax->key);}}bool SearchR(Node _root, const T& val){if (_root == nullptr){return false;}if (val < _root->key){return SearchR(_root->left, val);}else if (val > _root->key){return SearchR(_root->right, val);}else{return true;}}void destroyTree(Node _root){if (_root == nullptr){return;}destroyTree(_root->left);destroyTree(_root->right);delete _root;}
};

main.cpp

#include"BinarysearchTree.h"
#include <iostream>
#include <cassert>
#include <string>using namespace std;void runTests() {// 1. 构造函数测试{// 默认构造函数BinarysearchTree<int> bst1;assert(bst1.search(1) == false);// 单元素构造函数BinarysearchTree<int> bst2(5);assert(bst2.search(5) == true);assert(bst2.search(1) == false);// 拷贝构造函数BinarysearchTree<int> bst3;bst3.insert(5);bst3.insert(3);bst3.insert(7);BinarysearchTree<int> bst4(bst3);assert(bst4.search(5) == true);assert(bst4.search(3) == true);assert(bst4.search(7) == true);assert(bst4.search(1) == false);cout << "Constructor tests passed!" << endl;}// 2. 赋值运算符测试{BinarysearchTree<int> bst1;bst1.insert(5);bst1.insert(3);bst1.insert(7);BinarysearchTree<int> bst2;bst2 = bst1;assert(bst2.search(5) == true);assert(bst2.search(3) == true);assert(bst2.search(7) == true);// 测试自我赋值bst2 = bst2;assert(bst2.search(5) == true);cout << "Assignment operator tests passed!" << endl;}// 3. 插入操作测试{// 插入空树BinarysearchTree<int> bst1;bst1.insert(5);assert(bst1.search(5) == true);// 插入多个元素BinarysearchTree<int> bst2;bst2.insert(5);bst2.insert(3);bst2.insert(7);bst2.insert(6);bst2.insert(8);assert(bst2.search(5) == true);assert(bst2.search(3) == true);assert(bst2.search(7) == true);assert(bst2.search(6) == true);assert(bst2.search(8) == true);assert(bst2.search(1) == false);// 重复插入BinarysearchTree<int> bst3;bst3.insert(5);bst3.insert(5);assert(bst3.search(5) == true);bst3.remove(5);assert(bst3.search(5) == false);cout << "Insert tests passed!" << endl;}// 4. 搜索操作测试{// 空树搜索BinarysearchTree<int> bst1;assert(bst1.search(5) == false);// 搜索存在的元素BinarysearchTree<int> bst2;bst2.insert(5);bst2.insert(3);bst2.insert(7);assert(bst2.search(5) == true);assert(bst2.search(3) == true);assert(bst2.search(7) == true);// 搜索不存在的元素assert(bst2.search(1) == false);assert(bst2.search(9) == false);cout << "Search tests passed!" << endl;}// 测试删除操作{// 从空树删除BinarysearchTree<int> bst1;bst1.remove(5);assert(bst1.search(5) == false);// 删除叶子节点BinarysearchTree<int> bst2;bst2.insert(5);bst2.insert(3);bst2.insert(7);bst2.remove(3);assert(bst2.search(3) == false);assert(bst2.search(5) == true);assert(bst2.search(7) == true);// 删除有一个子节点的节点BinarysearchTree<int> bst3;bst3.insert(5);bst3.insert(3);bst3.insert(2);bst3.insert(7);bst3.remove(3); // 有一个左孩子assert(bst3.search(3) == false);assert(bst3.search(2) == true);bst3.insert(8);bst3.remove(7); // 有一个右孩子assert(bst3.search(7) == false);assert(bst3.search(8) == true);// 删除有两个子节点的节点 - 修改后的测试BinarysearchTree<int> bst4;bst4.insert(5);bst4.insert(3);bst4.insert(7);bst4.insert(6);bst4.insert(8);// 验证树仍然包含其他节点assert(bst4.search(3) == true);assert(bst4.search(7) == true);assert(bst4.search(6) == true);assert(bst4.search(8) == true);// 删除根节点BinarysearchTree<int> bst5;bst5.insert(5);bst5.remove(5);assert(bst5.search(5) == false);bst5.insert(5);bst5.insert(3);bst5.remove(5);assert(bst5.search(5) == false);assert(bst5.search(3) == true);cout << "Remove tests passed!" << endl;}// 6. 递归操作测试{// 递归插入BinarysearchTree<int> bst1;bst1.insertR(5);bst1.insertR(3);bst1.insertR(7);bst1.insertR(6);bst1.insertR(8);assert(bst1.searchR(5) == true);assert(bst1.searchR(3) == true);assert(bst1.searchR(7) == true);assert(bst1.searchR(6) == true);assert(bst1.searchR(8) == true);assert(bst1.searchR(1) == false);// 递归删除BinarysearchTree<int> bst2;bst2.insert(5);bst2.insert(3);bst2.insert(7);bst2.insert(6);bst2.insert(8);bst2.removeR(5);assert(bst2.searchR(5) == false);assert(bst2.searchR(3) == true);assert(bst2.searchR(7) == true);assert(bst2.searchR(6) == true);assert(bst2.searchR(8) == true);// 递归搜索BinarysearchTree<int> bst3;bst3.insert(5);bst3.insert(3);bst3.insert(7);assert(bst3.searchR(5) == true);assert(bst3.searchR(3) == true);assert(bst3.searchR(7) == true);assert(bst3.searchR(1) == false);cout << "Recursive operation tests passed!" << endl;}{// 大型树测试BinarysearchTree<int> bst1;for (int i = 0; i < 1000; ++i) {bst1.insert(i);}for (int i = 0; i < 1000; ++i) {assert(bst1.search(i) == true);}for (int i = 0; i < 1000; i += 2) {bst1.remove(i);}for (int i = 0; i < 1000; ++i) {assert(bst1.search(i) == (i % 2 == 1));}// 字符串类型测试BinarysearchTree<string> bst2;bst2.insert("apple");bst2.insert("banana");bst2.insert("cherry");assert(bst2.search("apple") == true);assert(bst2.search("banana") == true);assert(bst2.search("cherry") == true);assert(bst2.search("date") == false);bst2.remove("banana");assert(bst2.search("banana") == false);cout << "Boundary tests passed!" << endl;}cout << "All tests passed successfully!" << endl;
}int main() {runTests();return 0;
}

运行截图：
在这里插入图片描述

应用

那么文章的最后，那么我就来谈论一下二叉搜索树的一个应用场景，那么二叉搜索树是一个key模型，那么一般是用于判断某个元素是否存在，所以二叉搜索树可以用作人脸识别，那么将其身份信息作为二叉搜索树的一个节点，而往后我们则还要学key-value模型，那么这里二叉搜索树存储的是一个元组，那么比较则是通过key值进行比较