前端和做网站,手机网站安装,工人找活平台,网站备案那个省份【C】---二叉搜索树 一、二叉搜索树概念二、二叉搜索树操作#xff08;非递归#xff09;1.二叉搜索树的查找 #xff08;非递归#xff09;#xff08;1#xff09;查找#xff08;2#xff09;中序遍历 2.二叉搜索树的插入#xff08;非递归#xff09;3.二叉搜索树… 【C】---二叉搜索树 一、二叉搜索树概念二、二叉搜索树操作非递归1.二叉搜索树的查找 非递归1查找2中序遍历 2.二叉搜索树的插入非递归3.二叉搜索树的删除非递归 三、二叉搜索树操作递归1.二叉搜索树的查找递归2.二叉搜索树的插入递归3.二叉搜索树的删除递归 四、二叉搜索树的默认成员函数1.构造2.拷贝构造3.赋值运算符重载4.析构 五、K模型和KV模型搜索树1.K模型搜索树2.KV模型搜索树 六、二叉搜索树性能分析 一、二叉搜索树概念
二叉搜索树又叫二叉排序数它或者是空树或者是具有以下性质的二叉树
如果它的左子树不为空那么左子树上所有节点的值都小于根结点的值。如果它的右子树不为空那么右子树上所有节点的值都大于根节点的值。它的左右子树也是二叉搜索树。 int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};比如说这个数组都可以将它化为二叉搜索树 总结在左子树值比根小右子树值比根大。 当树走中序遍历时序列都是有序的。
二叉搜索树 的 结构定义 #includeiostream
using namespace std;templateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
private:Node* _root;
public:BSTree():_root(nullptr){}
};二、二叉搜索树操作非递归
1.二叉搜索树的查找 非递归
利用二分查找的方法借助我们去二叉搜索树中查找节点。 查找的时间复杂度最坏的情况就是查找高度hlogN次就可以判断一个值在不在节点里面。
1查找
查找的思路
key比当前结点的值小往左走key比当前结点的值大往右走key当前结点的值就找到了 // 查找Node* Find(const K key){Node* cur _root;while (cur){if (key cur-_key){cur cur-_left;}else if (key cur-_key){cur cur-_right;}else{return cur;// 找到了}}return nullptr;// 遍历完了都还没找到}2中序遍历
由于根节点_root是私有成员变量如果在main函数里面来进行中序遍历的话这就是在类外对私有成员进行访问这是不合法的
所以说我们要解决这个问题可以用这样 在类的public内的 中序遍历 InOrder 里面 再套一层私有的中序遍历_InOrder这样_InOrder身为私有函数就可以访问私有变量_root
private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key endl;_InOrder(root-_right);}
public:// 中序遍历void InOrder() //这个函数 类外可以直接访问{_InOrder(_root); // 这个函数是 私有函数 对 私有成员 的访问cout endl;}2.二叉搜索树的插入非递归
插入节点分两步
1找位置 ①key比当前节点值大向左走②key比当前节点值小向右走③key等于当前节点值该节点值已经存在插入失败2插入 ①key比父亲节点值小就插入父亲左子树②key比父亲节点值大就插入父亲右子树由于插入后要将节点链接到树中因此要定义parent节点用来链接新节点 // 插入bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;// (1) 找到插入的位置while (cur){if (key cur-_key){parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}else{return false;// 二叉搜索树不允许数据冗余}}cur new Node(key);// (2) 判断if (keyparent-_key){parent-_left cur;}else{parent-_right cur;}return true;}3.二叉搜索树的删除非递归
非递归删除
1找位置 ①key比当前节点值大向左走②key比当前节点值小向右走③key等于当前节点值找到了准备删除2删除有两种删除方法非递归和递归 非递归删除: ①该节点没有孩子即该节点是叶子节点删除节点后把父亲指向自己的指针置空②该节点有一个孩子就把该节点的孩子节点的链接给该节点的父亲顶替自己的位置①可以当成②的特殊情况③该节点有两个孩子找比它自己的左孩子大比它自己的右孩子小的节点替换它也就是拿它的左子树的最大节点或右子树的最小节点替换它替换之后该节点就只有一个孩子或没有孩子了就变成①或②了。// 删除bool erase(const K key){Node* cur _root;Node* parent nullptr;// (1) 找到插入的位置while (cur){if (key cur-_key){parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}else{break;}}// 1、2、 (子 代替 父亲的位置)// 大前提如果要删除的节点left为空if (cur-_left nullptr){// 如果要删除根if (cur _root){_root cur-_right;// 那就让cur的右当根}// 如果要删除的不是根else{// 如果要删除的节点cur在父亲的左边。// 因为是替代法所以说要让 子 的位置代替 父亲 的位置但是 子 的位置只有_right存在所以说会把_right的位置放到即将要删除cur的位置。if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}// 大前提如果要删除的节点right为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{// 因为是替代法所以说要让 子 的位置代替 父亲 的位置但是 子 的位置只有_left存在所以说会把_left的位置放到即将要删除cur的位置。if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}// 3、要删除的cur不只有一个节点。可能有多个节点甚至整个指子树// 找到要删除节点cur左子树最大的节点右子树最小的节点来代替cur的位置。else{// 要么找cur左子树中的max要么就找右子树中的min// 这里 以 RightMin为例// (1)找到 RightMin (就像找 cur那样)Node* RightMin cur-_right;Node* RightMinParent cur; // 定义 RightMinParent 为了方便后续节点的连接。while (RightMin-_left){RightMinParent RightMin;RightMin RightMin-_left;}// (2)找到了 就交换swap(RightMin-_key, cur-_key);// (3) 交换完后 就链接if (RightMinParent-_left RightMin)RightMinParent-_left cur;elseRightMinParent-_right cur;// 链接完成delete cur;}return true;}递归删除
相对于非递归只需要修改找到了要修改的代码找到了后不需要管cur到底左为空、右为空、还是左右都不为空
① 找要删除节点的右子树的最小节点并把它的值保存起来
② 删除右子树的最小节点
③ 把要删除的节点值替换成右子树的最小节点值 else//左右都不为空替换法删除{//找右子树最小节点Node* minRight cur-_right;while (minRight-_left){minRight minRight-_left;}//用min保存右子树最小节点的值K min minRight-_key;//递归调用自己去替换删除节点一定会走到左为空的情况处理this-Erase(min);//删除完毕替换节点之后把cur的值替换成mincur-_key min;}三、二叉搜索树操作递归
理解了非递归操作以后 递归操作就很简单了
#includeiostream
using namespace std;//树的节点可以支持多种类型
templateclass K
//树节点结构
struct BSTreeNode
{BSTreeNodeK* _left;//左指针BSTreeNodeK* _right;//右指针K _key;//值//构造函数BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){}
};templateclass K
class BStree//树结构
{typedef BSTreeNodeK Node;
public://递归查找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* _root;
};由于_root是私有的可以把递归子函数查找、插入、删除都定义成私有的
1.二叉搜索树的查找递归
private://查找Node* _FindR(Node* root, const K key){if (root nullptr)//没找到{return nullptr;}if (key root-_key)//到左子树去找{FindR(root-_left, key);}else if (key root-_key)//到右子树去找{FindR(root-_right, key);}else//找到了{return root;}}2.二叉搜索树的插入递归 //插入 加了root是_root的别名修改root就直接修改到上一层调用不用找父亲bool _InsertR(Node* root, const K key){if (root nullptr)//找到位置了{root new Node(key);return true;}if (key root-_key)//到左子树去找位置{_InsertR(root-_left, key);}else if (key root-_key)//到右子树去找位置{_InsertR(root-_right, key);}else//已存在无需插入{return false;}}3.二叉搜索树的删除递归
递归删除和二叉树的删除非递归一样找到后的删除也有两种方式递归和非递归
找到后的非递归删除 //插入 加了root是_root的别名修改root就直接修改到上一层调用不用找父亲 bool _EraseR(Node* root, const K key){if (root nullptr)//没找到{return false;}if (key root-_key)//到左子树去找{_EraseR(root-_left, key);}else if (key root-_key)//到右子树去找{_EraseR(root-_right, key);}else{//找到了root就是要删除的节点if (root-_left nullptr)//root左为空{Node* del root;root root-_right;delete del;}else if (root-_right nullptr)//root右为空{Node* del root;root root-_left;delete del;}else//root左右都不为空{//找到右子树最左节点替换Node* minParent root;Node* minRight root-_right;while (minRight-_left){minParent minRight;minRight minRight-_left;}//保存替换节点的值cur-_key minRight-_key;//链接if (minParent-_left minRight){minParent-_left minRight-_right;}else{minParent-_right minRight-_right;}//删除delete minRight;}return true;}}找到后的递归删除 else//root左右都不为空{ //找右子树最左节点Node* minRight root-_right;while (minRight-_left){minRight minRight-_left;}//保存右子树最左节点的值K min minRight-_key;//使用递归方法删除右子树最左节点_Erase(root-_right, min);}四、二叉搜索树的默认成员函数
现在还剩下二叉搜索树的构造、拷贝构造、赋值运算符重载、析构函数。
1.构造
public://构造函数需要将根初始化为空就行了BSTree():_root(nullptr){}2.拷贝构造
拷贝构造利用递归调用子函数不断拷贝节点: //拷贝构造BSTree(const BSTreeK t){_root t.copy(t._root);}在子函数处: Node* _copy(Node* root){if (root nullptr)//如果根为空直接返回{return;}Node* copyNode new Node(root-_key);//创建根节点copyNode-_left _copy(root-_left);//递归拷贝左子树节点copyNode-_right _copy(root-_right);//递归拷贝右子树节点return copyNode;//返回根}3.赋值运算符重载
借助拷贝构造用现代写法写: //赋值运算符重载(现代写法)BSTree operator(const BSTreeK t){swap(_root,t._root);return *this;}4.析构
递归调用子函数去析构 //析构~BSTree(){_Destroy(_root);_root nullptr;}在子函数处: _Destroy(root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}五、K模型和KV模型搜索树
1.K模型搜索树
K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 1、以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 2、在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
2.KV模型搜索树
KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见
1、比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对 2、再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是word, count就构成一种键值对。
改造二叉搜索树为KV结构的代码
#pragma once
#includeiostream
#includestring
using namespace std;namespace key_value
{templateclass K, class Vstruct BSTreeNode{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;// pairK, V _kv;BSTreeNode(const K key, const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};templateclass K, class Vclass BSTree{typedef BSTreeNodeK, V Node;public:// logNbool Insert(const K key, const V value){if (_root nullptr){_root new Node(key, value);return true;}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{return false;}}cur new Node(key, value);if (parent-_key key){parent-_right cur;}else{parent-_left cur;}return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return cur;}}return cur;}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(parent nullptr)if (cur _root){_root cur-_right;}else{if (cur parent-_left){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){//if(parent nullptr)if (cur _root){_root cur-_left;}else{// 右为空父亲指向我的左if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{// 左右都不为空替换法删除// // 查找右子树的最左节点替代删除Node* rightMinParent cur;Node* rightMin cur-_right;while (rightMin-_left){rightMinParent rightMin;rightMin rightMin-_left;}swap(cur-_key, rightMin-_key);if (rightMinParent-_left rightMin)rightMinParent-_left rightMin-_right;elserightMinParent-_right rightMin-_right;delete rightMin;}return true;}}return false;}void InOrder(){_InOrder(_root);cout endl;}private:void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_key : root-_value endl;_InOrder(root-_right);}private:Node* _root nullptr;};六、二叉搜索树性能分析 好了今天的分享就到这里了 如果对你有帮助记得点赞关注哦 我的主页还有其他文章欢迎学习指点。关注我让我们一起学习一起成长吧
