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,erase
bool 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,erase
Node* 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缺省值nullptr
Node* _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搜索二叉树不允许出现重复值,因此不允许插入,返回false
else
{
return false;
}
}
//此时cur为空,说明找到了空位置 在此位置插入value
cur = 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.往左找,在左子树里面删除key
if (root->_key > key)
{
return _EraseR(root->_left, key);
}
//2.往右找,在右子树里面删除key
else if (root->_key < key)
{
return _EraseR(root->_right, key);
}
// 当前的根节点
else
{
//root不仅仅是root,root是父亲的孩子的别名
//因此只需要改变root就可以改变父亲的孩子了
if (root->_left == nullptr)
{
//不要忘了保存root
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值即可
//而且也适用于直接删除根节点的情况
_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,erase
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搜索二叉树不允许出现重复值,因此不允许插入,返回false
else
{
return false;
}
}
//此时cur为空,在此位置插入value
cur = 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,erase
Node* 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,erase
bool 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搜索二叉树不允许出现重复值,因此不允许插入,返回false
else
{
return false;
}
}
//此时cur为空,在此位置插入value
cur = 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,erase
Node* 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)的实现(非递归版本与递归版本)与应用的全部内容,希望能对大家有所帮助!
