东莞市网站seo内容优化,网站自动加水印,摄影设计说明,企业库二叉搜素树简单介绍
二叉搜索树又称二叉排序树#xff0c;是具有以下性质的二叉树: 若它的左子树不为空#xff0c;则左子树上所有节点的值都小于根节点的值 若它的右子树不为空#xff0c;则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
注意…二叉搜素树简单介绍
二叉搜索树又称二叉排序树是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
注意空树也是二叉搜索树 二叉搜素树的模型
K模型
K模型即只有key作为关键字节点中只需要存储Key即可关键字即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下
以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。
KV模型
每一个关键码key都有与之对应的值Value即Key, Value的键值对。 该种方式在现实生活中非常常见 比如 英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对
再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出 现次数就是word, count就构成一种键值对。
K模式和KV模式实现上基本一样就是节点中存储的是key还是key,val的区别 二叉搜素树的性能
二叉搜索树的性能取决于树的高度因为一次查找最多查找高度次而删除和插入也是在查找的基础上增加了一些O(1)的操作 在最理想的情况下树是完全平衡的平均查找、插入和删除的时间复杂度O(log N)。 但在最坏的情况下树可能退化成一个链表此时这些操作的时间复杂度将增加到O(N)。
例 全部的实现代码放在了文章末尾
准备工作
创建两个文件一个头文件BSTree.hpp一个源文件test.cpp
【因为模板的声明和定义不能分处于不同的文件中所以把成员函数的声明和定义放在了同一个文件BSTree.hpp中】 RBTree.hpp存放包含的头文件命名空间的定义成员函数和命名空间中的函数的定义 test.cpp存放main函数以及测试代码 包含头文件
iostream用于输入输出 类的成员变量 构造函数和拷贝构造
构造函数没什么好说的默认构造就行了
BSTree() :_root(nullptr)
{}
拷贝构造 因为节点都是从堆区new出来的所以要深拷贝
使用递归实现深拷贝 因为拷贝构造不能有多余的参数但是递归函数又必须使用参数记录信息 所以再封装一个成员函数专门用来递归拷贝 然后在拷贝构造里面调用一下这个函数就行了
拷贝构造
BSTree(const BSTree obj)
{_root Copy(obj._root);
}swap和赋值运算符重载
交换两颗二叉搜索树的本质就是交换两颗数的资源数据而它们的资源都是从堆区申请来的然后用指针指向这些资源
并不是把资源存储在了二叉搜索树对象中
所以资源交换很简单直接交换_root指针的指向即可
void Swap(BSTree obj)
{std::swap(_root, obj._root);
}赋值运算符重载
BSTree operator(BSTree obj)
{this-Swap(obj);return *this;
}为什么上面的两句代码就可以完成深拷贝呢 这是因为
使用了传值传参会在传参之前调用拷贝构造再把拷贝构造出的临时对象作为参数传递进去
赋值运算符的左操作数*this再与传入的临时对象obj交换就直接完成了拷贝
在函数结束之后存储在栈区的obj再函数结束之后obj生命周期结束
obj调用析构函数把指向的从*this那里交换来的不需要的空间销毁 析构函数
使用递归遍历把所有从堆区申请的节点都释放掉 因为析构函数不能有多余的参数但是递归函数又必须使用参数记录信息 所以再封装一个成员函数专门用来递归释放 然后在拷贝构造里面调用一下这个函数就行了
析构函数
~BSTree()
{Destroy(_root);_root nullptr;
}find
具体流程 从根节点开始将目标值传入的key与当前节点的key进行比较。 如果目标值小于当前节点值则在左子树中继续查找 如果目标值大于当前节点值则在右子树中继续查找。
这个过程一直进行直到找到与目标值或者到达空节点为止。
把上述过程转成代码 insert
插入的具体过程如下 树为空则直接新增节点赋值给二叉搜索树的成员变量_root指针 树不空则按照查找find的逻辑找到新节点应该插入的位置 树不空如果树中已经有了一个节点的key值与要插入的节点的key相同就插入失败
这个过程一直进行直到找到与传入的key相等的节点或者到达空节点为止。
把上述过程转成代码 erase
删除操作较为复杂需要先在数中找到要删除的节点再根据要删除节点的子节点数量进行不同的处理 如果要删除节点没有子节点则直接删除该节点。 如果要删除节点有一个子节点子树则用其子节点子树替换该节点。 如果要删除节点有两个子节点子树 在右子树中找到最小值的节点或左子树中找到最大值的节点来替换待删除节点然后删除那个最小值或最大值的节点
情况1可以和情况2合并一下
把上述过程转成代码
bool Erase(const K key)
{Node* cur _root;从根节点开始Node* parent nullptr;先找到要删除的节点curwhile (cur)如果到了空节点就结束循环{if (cur-_key key) 目标值大于当前节点值则在右子树中继续查找{parent cur;cur cur-_right;}else if (cur-_key key) 目标值小于当前节点值则在左子树中继续查找{parent cur;cur cur-_left;}else{break;找到要删除的节点了结束循环}}如果找到空节点了还没找到要删除的节点就说明树里面本来就没有这个key不需要删除if (cur nullptr){return false; 删除失败返回false}else{如果 左 子树为空 右 子树不为空或者左右都为空)即只有右子节点右子树或者没有子节点if (cur-_left nullptr){如果父亲节点为空就表示cur为根节点if (parent nullptr){使用右子节点代替根节点_root cur-_right;}else 根据cur与它的父亲节点的链接关系{if (cur parent-_left){使用右子节点代替curparent-_left cur-_right;}else{使用右子节点代替curparent-_right cur-_right;}}delete cur; 删除cur节点即要删除的节点}如果 右 子树为空 左 子树不为空或者左右都为空)即只有左子节点左子树或者没有子节点else if (cur-_right nullptr){如果父亲节点为空就表示cur为根节点if (parent nullptr){使用左子节点代替根节点_root cur-_left;}else 根据cur与它的父亲节点的链接关系{if (cur parent-_left){使用左子节点代替curparent-_left cur-_left;}else{使用左子节点代替curparent-_right cur-_left;}}delete cur; 删除cur节点即要删除的节点}else 如果左右子树都不为nullptr{去cur要删除的节点的右子树中找key最小的节点Node* tmp cur-_right;Node* prev cur;二叉搜索树的最小节点一定在这颗树的最左边while (tmp-_left) 所以一直往左走直到左子树为nullptr{prev tmp;tmp tmp-_left; 往左走}用右子树中key最小的节点的数据替换cur中的数据也就相当于把cur要删除的节点删除了cur-_key tmp-_key;cur-_val tmp-_val;如果prev cur就说明tmp就是key最小的节点了此时tmp在cur(prev)的右边if (prev cur){把cur(prev)的 右边 连上tmp的右子树因为tmp虽然是最左节点但是它有可能还有右孩子cur-_right tmp-_right;delete tmp;}else{把prev的 左边 连上tmp的右子树因为tmp虽然是最左节点但是它有可能还有右孩子prev-_left tmp-_right;delete tmp;}}}return true; 删除成功返回true
}empty
bool Empty()
{如果_root为空那么树就是空的return _root nullptr;
}size
使用递归实现二叉搜索树的节点个数统计 因为我们经常使用的stl的容器的size都是没有参数的但是递归函数又必须使用参数记录信息 所以再封装一个成员函数专门用来递归 然后再size里面调用一下就行了
size_t Size()
{return _Size(_root);
}中序遍历
中序遍历的递归函数 然后再调用递归函数
void InOrder()
{_InOrder(_root);
}全部代码
#includeiostream
using namespace std;templateclass K, class V
struct BSTreeNode
{K _key;V _val;BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;BSTreeNode(const K key, const V val):_left(nullptr), _right(nullptr){_key key;_val val;}
};templateclass K, class V
class BSTree
{typedef BSTreeNodeK, V Node;
public:BSTree() :_root(nullptr){}BSTree(const BSTree obj){_root Copy(obj._root);}BSTree operator(BSTree obj){this-Swap(obj);return *this;}~BSTree(){Destroy(_root);_root nullptr;}void Swap(BSTree obj){std::swap(_root, obj._root);}bool Insert(const K key, const V val){if (_root nullptr)//树为空则直接新增节点{//赋值给二叉搜索树的成员变量_root指针_root new Node(key, val);return true;//返回true代表插入成功}Node* cur _root;//从根节点开始//定义parent来保存cur的父亲节点//假设根节点的父亲节点为nullptrNode* parent nullptr;while (cur){if (cur-_key key)//目标值大于当前节点值则在右子树中继续查找{parent cur;cur cur-_right;}else if (cur-_key key)//目标值小于当前节点值则在左子树中继续查找{parent cur;cur cur-_left;}else{return false;}}Node* newnode new Node(key, val);if (parent-_key key){parent-_left newnode;}else{parent-_right newnode;}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 nullptr;//找不到就返回nullptr}bool Erase(const K key){Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{break;}}if (cur nullptr)return false;else{if (cur-_left nullptr){if (parent nullptr){_root cur-_right;}else{if (cur parent-_left)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;}else if (cur-_right nullptr){if (parent nullptr){_root cur-_left;}else{if (cur parent-_left)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;}else{Node* tmp cur-_right;Node* prev cur;while (tmp-_left){prev tmp;tmp tmp-_left;}cur-_key tmp-_key;cur-_val tmp-_val;if (prev cur){cur-_right tmp-_right;delete tmp;}else{prev-_left tmp-_right;delete tmp;}}}return true;}void InOrder(){_InOrder(_root);}bool Empty(){return _root nullptr;}size_t Size(){return _Size(_root);}size_t Height(){return _Height(_root);}
private:Node* _root nullptr;size_t _Height(Node* root){if (root nullptr)return 0;int left _Height(root-_left);int right _Height(root-_right);return left right ? left 1 : right 1;}Node* Copy(Node* root){if (root nullptr)return nullptr;Node* newnode new Node(root-_key, root-_val);newnode-_left Copy(root-_left);newnode-_right Copy(root-_right);return newnode;}//使用 后序遍历 释放void Destroy(Node* root){//空节点不需要释放直接返回if (root nullptr)return;Destroy(root-_left);//递归释放左子树Destroy(root-_right);//递归释放右子树delete root;//释放根节点}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);//遍历左子树//打印信息cout root-_key : root-_val endl;_InOrder(root-_right);//遍历右子树}//直接遍历二叉树进行节点统计size_t _Size(Node* root){if (root nullptr)return 0;//统计左子树节点个数int left _Size(root-_left);//统计右子树节点个数int right _Size(root-_right);return left right 1;//1是当前节点}
};
