【c++篇】：二叉搜索树--有序存储与高效查找的关键
✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客
文章目录
- 前言
- 一.二叉搜索树的概念和性质
- 二.模拟实现
- 基本框架
- 中序遍历
- 查找函数
- 插入函数
- 删除函数
- 默认成员函数
- 测试
- 三.完整代码
前言
在之前的初阶数据结构中，我们已经了解过一点关于二叉树的概念和使用，这里我们将要了解一个新的二叉树–二叉搜索树。二叉搜索树也是一种树形结构。
学习二叉搜索树是为了后面学习map和set进行铺垫，有助于我们更好的理解map和set的特性。其次二叉树中有的部分OJ题使用C语言写起来会比较麻烦，而在我们学过c++之后在去尝试写这些OJ题就会非常方便，废话不多说，让我们步入正题，开始学习二叉搜索树。
一.二叉搜索树的概念和性质
二叉搜索树(Binary Search Tree，简称BST)是一种特殊的二叉树，二叉搜索树又称二叉排序树或者二叉查找树，可以是空树，如果不是空树时，具有以下性质：
有序性：
- 若它的左子树不为空，则左子树上所有节点的值都
小于根节点的值 - 若它的右子树不为空，则右子树上所有节点的值都
大于根节点的值
递归性：
- 它的左右子树也分别为二叉搜索树
二叉搜索树的有序性使得二叉搜索树在查找，插入和删除操作上具有高效性。递归性保证了整个树的结构一致性。
这里查找，插入和删除等操作我们直接通过模拟实现二叉搜索树来详细讲解
二.模拟实现
基本框架
- 代码实现：
#include<iostream>
#include<algorithm>
using namespace std;
//树的节点类封装
template<class K>
class BSTreeNode{
public:
//构造函数
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
k _key;
};
//二叉搜索树类的封装
template<class K>
class BSTree{
//重定义节点类型为Node
typedef BSTreeNode<K> Node;
public:
//构造函数
BSTree()
:_root(nullptr)
{}
//....其他成员函数
private:
Node* _root;
}
- 实现原理：
- 二叉搜索树中每个树的节点都包含指针域和数据域，指针域中有两个节点指针分别指向
_left左子结点和_right右子节点，数据域中存储的是_key节点数据，通过类将节点进行封装 - 二叉搜索树中每个树都含有一个根节点
_root，通过类将二叉搜索树进行封装
- 二叉搜索树中每个树的节点都包含指针域和数据域，指针域中有两个节点指针分别指向
中序遍历
在前面二叉搜索树的概念中我们可以知道，二叉搜索树也叫二叉排序树，通过其有序性再加上中序遍历就可以实现排序效果，这里展示中序遍历的代码实现
- 代码实现：
void InOrder(){
_InOrder(_root);
cout<<endl;
}
private:
void _InOrder(Node* root){
if(root==nullptr){
return;
}
_InOrder(root->_left);
cout<<root->_key<<" ";
_InOrder(root->_right);
}
- 实现原理：
- 因为在类中，根节点
_root为私有类型，不能在类外中作为参数使用，所以这里使用两个函数来达到调用效果 - 子函数
_InOrder要设置成私有类型，防止在类外中调用，只能通过函数InOrder调用
- 因为在类中，根节点
查找函数
因为二叉搜索树的左右子树结构相同，所以可以实现递归调用，所以查找函数以及之后的插入和删除都展示两种代码实现，递归和非递归实现
- 非递归代码实现：
bool Find(const K& key){
//空树时，直接返回false，没有找到
if(_root==nullptr){
return false;
}
//非空树时，循环查找
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 FindR(const k& key){
return _FindR(_root,key);
}
private:
bool _FindR(Node* root,const K& key){
if(root==nullptr){
return false;
}
if(root->_key<key){
return _FindR(root->_right,key);
}
else if(root->_key>key){
return _FindR(root->_left,key);
}
else{
return true;
}
}
- 实现原理：
- 查找过程从根节点开始，如果目标值小于当前节点的值，到该节点的左子树中查找；如果目标值大于当前节点的值，到该节点的右子树中查找，当相等时说明已经找到返回
true - 当遇到空节点时，非递归表示没有找到，返回
false；递归表示当前子树中没有，返回到上一层的函数调用中去，直到没有找到，依次返回false
- 查找过程从根节点开始，如果目标值小于当前节点的值，到该节点的左子树中查找；如果目标值大于当前节点的值，到该节点的右子树中查找，当相等时说明已经找到返回
插入函数
- 非递归代码实现：
bool Insert(const K& key){
if(_root==nullptr){
_root=new Node(key);
return true;
}
else{
Node* cur=_root;
Node* parent=cur;
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;
}
-
实现原理：
- 树为空，则直接新增节点，赋值给根节点指针
- 树不为空，按照二叉搜索树的有序性来查找插入位置，同时设置一个
parent指针，用来指向插入位置的父节点，找到插入位置后，再判断是插入到父节点指针的左子结点还是右子节点
-
递归代码实现：
bool InsertR(const K& key){
return _InsertR(_root,key);
}
private:
bool _InsertR(Node*& root,const K& key){
if(root==nullptr){
root=new Node(key)
return true;
}
if(root->_key<key){
return _InsertR(root->_right,key);
}
else if(root->_key>key){
return _InsertR(root->_left,key);
}
else{
return false;
}
}
- 实现原理：
- 和非递归不同的是，这里递归调用中，参数节点为指针类型的引用，通过引用，不用在设置父节点来插入，直接找到对应位置，对应节点为空时，赋值给当前节点即可
删除函数
删除节点时首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
-
删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
-
删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
-
在删除节点的左子树中寻找最大（最右）结点用它的值填补到被删除节点，或者右子树的最小（最左）节点，交换后再来处理该结点的删除问题–替换法删除
- 非递归代码实现：
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->_right=cur){
parent->_right=cur->_right;
}
else{
parent->_left=cur->_right;
}
}
}
//删除节点的右子结点为空
else if(cur->_right==nullptr){
if(cur==_root){
_root=cur->_left;
}
else{
if(parent->_right==cur){
parent->_right=cur->_left;
}
else{
parent->_left=cur->_left;
}
}
}
//删除节点的左右子节点都不为空
else{
Node* parent=cur;
Node* leftMax=cur->_left;
while(leftMax->_right){
parent=leftMax;
leftMax=leftMax->_right;
}
swap(cur->_key,leftMax->_key);
if(parent->_left==leftMax){
parent->_left=leftMax->_left;
}
else{
parent->_right=leftMax->_right;
}
cur=leftMax;
}
delete cur;
cur=nullptr;
return true;
}
}
return false;
}
-
实现原理：
- 通过二叉搜索树的有序性找到要删除的节点，当节点的
_key值等于key时，该节点就是要删除的节点 - 删除时，分为三种情况
- 删除节点的左子结点为空，判断删除节点是父节点的左子结点还是右子节点，将删除节点的右子节点交给父节点对应的左右子节点
- 删除节点的右子节点为空，判断删除节点是父节点的左子结点还是右子节点，将删除节点的左子结点交给父节点对应的左右子节点
- 删除节点的左右子节点都不为空，从删除节点的左子树中找到最右节点
leftMax替换，替换后，将删除节点的子节点交给父节点 - 最后释放节点指针，置为空即可
- 通过二叉搜索树的有序性找到要删除的节点，当节点的
-
递归代码实现：
bool EraseR(const K& key){
return _EraseR(_root,key);
}
private:
bool _EraseR(Node*& root,const K& key){
if(root==nullptr){
return false;
}
if(root->_key<key){
return _EraseR(root->_right,key);
}
else if(root->_key>key){
return _EraseR(root->_left,key);
}
else{
Node* del=root;
//删除节点的左子结点为空
if(root->_left==nulllptr){
root=root->_right;
}
//删除节点的右子节点为空
else if(root->_right==nullptr){
root=root->_left;
}
//左右子节点都不为空
else{
Node* leftMax=root->_left;
while(leftMax->_right){
leftMax=leftMax->_right;
}
swap(root->_key,leftMax->_key);
return _EraseR(root->_left,key);
}
delete del;
del=nullptr;
}
return true;
}
- 实现原理：
- 和非递归不同的是，递归调用的参数
root是节点指针类型，所以不用借助父节点来删除，可以直接更改节点指针root的指向 - 还是三种情况
- 如果删除节点的左子结点为空，节点指针root指向删除节点的右子节点
- 若果删除节点的右子节点为空，节点指针root指向删除节点的左子结点
- 如果左右子节点都不为空，找到替换节点，交换后，递归调用该函数从当前root节点的左子树中删除，相当于转换成上面两种情况
- 最后释放节点指针，指针置为空即可
- 和非递归不同的是，递归调用的参数
默认成员函数
- 析构函数代码实现：
~BSTree(){
Destroy(_root);
}
private:
void Destroy(Node* root){
if(root==nullptr){
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
root=nullptr;
}
-
实现原理：
通过后序遍历，先左子结点再右子节点最后再是根节点，依次释放节点指针即可
-
拷贝构造函数代码实现：
BSTree(const BSTree<K>& t){
_root=Copy(t._root);
}
private:
Node* Copy(Node* root){
if(root==nullptr){
return nullptr;
}
TreeNode* copyroot=new Node(root->_key);
copyroot->_left=Copy(root->_left);
copyroot->_right=Copy(root->_right);
return copyroot;
}
-
实现原理：
通过前序遍历，先拷贝构造出根节点，再递归调用构造左子树和右子树，最后返回根节点即可
-
赋值运算符重载函数代码实现：
BSTree<K>& operator=(BSTree<K>& t){
swap(_root,t._root);
return *this;
}
-
实现原理：
直接交换赋值对象和被赋值对象的根节点指针即可
测试
测试代码如下：
void test1(){
int arr[]={6,3,0,5,9,1,2,4,8,7};
BSTree<int> t;
for(auto e:arr){
t.InsertR(e);
}
t.InOrder();
for(auto a:arr){
t.EraseR(a);
t.InOrder();
}
}
void test2(){
int arr[]={6,3,0,5,9,1,2,4,8,7};
BSTree<int> T1;
for(auto e:arr){
T1.InsertR(e);
}
BSTree<int> T2(T1);
T2.InOrder();
BSTree<int> T3;
T3=T1;
T3.InOrder();
cout<<T3.FindR(8)<<endl;
cout<<T3.FindR(100)<<endl;
}
int main(){
test1();
test2();
return 0;
}
测试结果如下：
三.完整代码
BSTree.h文件完整代码：
#include<iostream>
#include<algorithm>
using namespace std;
template<class K>
class BSTreeNode{ //二叉搜索树的节点类封装
public:
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
};
template<class K>
class BSTree{ //二叉树搜索树类的封装
typedef BSTreeNode<K> Node;
public:
BSTree() //构造函数
:_root(nullptr)
{
cout<<"BSTree()"<<endl;
}
~BSTree(){ //析构函数
cout<<"~BSTree()"<<endl;
Destroy(_root);
}
BSTree(const BSTree<K>& t){ //拷贝构造函数
cout<<"BSTree(const BSTree<K>& t)"<<endl;
_root=Copy(t._root);
}
BSTree<K>& operator=(BSTree<K>& t){ //赋值运算符重载
swap(_root,t._root);
return *this;
}
void InOrder(){ //中序遍历
_InOrder(_root);
cout<<endl;
}
bool FindR(const K& key){ //递归查找函数
return _FindR(_root,key);
}
bool InsertR(const K& key){ //递归插入函数
return _InsertR(_root,key);
}
bool EraseR(const K& key){ //递归删除函数
return _EraseR(_root,key);
}
bool Find(const K& key){
if(_root==nullptr){
return false;
}
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 Insert(const K& key){ //插入节点函数
if(_root==nullptr){ //如果当前是空树，直接创建根节点
_root=new Node(key);
return true;
}
else{
Node* cur=_root;
Node* parent=cur;
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 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->_right==cur){ //父节点的右子节点是删除节点
parent->_right=cur->_right;
}
else{ //父节点的左子结点是删除节点
parent->_left=cur->_right;
}
}
}
else if(cur->_right==nullptr){ //删除的右子节点为空
if(cur==_root){ //且是根节点
_root=cur->_left;
}
else{ //不是根节点的情况
if(parent->_right==cur){ //父节点的右子节点是删除节点
parent->_right=cur->_left;
}
else{ //父节点的左子结点是删除节点
parent->_left=cur->_left;
}
}
}
else{ //删除的节点左右子节点都不为空
Node* parent=cur; //父节点初始时必须指向cur节点
Node* leftMax=cur->_left; //定义一个leftMax节点用来找左子树的最大节点也是最右节点
while(leftMax->_right){
parent=leftMax;
leftMax=leftMax->_right;
}
swap(cur->_key,leftMax->_key); //交换需要删除的节点和找到的替换节点的值
if(parent->_left==leftMax){
parent->_left=leftMax->_left;
}
else{
parent->_right=leftMax->_right;
}
cur=leftMax;
}
delete cur; //释放需要删除的节点
cur=nullptr; //节点置为空
return true;
}
}
return false;
}
private:
void _InOrder(Node* root){ //中序遍历子函数
if(root==nullptr){
return;
}
_InOrder(root->_left);
cout<<root->_key<<" ";
_InOrder(root->_right);
}
void Destroy(Node* root){ //析构函数子函数
if(root==nullptr){ //后序遍历即可
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
root=nullptr;
}
Node* Copy(Node* root){ //拷贝构造子函数
if(root==nullptr){ //前序遍历即可
return nullptr;
}
Node* copyroot=new Node(root->_key);
copyroot->_left=Copy(root->_left);
copyroot->_right=Copy(root->_right);
return copyroot;
}
bool _FindR(Node*& root,const K& key){ //递归查找子函数
if(root==nullptr){
return false;
}
if(root->_key<key){
return _FindR(root->_right,key);
}
else if(root->_key>key){
return _FindR(root->_left,key);
}
else{
return true;
}
}
bool _InsertR(Node*& root,const K& key){ //递归插入子函数
if(root==nullptr){ //如果当前节点为空，说明找到了插入的位置
root=new Node(key); //因为指针引用，所以直接创造新节点
return true; //插入成功，返回true
}
if(root->_key<key){ //当前节点_key值小于key值，到右子树中查找
return _InsertR(root->_right,key);
}
else if(root->_key>key){ //当前节点_key值大于key值，到左子树中查找
return _InsertR(root->_left,key);
}
else{ //当前节点_key值等于key值，说明已经存在，返回false
return false;
}
}
bool _EraseR(Node*& root,const K& key){ //递归删除子函数
if(root==nullptr){ //如果当前节点为空，说明没有找到要删除的节点
return false; //返回false
}
if(root->_key<key){ //当前节点_key值小于key值，到右子树中查找
return _EraseR(root->_right,key);
}
else if(root->_key>key){ //当前节点_key值大于key值，到左子树中查找
return _EraseR(root->_left,key);
}
else{ //当前节点_key值等于key值，说明找到要删除的节点
Node* del=root; //从新顶一个指针指向当前要删除的节点
if(root->_left==nullptr){ //删除节点左子结点为空
root=root->_right; //root指向删除节点的右子节点
}
else if(root->_right==nullptr){ //删除节点右子结点为空
root=root->_left; //root指向删除节点的左子节点
}
else{ //如果删除节点的左右子节点都不为空
Node* leftMax=root->_left; //定义一个新的节点指针指向删除节点的左子结点
while(leftMax->_right){ //查找替换节点，左子树的最大节点，也是最右节点
leftMax=leftMax->_right;
}
swap(root->_key,leftMax->_key); //交换删除节点和替换节点的值
return _EraseR(root->_left,key); //再从左子树中查找要删除的节点
}
delete del; //释放删除节点
del=nullptr; //节点置为空
}
return true;
}
private:
Node* _root;
};
** 以上就是关于二叉搜索树的概念和模拟实现的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！**
