网站设计特点,广告设计公司招聘,石家庄自适应网站建设,wordpress安全权限C 二叉搜索树的实现与应用 一.二叉搜索树的特点二.我们要实现的大致框架三.Insert四.InOrder和Find1.InOrder2.Find 五.Erase六.Find,Insert,Erase的递归版本1.FindR2.InsertR3.EraseR 七.析构,拷贝构造,赋值运算符重载1.析构2.拷贝构造3.赋值运算重载 八.Key模型完整代码九.二… C 二叉搜索树的实现与应用 一.二叉搜索树的特点二.我们要实现的大致框架三.Insert四.InOrder和Find1.InOrder2.Find 五.Erase六.Find,Insert,Erase的递归版本1.FindR2.InsertR3.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
{BSTreeNodeK* _left nullptr;BSTreeNodeK* _right nullptr;K _key;BSTreeNode(const K key):_key(key){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public://非递归实现insert.find,erasebool Insert(const K key);Node* Find(const K key);bool Erase(const K key);//析构函数 后续遍历析构~BSTree();//C11新语法BSTree() default;//强制生成默认构造//拷贝构造//先序遍历构造BSTree(const BSTreeK bst);//赋值运算符重载:现代版本BSTreeK operator(BSTreeK 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了,编译器默认生成的构造函数就会使用这个缺省值 这里补充一点:
//C11新语法:给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;
_rootnullptr;
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 BSTreeK 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.赋值运算重载
实现了拷贝构造之后就可以 直接现代写法了
//赋值运算符重载
BSTreeK operator(BSTreeK bst)
{std::swap(_root, bst._root);return *this;
}八.Key模型完整代码
template class K
struct BSTreeNode
{BSTreeNodeK* _left nullptr;BSTreeNodeK* _right nullptr;K _key;BSTreeNode(const K key):_key(key){}
};templateclass K
class BSTree
{typedef BSTreeNodeK 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);}//C11新语法BSTree() default;//强制生成默认构造//拷贝构造//先序遍历构造BSTree(const BSTreeK bst){_root _Copy(bst._root);}//赋值运算符重载BSTreeK operator(BSTreeK 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 Vstruct {BSTreeNodeK,V* _left nullptr;BSTreeNodeK,V* _right nullptr;K _key;V _value;BSTreeNode(const K key,const V value):_key(key),_value(value){}};templateclass K,class Vclass BSTree{typedef BSTreeNodeK,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);}//C11新语法BSTree() default;//强制生成默认构造//拷贝构造//先序遍历构造BSTree(const BSTreeK,V bst){_root _Copy(bst._root);}//赋值运算符重载BSTreeK,V operator(BSTreeK,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::BSTreestring, int countTree;for (auto str : strs){auto ret countTree.Find(str);if (ret NULL){countTree.Insert(str, 1);}else{ret-_value;}}countTree.InOrder();//英汉互译的词典kv::BSTreestring, 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)的实现(非递归版本与递归版本)与应用的全部内容,希望能对大家有所帮助!
