C++ 二叉搜索树(BST)的实现(非递归版本与递归版本)与应用

C++ 二叉搜索树的实现与应用

  • 一.二叉搜索树的特点
  • 二.我们要实现的大致框架
  • 三.Insert
  • 四.InOrder和Find
    • 1.InOrder
    • 2.Find
  • 五.Erase
  • 六.Find,Insert,Erase的递归版本
    • 1.FindR
    • 2.InsertR
    • 3.EraseR
  • 七.析构,拷贝构造,赋值运算符重载
    • 1.析构
    • 2.拷贝构造
    • 3.赋值运算重载
  • 八.Key模型完整代码
  • 九.二叉搜索树的应用
    • 1.Key模型
    • 2.Key-Value模型

二叉搜索树既可以实现为升序版本,也可以实现为降序版本
本文实现为升序版本

一.二叉搜索树的特点

二叉搜索树是一种特殊的二叉树
它的特点是:

1.左子树的所有节点均比根节点的值小
2.右子树的所有节点均比根节点的值大
3.左右子树都是二叉搜索树
4.中序遍历序列是有序的
5.一般二叉搜索树不允许有重复值

当然,二叉搜索树默认是升序的,不过也可以实现成降序的样子
只需要更改一下第1条和第2条即可,
第一条改为左子树的节点都要大于根节点
第二条改为右子树的节点都要小于根节点
此时实现出来的二叉搜索树就是降序的
在这里插入图片描述
例如:这个树就是一个二叉搜索树

二.我们要实现的大致框架

#pragma once
#include <iostream>
using namespace std;
//BST排升序:左孩子小于我,  右孩子大于我
//排降序:   左孩子大于我,  右孩子小于我//节点的结构体
template <class K>
struct BSTreeNode
{BSTreeNode<K>* _left = nullptr;BSTreeNode<K>* _right = nullptr;K _key;BSTreeNode(const K& key):_key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://非递归实现insert.find,erasebool Insert(const K& key);Node* Find(const K& key);bool Erase(const K& key);//析构函数  后续遍历析构~BSTree();//C++11新语法BSTree() = default;//强制生成默认构造//拷贝构造//先序遍历构造BSTree(const BSTree<K>& bst);//赋值运算符重载:现代版本BSTree<K>& operator=(BSTree<K> bst);void InOrder(){_InOrder(_root);}//递归实现insert.find,eraseNode* 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);}private://拷贝构造函数的子函数Node* _Copy(const Node* root);//析构函数的子函数void _Destroy(Node*& root);//中序遍历的子函数void _InOrder(Node* root);//find的子函数Node* _FindR(Node* root, const K& key);//insert的子函数bool _InsertR(Node*& root, const K& key);//erase的子函数bool _EraseR(Node*& root, const K& key);//给根节点_root缺省值nullptrNode* _root = nullptr;
};

这是Key模型的版本,最后我们要修改一份Key-Value版本

template <class K>

这里模板给K的原因是:贴合K模型而已,所以没有用T
这里的R : recursion(递归的英文)

//给根节点_root缺省值nullptr
Node* _root = nullptr;

这里直接给根节点_root缺省值nullptr了,编译器默认生成的构造函数就会使用这个缺省值
这里补充一点:

//C++11新语法:给default这个关键字增加了一个含义
BSTree() = default;//强制生成默认构造

三.Insert

学习了二叉搜索树的特点之后,我们来看如何插入一个值
在这里插入图片描述
注意:
1.在遍历查找要插入的位置时一定要记录父节点,否则无法插入
2.最后插入的时候要判断该值与父节点的大小关系,这样才能知道要插入到左侧还是右侧

因此我们就可以写出这样的代码

插入成功,返回true
插入失败(说明插入了重复值),返回false
bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = _root;//记录父亲,因为要能够插入while (cur){//要插入的值小于父亲,往左找if (cur->_key > key){parent = cur;cur = cur->_left;}//要插入的值大于父亲,往右找else if (cur->_key < key){parent = cur;cur = cur->_right;}//出现了重复元素,BST搜索二叉树不允许出现重复值,因此不允许插入,返回falseelse{return false;}}//此时cur为空,说明找到了空位置 在此位置插入valuecur = new Node(key);//要插入的元素小于父亲,插入到左侧if (parent->_key > key){parent->_left = cur;}//要插入的元素大于父亲,插入到右侧else{parent->_right = cur;}//插入成功return true;
}

四.InOrder和Find

1.InOrder

关于InOrder中序遍历跟普通二叉树的中序遍历是一模一样的
只不过因为要用递归去实现,而且_root是私有变量不能让外界访问到,因此封装了一个子函数,让子函数去递归完成任务,主函数可以被外界调用到,子函数无需提供给外界
同理,后面的Insert,Erase,Find的递归版本都是封装了一个子函数,跟InOrder这方面的思路一样

void InOrder()
{_InOrder(_root);cout << endl;
}
void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);
}

2.Find

学习了Insert之后,Find对我们来说就很简单了
要查找一个值key
1.key小于当前节点的值,往左找
2.key大于当前节点的值,往右找
3.key等于当前节点的值,找到了,返回该节点
4.要查找的当前节点为空节点,返回nullptr,代表查找失败

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return cur;}}//此时cur为空说明没有找到return nullptr;
}

此时我们就可以开始玩这个二叉搜索树了
在这里插入图片描述
可以看出,中序遍历的确是有序的

五.Erase

前面的insert和find都比较简单,接下来的erase就比较复杂了
erase分为4种情况:
对于要删除的节点
1.该节点没有左孩子,也没有右孩子
在这里插入图片描述
不过这里最后删除的时候是不对的,因为14依旧指向13,而13已经被释放了,所以14的_left指针就成为了野指针,怎么办呢?
此时只需要先让该节点的父亲(也就是14)指向空,
然后就可以放心地删除13了
正确的版本:
在这里插入图片描述
2.该节点没有左孩子,但是有右孩子
此时只需要把该节点的右孩子托付给父亲即可
在这里插入图片描述
3.该节点有左孩子,不过没有右孩子
此时只需要把该节点的左孩子托付给父亲即可
其实第一类可以归为第二类或者第三类
在这里插入图片描述
4.该节点既有左孩子,又有右孩子
在这里插入图片描述
其实这里的1就是整棵树当中小于3这个值的最大值
4就是整棵树当中大于3这个值的最小值
他们都可以来代替3这个值

1其实就是要删除的节点的左子树的最大值(最大值就是最右侧节点)
4其实就是要删除的节点的右子树的最小值(最大值就是最左侧节点)

而且1和4都有一个特点:最多只有一个孩子
此时删除1和4就可以借助于第2种或第3种方案了

我们今天按照寻找右子树的最小值的方式来做

注意:之后删除3的操作不能使用递归,因为交换后就不是二叉搜索树了,就无法保证能够找到那个值了

不过上述的讨论当中我们讨论的都是该节点有父亲的情况
都没有讨论下面的这种情况:
5.我要删除的是根节点呢?
(1).根节点没有左孩子也没有右孩子

Node* tmp = _root;
_root=nullptr;
delete tmp;

在这里插入图片描述
(2).根节点只有1个孩子
因为我们知道:一个二叉搜索树的左子树和右子树都是二叉搜索树
比方说根节点只有左孩子,没有右孩子
此时只需要让根节点等于左子树的根节点(也就是根节点的左孩子)即可
在这里插入图片描述
删除根节点之前:
在这里插入图片描述
删除根节点之后:
在这里插入图片描述
可见,这么做的话,删除之后的确也还是二叉搜索树
同理,节点只有右孩子,没有左孩子的时候
只需要让根节点等于右子树的根节点(也就是根节点的右孩子)即可

同理,第一种情况也可以归为第二种情况
(3).根节点有2个孩子
在这里插入图片描述
删除之前:
在这里插入图片描述
删除之后:
在这里插入图片描述
在这里插入图片描述
不过这里也分为两种情况
1.因为查找的是右子树的最左侧节点
也就是一路往左查找,因此最后的时候只需要让我的右孩子成为父亲的左孩子即可

2.不过如果没有一路查找,直接找到了的话
也就是说此时我是父亲的右孩子,那么就要让我的右孩子成为父亲的右孩子了

上面演示的那种情况就属于第二种情况
因此,我们就可以写出这样的代码
里面的注释非常详细,大家如果还不是特别理解的话,
可以对照着边走读代码边画图来更好地理解

//删除成功,返回true
//删除失败,说明没有这个元素,返回false
bool Erase(const K& key)
{//1.没有左孩子,没有右孩子 可以归为2,3中的任意一类//2.有右孩子,没有左孩子//3.有左孩子,没有右孩子//4.有左孩子,也有右孩子Node* cur = _root;Node* parent = cur;//父亲while (cur){//往左找if (cur->_key > key){parent = cur;cur = cur->_left;}//往右找else if (cur->_key < key){parent = cur;cur = cur->_right;}//找到了else{//1.有右孩子,没有左孩子//此时只需要让他的右孩子代替它的位置即可(也就是把自己的右孩子给父亲,然后删除自己即可)if (cur->_left == nullptr){//要删除的是_root,且_root没有左孩子//那么让右孩子变成root即可if (cur == _root){_root = cur->_right;delete cur;}//说明我是父亲的左孩子if (cur == parent->_left){//就让我的右孩子成为父亲的左孩子parent->_left = cur->_right;delete cur;}//说明我是父亲的右孩子else{//就让我的右孩子成为父亲的右孩子parent->_right = cur->_right;delete cur;}}//2.有左孩子,没有右孩子else if (cur->_right == nullptr){//要删除的是_root,且_root没有左孩子//那么让右孩子变成root即可if (cur == _root){_root = cur->_left;delete cur;}//说明我是父亲的左孩子if (cur == parent->_left){//就让我的左孩子成为父亲的左孩子parent->_left = cur->_left;delete cur;}//说明我是父亲的右孩子else{//就让我的左孩子成为父亲的右孩子parent->_right = cur->_left;delete cur;}}//3.有左孩子,也有右孩子//我既可以让左子树的最大值替代我,也可以让右子树的最小值替代我//这里就找右子树的最小值吧,右子树的最小值就是右子树的最左侧节点//找到右子树中的最小值,将他的值跟我交换,然后删除刚才那个节点//注意:"删除刚才那个节点"的操作不能使用递归,因为交换后就不是BST了,就无法保证能够找到那个值了else{parent = cur;Node* MinOfRight = cur->_right;while (MinOfRight->_left){parent = MinOfRight;MinOfRight = MinOfRight->_left;}//开始交换swap(cur->_key, MinOfRight->_key);//然后删除MinOfRight//1.的确向下查找了//此时MinOfRight就是parent的左孩子//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的左孩子,然后就可以删除了if (parent->_left == MinOfRight){parent->_left = MinOfRight->_right;delete MinOfRight;}//2.没有继续往下查找//此时MinOfRight就是parent的右孩子//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的右孩子,然后就可以删除了else{parent->_right = MinOfRight->_right;delete MinOfRight;}}//删除成功return true;}}//此时cur为空说明没有找到return false;
}

六.Find,Insert,Erase的递归版本

1.FindR

Find的递归版本就很简单了:
假设要查找的值是Key
如果当前节点的值==key:查到了,返回当前节点即可
如果当前节点的值>key:说明当前节点值太大,往左找
如果当前节点的值<key:说明当前节点值太小,往右找

Node* FindR(const K& key)
{return _FindR(_root,key);
}
Node* _FindR(Node* root, const K& key)
{if (root == nullptr){return nullptr;}if (root->_key > key){return _FindR(root->_left, key);}else if(root->_key < key){return _FindR(root->_right, key);}else{return root;}
}

2.InsertR

如果当前节点是空节点:说明找到了空位置,插入即可
如果当前节点的值>key:说明当前节点值太大,往左找插入位置
如果当前节点的值<key:说明当前节点值太小,往右找插入位置
如果当前节点的值==key:说明重复了,返回false,不能插入重复元素

bool InsertR(const K& key)
{return _InsertR(_root, key);
}
bool _InsertR(Node*& root, const K& key)
{if (root == nullptr){root = new Node(key);return true;}else if (root->_key > key){return _InsertR(root->_left, key);}else if(root->_key < key){return _InsertR(root->_right, key);}else{return false;}
}

这里特别巧妙的一点在于:只要加上引用
那么就可以不用传递父节点了
因为root就是上一个节点的左孩子或者右孩子的别名,改变root会影响到上一个节点的左孩子或者右孩子

这里引用作为参数的价值就显得格外巧妙了

3.EraseR

这里是递归版本的erase,
而且要删除的节点跟MinOfRight交换之后,右子树是一个二叉搜索树
因此后面删除MinOfRight的时候可以复用,直接在右子树上面删除MinOfRight即可
而且对于删除根节点也是如此

这里依旧使用引用作为参数,它的巧妙之处在于修改指向时特别方便了,无需传入父亲节点

bool EraseR(const K& key)
{return _EraseR(_root, key);
}
bool _EraseR(Node*& root, const K& key)
{if (root == nullptr){return false;}//1.往左找,在左子树里面删除keyif (root->_key > key){return _EraseR(root->_left, key);}//2.往右找,在右子树里面删除keyelse if (root->_key < key){return _EraseR(root->_right, key);}// 当前的根节点else{//root不仅仅是root,root是父亲的孩子的别名//因此只需要改变root就可以改变父亲的孩子了if (root->_left == nullptr){//不要忘了保存rootNode* del = root;root = root->_right;//这里不是迭代,而是修改指向,是把我的右孩子托付给父亲delete del;return true;}else if (root->_right == nullptr){Node* del = root;root = root->_left;delete del;return true;}else{Node* MinOfRight = root->_right;while (MinOfRight->_left){MinOfRight = MinOfRight->_left;}swap(root->_key, MinOfRight->_key);//注意:现在是递归版本,参数可以传入节点,此时这棵树不是BST,但是root的右子树是BST//所以此时递归删除root->_right上的key值即可//而且也适用于直接删除根节点的情况_EraseR(root->_right, key);}}return true;
}

七.析构,拷贝构造,赋值运算符重载

1.析构

跟二叉树的销毁一样,后序遍历销毁
依旧是采用递归版本

//析构函数  后续遍历析构
~BSTree()
{_Destroy(_root);
}
void _Destroy(Node*& root)
{if (root == nullptr) return;_Destroy(root->_left);_Destroy(root->_right);delete root;root = nullptr;
}

2.拷贝构造

先序遍历构造
先构造根节点,然后递归构造左子树和右子树
最后返回根节点

//拷贝构造
//先序遍历构造
BSTree(const BSTree<K>& bst)
{_root = _Copy(bst._root);
}
Node* _Copy(const Node* root)
{if (root == nullptr){return nullptr;}Node* NewRoot = new Node(root->_key);NewRoot->_left = _Copy(root->_left);NewRoot->_right = _Copy(root->_right);return NewRoot;
}

3.赋值运算重载

实现了拷贝构造之后就可以
直接现代写法了

//赋值运算符重载
BSTree<K>& operator=(BSTree<K> bst)
{std::swap(_root, bst._root);return *this;
}

八.Key模型完整代码

template <class K>
struct BSTreeNode
{BSTreeNode<K>* _left = nullptr;BSTreeNode<K>* _right = nullptr;K _key;BSTreeNode(const K& key):_key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://非递归实现insert.find,erasebool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = _root;//记录父亲,因为要能够插入while (cur){//要插入的值小于父亲,插入到左子树当中if (cur->_key > key){parent = cur;cur = cur->_left;}//要插入的的值大于父亲,插入到右子树当中else if (cur->_key < key){parent = cur;cur = cur->_right;}//出现了重复元素,BST搜索二叉树不允许出现重复值,因此不允许插入,返回falseelse{return false;}}//此时cur为空,在此位置插入valuecur = new Node(key);//要插入的元素小于父亲,插入到左子树当中if (parent->_key > key){parent->_left = cur;}//要插入的元素大于父亲,插入到右子树当中else{parent->_right = cur;}//插入成功return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return cur;}}//此时cur为空说明没有找到return nullptr;}bool Erase(const K& key){//1.没有左孩子,没有右孩子 可以归为2,3中的任意一类//2.有右孩子,没有左孩子//3.有左孩子,没有右孩子//4.有左孩子,也有右孩子Node* cur = _root;Node* parent = cur;//父亲while (cur){//往左找if (cur->_key > key){parent = cur;cur = cur->_left;}//往右找else if (cur->_key < key){parent = cur;cur = cur->_right;}//找到了else{//1.有右孩子,没有左孩子//此时只需要让他的右孩子代替它的位置即可(也就是把自己的右孩子给父亲,然后删除自己即可)if (cur->_left == nullptr){//要删除的是_root,且_root没有左孩子//那么让右孩子变成root即可if (cur == _root){_root = cur->_right;delete cur;}//说明我是父亲的左孩子if (cur == parent->_left){//就让我的右孩子成为父亲的左孩子parent->_left = cur->_right;delete cur;}//说明我是父亲的右孩子else{//就让我的右孩子成为父亲的右孩子parent->_right = cur->_right;delete cur;}}//2.有左孩子,没有右孩子else if (cur->_right == nullptr){//要删除的是_root,且_root没有左孩子//那么让右孩子变成root即可if (cur == _root){_root = cur->_left;delete cur;}//说明我是父亲的左孩子if (cur == parent->_left){//就让我的左孩子成为父亲的左孩子parent->_left = cur->_left;delete cur;}//说明我是父亲的右孩子else{//就让我的左孩子成为父亲的右孩子parent->_right = cur->_left;delete cur;}}//3.有左孩子,也有右孩子//我既可以让左子树的最大值替代我,也可以让右子树的最小值替代我//这里就找右子树的最小值吧,右子树的最小值就是右子树的最左侧节点//找到右子树中的最小值,将他的值跟我交换,然后删除刚才那个节点//注意:"删除刚才那个节点"的操作不能使用递归,因为交换后就不是BST了,就无法保证能够找到那个值了else{parent = cur;Node* MinOfRight = cur->_right;while (MinOfRight->_left){parent = MinOfRight;MinOfRight = MinOfRight->_left;}//开始交换swap(cur->_key, MinOfRight->_key);//然后删除MinOfRight//1.的确向下查找了//此时MinOfRight就是parent的左孩子//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的左孩子,然后就可以删除了if (parent->_left == MinOfRight){parent->_left = MinOfRight->_right;delete MinOfRight;}//2.没有继续往下查找//此时MinOfRight就是parent的右孩子//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的右孩子,然后就可以删除了else{parent->_right = MinOfRight->_right;delete MinOfRight;}}//删除成功return true;}}//此时cur为空说明没有找到return false;}//析构函数  后续遍历析构~BSTree(){_Destroy(_root);}//C++11新语法BSTree() = default;//强制生成默认构造//拷贝构造//先序遍历构造BSTree(const BSTree<K>& bst){_root = _Copy(bst._root);}//赋值运算符重载BSTree<K>& operator=(BSTree<K> bst){std::swap(_root, bst._root);return *this;}void InOrder(){_InOrder(_root);cout << endl;}//递归实现insert.find,eraseNode* 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);}
private:Node* _Copy(const Node* root){if (root == nullptr){return nullptr;}Node* NewRoot = new Node(root->_key);NewRoot->_left = _Copy(root->_left);NewRoot->_right = _Copy(root->_right);return NewRoot;}void _Destroy(Node*& root){if (root == nullptr) return;_Destroy(root->_left);_Destroy(root->_right);delete root;root = nullptr;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _FindR(Node* root, const K& key){if (root == nullptr){return nullptr;}if (root->_key > key){return _FindR(root->_left, key);}else if(root->_key < key){return _FindR(root->_right, key);}else{return root;}}bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}else if (root->_key > key){return _InsertR(root->_left, key);}else if(root->_key < key){return _InsertR(root->_right, key);}else{return false;}}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}//1.往左找if (root->_key > key){return _EraseR(root->_left, key);}//2.往右找else if (root->_key < key){return _EraseR(root->_right, key);}// 删除else{//root不仅仅是root,root是父亲的孩子的别名,让root成为root的右孩子即可if (root->_left == nullptr){Node* del = root;root = root->_right;//这里不是迭代,而是修改指向,托孤delete del;return true;}else if (root->_right == nullptr){Node* del = root;root = root->_left;delete del;return true;}else{Node* MinOfRight = root->_right;while (MinOfRight->_left){MinOfRight = MinOfRight->_left;}swap(root->_key, MinOfRight->_key);//注意:现在是递归版本,参数可以传入节点,此时这棵树不是BST,但是root的右子树是BST//所以此时递归删除root->_right上的key值即可//而且对于直接删除_root也没有任何影响_EraseR(root->_right, key);}}return true;}Node* _root = nullptr;
};

九.二叉搜索树的应用

1.Key模型

在这里插入图片描述

2.Key-Value模型

在这里插入图片描述
下面我们把刚才Key模型的代码改为Key-Value模型
只需要改一下:
1.BSTreeNode节点
2.insert
3.InOrder的打印即可
其他地方都不需要修改

namespace kv
{template <class K,class V>struct {BSTreeNode<K,V>* _left = nullptr;BSTreeNode<K,V>* _right = nullptr;K _key;V _value;BSTreeNode(const K& key,const V& value):_key(key),_value(value){}};template<class K,class V>class BSTree{typedef BSTreeNode<K,V> Node;public://非递归实现insert.find,erasebool Insert(const K& key,const V& value){if (_root == nullptr){_root = new Node(key,value);return true;}Node* cur = _root;Node* parent = _root;//记录父亲,因为要能够插入while (cur){//要插入的值小于父亲,插入到左子树当中if (cur->_key > key){parent = cur;cur = cur->_left;}//要插入的的值大于父亲,插入到右子树当中else if (cur->_key < key){parent = cur;cur = cur->_right;}//出现了重复元素,BST搜索二叉树不允许出现重复值,因此不允许插入,返回falseelse{return false;}}//此时cur为空,在此位置插入valuecur = new Node(key,value);//要插入的元素小于父亲,插入到左子树当中if (parent->_key > key){parent->_left = cur;}//要插入的元素大于父亲,插入到右子树当中else{parent->_right = cur;}//插入成功return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return cur;}}//此时cur为空说明没有找到return nullptr;}bool Erase(const K& key){//1.没有左孩子,没有右孩子 可以归为2,3中的任意一类//2.有右孩子,没有左孩子//3.有左孩子,没有右孩子//4.有左孩子,也有右孩子Node* cur = _root;Node* parent = cur;//父亲while (cur){//往左找if (cur->_key > key){parent = cur;cur = cur->_left;}//往右找else if (cur->_key < key){parent = cur;cur = cur->_right;}//找到了else{//1.有右孩子,没有左孩子//此时只需要让他的右孩子代替它的位置即可(也就是把自己的右孩子给父亲,然后删除自己即可)if (cur->_left == nullptr){//要删除的是_root,且_root没有左孩子//那么让右孩子变成root即可if (cur == _root){_root = cur->_right;delete cur;}//说明我是父亲的左孩子if (cur == parent->_left){//就让我的右孩子成为父亲的左孩子parent->_left = cur->_right;delete cur;}//说明我是父亲的右孩子else{//就让我的右孩子成为父亲的右孩子parent->_right = cur->_right;delete cur;}}//2.有左孩子,没有右孩子else if (cur->_right == nullptr){//要删除的是_root,且_root没有左孩子//那么让右孩子变成root即可if (cur == _root){_root = cur->_left;delete cur;}//说明我是父亲的左孩子if (cur == parent->_left){//就让我的左孩子成为父亲的左孩子parent->_left = cur->_left;delete cur;}//说明我是父亲的右孩子else{//就让我的左孩子成为父亲的右孩子parent->_right = cur->_left;delete cur;}}//3.有左孩子,也有右孩子//我既可以让左子树的最大值替代我,也可以让右子树的最小值替代我//这里就找右子树的最小值吧,右子树的最小值就是右子树的最左侧节点//找到右子树中的最小值,将他的值跟我交换,然后删除刚才那个节点//注意:"删除刚才那个节点"的操作不能使用递归,因为交换后就不是BST了,就无法保证能够找到那个值了else{parent = cur;Node* MinOfRight = cur->_right;while (MinOfRight->_left){parent = MinOfRight;MinOfRight = MinOfRight->_left;}//开始交换swap(cur->_key, MinOfRight->_key);//然后删除MinOfRight//1.的确向下查找了//此时MinOfRight就是parent的左孩子//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的左孩子,然后就可以删除了if (parent->_left == MinOfRight){parent->_left = MinOfRight->_right;delete MinOfRight;}//2.没有继续往下查找//此时MinOfRight就是parent的右孩子//并且此时MinOfRight没有左孩子,那么就可以直接把MinOfRight的右孩子给parent当做它的右孩子,然后就可以删除了else{parent->_right = MinOfRight->_right;delete MinOfRight;}}//删除成功return true;}}//此时cur为空说明没有找到return false;}//析构函数  后续遍历析构~BSTree(){_Destroy(_root);}//C++11新语法BSTree() = default;//强制生成默认构造//拷贝构造//先序遍历构造BSTree(const BSTree<K,V>& bst){_root = _Copy(bst._root);}//赋值运算符重载BSTree<K,V>& operator=(BSTree<K,V> bst){std::swap(_root, bst._root);return *this;}void InOrder(){_InOrder(_root);cout << endl;}//递归实现insert.find,eraseNode* FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key,const V& value){return _InsertR(_root, key,value);}bool EraseR(const K& key){return _EraseR(_root, key);}private:Node* _Copy(const Node* root){if (root == nullptr){return nullptr;}Node* NewRoot = new Node(root->_key);NewRoot->_left = _Copy(root->_left);NewRoot->_right = _Copy(root->_right);return NewRoot;}void _Destroy(Node*& root){if (root == nullptr) return;_Destroy(root->_left);_Destroy(root->_right);delete root;root = nullptr;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << " ";_InOrder(root->_right);}Node* _FindR(Node* root, const K& key){if (root == nullptr){return nullptr;}if (root->_key > key){return _FindR(root->_left, key);}else if (root->_key < key){return _FindR(root->_right, key);}else{return root;}}bool _InsertR(Node*& root, const K& key,const V& value){if (root == nullptr){root = new Node(key,value);return true;}else if (root->_key > key){return _InsertR(root->_left, key);}else if (root->_key < key){return _InsertR(root->_right, key);}else{return false;}}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}//1.往左找if (root->_key > key){return _EraseR(root->_left, key);}//2.往右找else if (root->_key < key){return _EraseR(root->_right, key);}// 删除else{//root不仅仅是root,root是父亲的孩子的别名,让root成为root的右孩子即可if (root->_left == nullptr){Node* del = root;root = root->_right;//这里不是迭代,而是修改指向,托孤delete del;return true;}else if (root->_right == nullptr){Node* del = root;root = root->_left;delete del;return true;}else{Node* MinOfRight = root->_right;while (MinOfRight->_left){MinOfRight = MinOfRight->_left;}swap(root->_key, MinOfRight->_key);//注意:现在是递归版本,参数可以传入节点,此时这棵树不是BST,但是root的右子树是BST//所以此时递归删除root->_right上的key值即可//而且对于直接删除_root也没有任何影响_EraseR(root->_right, key);}}return true;}Node* _root = nullptr;};
}

下面我们来测试一下
一个是统计单词出现的次数
一个是英汉互译的词典

void TestBSTree()
{string strs[] = { "apple","Banana","Grape","Mango","apple","Banana" ,"apple","Mango" ,"Mango" ,"Mango" ,"Mango" };// 统计单词出现的次数kv::BSTree<string, int> countTree;for (auto str : strs){auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();//英汉互译的词典kv::BSTree<string, string> dict;dict.Insert("insert", "插入");dict.Insert("erase", "删除");dict.Insert("BST", "二叉搜索树");dict.Insert("KV", "key-value模型");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << str << ":" << ret->_value << endl;}else{cout << "单词拼写错误" << endl;}}
}

在这里插入图片描述

以上就是C++ 二叉搜索树(BST)的实现(非递归版本与递归版本)与应用的全部内容,希望能对大家有所帮助!

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/219733.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

antd-table：通过rowClassName实现斑马条纹样式+通过rowSelection实现单选功能效果——基础积累

antd-table：通过rowClassName实现斑马条纹样式+通过rowSelection实现单选功能效果——基础积累

斑马条纹 对于element-ui是有个stripe斑马条纹的属性的&#xff0c;最终呈现的效果如下&#xff1a; antd-table中是没有这个属性的&#xff0c;但是可以通过rowClassName&#xff1a;可以给对应行添加指定类名。 实现方法&#xff1a; <a-table:rowClassName"getRo…
阅读更多...
当当狸AR智能学习图集跨越千年文明传承，邀您“面对面”与虚拟诗人互动对诗

当当狸AR智能学习图集跨越千年文明传承，邀您“面对面”与虚拟诗人互动对诗

中华传统文化底蕴深厚&#xff0c;余韵悠长。即使经过千年的历史裂变&#xff0c;依然历久铭心慰藉着一代又一代人的灵魂。千百年后的今天&#xff0c;成为了我们独一无二的财富。 如今&#xff0c;国人学习中华传统文化的方式有很多&#xff0c;诗词集、动画影片、诗歌传颂等…
阅读更多...
THEMIS---Beta Sprint Summary Essay Blog

THEMIS---Beta Sprint Summary Essay Blog

Which course does this assignment belong to2301-MUSE社区-CSDN社区云What are the requirements for this assignmentbeta SprintThe goal of this assignmentTo summarize the beta task progress and the teams sprintsTeam NameThemisTop-of-the-line collection of essa…
阅读更多...
动手学深度学习-自然语言处理-预训练

动手学深度学习-自然语言处理-预训练

词嵌入模型 将单词映射到实向量的技术称为词嵌入。 为什么独热向量不能表达词之间的相似性&#xff1f; 自监督的word2vec。 word2vec将每个词映射到一个固定长度的向量&#xff0c;这些向量能更好的表达不同词之间的相似性和类比关系。 word2vec分为两类&#xff0c;两类…
阅读更多...
蓝桥杯网络安全组竞赛

蓝桥杯网络安全组竞赛

竞赛规则及说明 选拔赛时长&#xff1a;4h 决赛时长&#xff1a;4h 竞赛形式&#xff1a;线上比赛&#xff1a; 个人赛&#xff1a;一人一机&#xff0c;全程机考 大赛制定竞赛系统&#xff0c;在时间内提交答案到比赛系统&#xff0c;超时无法提交 机器环境&#xff1a; 电脑…
阅读更多...
汽车EDI：Chrysler EDI项目案例

汽车EDI：Chrysler EDI项目案例

菲亚特克莱斯勒汽车Fiat Chrysler Automobiles(FCA)是一家全球性汽车制造商&#xff0c;主营产品包括轿车、SUV、皮卡车、商用车和豪华车等多种车型。其旗下品牌包括菲亚特、克莱斯勒、道奇、Jeep、Ram、阿尔法罗密欧和玛莎拉蒂等。 Chrysler通过EDI来优化订单处理、交付通知、…
阅读更多...
python学习3

python学习3

大家好&#xff0c;今天又来更新python学习篇了。本次的内容比较简单&#xff0c;时描述性统计代码&#xff0c;直接给出所有代码&#xff0c;如下&#xff1a; import pandas as pd from scipy.stats import fisher_exact from fuzzywuzzy import fuzz from fuzzywuzzy impor…
阅读更多...
风格随心选，AGI 让家居行业实现「秒级整装」内容营销

风格随心选，AGI 让家居行业实现「秒级整装」内容营销

家居行业的营销方式正在不断变化&#xff0c;从面向大牌代言、广告覆盖的品牌化营销&#xff0c;发展成了面向个性化消费者的多元化营销。 过去&#xff0c;家居消费者也许更看重产品材质&#xff0c;那是品味的彰显&#xff1b;如今&#xff0c;颜值即正义&#xff0c;消费者则…
阅读更多...
freeRTOS使用

freeRTOS使用

创建第一个FreeRTOS程序 1、官网源码下载 &#xff08;1&#xff09;进入FreeRTOS官网FreeRTOS professional services for application and RTOS development and consulting. FreeRTOS is an Open Source Code RTOS &#xff08;2&#xff09;点击下载FreeRTOS 2、处理目录 &…
阅读更多...
完全平方数 C语言xdoj49

完全平方数 C语言xdoj49

问题描述 若一个整数n能表示成某个整数m的平方的形式&#xff0c;则称这个数为完全平方数。写一个程序判断输入的整数是不是完全平方数。 输入说明 输入数据为一个整数n&#xff0c;0<n<10000000。 输出说明 如果n是完全平方数&#xff0c;则输出构成这个完全…
阅读更多...
Vue中的数据变化监控与响应——深入理解Watchers

Vue中的数据变化监控与响应——深入理解Watchers

目录 ​编辑 前言 1. 基本用法&#xff1a; 2. 深度监听&#xff1a; 3. 立即执行&#xff1a; 4. 监听多个数据&#xff1a; 5. 清理监听器&#xff1a; 6. 监听路由变化&#xff1a; 总结&#xff1a; 我的其他博客 前言 在Vue.js中&#xff0c;watch是一种用于监听…
阅读更多...
python+pytest接口自动化(16)-接口自动化项目中日志的使用 (使用loguru模块)

python+pytest接口自动化(16)-接口自动化项目中日志的使用 (使用loguru模块)

通过上篇文章日志管理模块loguru简介&#xff0c;我们已经知道了loguru日志记录模块的简单使用。在自动化测试项目中&#xff0c;一般都需要通过记录日志的方式来确定项目运行的状态及结果&#xff0c;以方便定位问题。 这篇文章我们使用loguru模块来记录接口自动化测试中的日…
阅读更多...
mybatis中oracle的sql没走索引导致特别慢（未加jdbcType的）

mybatis中oracle的sql没走索引导致特别慢（未加jdbcType的）

如果直接跑sql是能走索引很快&#xff0c;在mybatis中不能&#xff0c;可能就是jdbcType的原因。 比如&#xff0c;我有一个属性A&#xff0c;在表里面是VARCHAR2类型&#xff0c;但是在mybatis中的sql是#{a}&#xff0c;缺少jdbcTypeJdbcType.VARCHAR&#xff0c;就会导致myba…
阅读更多...
SpeechGPT领航：创新的130亿参数跨模态AI模型

SpeechGPT领航：创新的130亿参数跨模态AI模型

引言 在人工智能的最新进展中&#xff0c;SpeechGPT以其130亿参数的规模和跨模态会话能力引起了业界的广泛关注。这一由复旦大学邱锡鹏教授团队开发的模型&#xff0c;不仅在技术层面上取得了重大突破&#xff0c;也为多模态人工智能&#xff08;AI&#xff09;的未来发展指明…
阅读更多...
基于Web的流浪狗收容领养管理平台的设计与实现论文

基于Web的流浪狗收容领养管理平台的设计与实现论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本浪狗收容领养管理平台就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据…
阅读更多...
普通二叉树和右倾斜二叉树--LeetCode 111题《Minimum Depth of Binary Tree》

普通二叉树和右倾斜二叉树--LeetCode 111题《Minimum Depth of Binary Tree》

本文将以解释计算二叉树的最小深度的思路为例&#xff0c;致力于用简洁易懂的语言详细描述普通二叉树和右倾斜二叉树在计算最小深度时的区别。通过跟随作者了解右倾斜二叉树的概念以及其最小深度计算过程&#xff0c;读者也将对左倾斜二叉树有更深入的了解。这将为解决LeetCode…
阅读更多...
MYSQL练题笔记-高级字符串函数 / 正则表达式 / 子句-简单3题

MYSQL练题笔记-高级字符串函数 / 正则表达式 / 子句-简单3题

这个系列先写了三题&#xff0c;比较简单写在一起。 1.修复表中的名字相关的表和题目如下 看题目就知道是有关字符串函数的&#xff0c;于是在书里查询相关的函数&#xff0c;如下图&#xff0c;但是没有完全对口的函数&#xff0c;所以我还是去百度了。 然后发现结合上面的4个…
阅读更多...
Rancher中使用promtail+loki+grafna收集k8s日志并展示

Rancher中使用promtail+loki+grafna收集k8s日志并展示

Rancher中使用promtail+loki+grafna收集k8s日志并展示 目录 Rancher中使用promtail+loki+grafna收集k8s日志并展示1、添加Chart Repo2、安装promtail3、安装loki+grafana4、使用根据应用需求和日志数量级别选择对应的日志收集、过滤和展示方式，当日志量不太大，又想简单集中管…
阅读更多...
【Spark精讲】Spark Shuffle详解

【Spark精讲】Spark Shuffle详解

目录 Shuffle概述 Shuffle执行流程 总体流程 中间文件 ShuffledRDD生成 Stage划分 Task划分 Map端写入(Shuffle Write) Reduce端读取(Shuffle Read) Spark Shuffle演变 SortShuffleManager运行机制 普通运行机制 bypass 运行机制 Tungsten Sort Shuffle 运行机制…
阅读更多...
C语言学习第二十六天（算法的时间复杂度和空间复杂度）

C语言学习第二十六天（算法的时间复杂度和空间复杂度）

1、算法效率 衡量一个算法的好坏&#xff0c;是从时间和空间两个方面来衡量的&#xff0c;换句话说就是从时间复杂度和空间复杂度来衡量的 这里需要补充一点&#xff1a;时间复杂度是衡量一个算法的运行快慢&#xff0c;空间复杂度是主要衡量一个算法运行所需要的额外空间。 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023