唐山专门做网站,网站后期增加内容,深圳网络推广方法,云南网络推广报价明细本章主要是二叉树的进阶部分#xff0c;学习搜索二叉树可以更好理解后面的map和set的特性。
1.二叉搜索树概念
二叉搜索树的递归定义为#xff1a;非空左子树所有元素都小于根节点的值#xff0c;非空右子树所有元素都大于根节点的值#xff0c;而左右子树也是二叉搜索树…本章主要是二叉树的进阶部分学习搜索二叉树可以更好理解后面的map和set的特性。
1.二叉搜索树概念
二叉搜索树的递归定义为非空左子树所有元素都小于根节点的值非空右子树所有元素都大于根节点的值而左右子树也是二叉搜索树。 2.二叉搜索树实现
2.1.接口分析
2.1.1.查找
从根开始比较查找比根大则往右边走查找比根小则往左边走查找。最多查找高度次走到空还没找到则该值不存在。
2.1.2.插入
树为空则直接新增节点赋值给root指针树不空按二叉搜索树性质查找插入位置插入新节点
2.1.3.删除
首先查找元素是否在二叉搜索树中如果不存在则返回false。否则要删除的结点可能分下面四种情况
要删除的结点无孩子结点要删除的结点只有左孩子结点要删除的结点只有右孩子结点要删除的结点有左、右孩子结点
看起来有待删除节点有四种情况实际情况1可以与情况2或者3合并起来因此真正的删除过程如下 情况1删除该结点且使被删除节点的双亲结点指向被删除结点的左/右孩子结点直接删除 情况2在它的右子树中寻找中序下的第一个结点关键码最小也就是右子树中最小的结点用它的值填补到被删除节点中再来处理该结点的删除问题替换法删除 补充实际上情况2找左子树的最大节点也是可以的。
上述体现了一种“托孤”的现象这和Linux中孤儿进程的托孤很是类似。
2.2.具体实现
#include iostream
#include string
using namespace std;templatetypename K//这里更加习惯写K也就是关键值key的类型
struct BinarySearchTreeNode
{BinarySearchTreeNodeK* _left;BinarySearchTreeNodeK* _right;K _key; BinarySearchTreeNode(K key K()) : _key(key), _left(nullptr), _right(nullptr) {}
};templatetypename K
class BinarySearchTree
{typedef BinarySearchTreeNodeK Node;
public://BinarySearchTree() : _root(nullptr) {}BinarySearchTree() default;//强制编译器生成默认的构造函数BinarySearchTree(const BinarySearchTreeK b){_root copy(b._root);}BinarySearchTreeK operator(BinarySearchTreeK b)//b拷贝了一份{swap(_root, b._root);return *this;}~BinarySearchTree(){destroy(_root);}//1.插入bool insert(const K key){/*对于第一个插入的节点就是根节点。至于数据冗余我在这里定义不允许数据冗余也就是不允许出现重复的数据节点。这样的搜索二叉树会受到数据先后顺序插入的影响您也可定义允许*///1.查看是否根节点if (_root nullptr){_root new Node(key);return true;}//2.寻找存放的位置Node* parent nullptr;//存放root的父节点Node* root _root;//遍历从根节点开始while (root)//直到空为止{parent root;if (root-_key key) {root root-_right;}else if(root-_key key){root root-_left;}else//root-_key key{return false;//默认不允许重复数据}}//3.插入节点及数据root new Node(key);if (parent-_key key)//注意不可以直接赋值给root不仅内存泄露还连接不上节点{parent-_right root;}else{parent-_left root;}return true;}bool insertR(const K key){return _insertR(_root, key);}//2.删除bool erase(const K key){/*寻找被删除的节点删除后如果是单子节点还好如果是多子节点就需要找到一个托孤后依旧满足二叉搜索树性质的节点因此删除有两种情况A.被删除节点是叶子节点 或者 被删除节点的左或右孩子为空直接将孩子节点替换被删除节点即可B.被删除节点拥有两个子节点取右子树中最小的节点替代被删除的节点当然也可以取左子树的最大节点b1.最小节点没有右孩子最小节点直接替代被删除节点并且将最小节点的空孩子节点交给父节点领养b2.最小节点存在右孩子最小节点直接替代被删除节点并且将最小节点的右孩子节点交给父节点领养最后还需要注意删除根节点根节点没有父节点的问题*/Node* parent nullptr;Node* cur _root;//1.寻找节点while (cur){if (cur-_key key){parent cur;//不可以和下一个if语句共用会出现cur和parenat的情况例如test_1()中删除10的时候cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{//2.删除节点找到了if (cur-_left nullptr)//2.1.左为空{if (parent nullptr)//避免cur是根节点没有父节点例如test_1()中删除11的时候{_root cur-_right;delete cur;return true;}if (parent-_left cur){parent-_left cur-_right;}else//parent-_right cur{parent-_right cur-_right;}delete cur;}else if (cur-_right nullptr)//2.2.右为空{if (parent nullptr){_root cur-_left;delete cur;return true;}if (parent-_left cur){parent-_left cur-_left;}else//parent-_right cur{parent-_right cur-_left;}delete cur;}else//2.3.左右均不为空取左子树中最大的或者取右子树中最小的节点替代被删除的节点{Node* pminRight cur;//注意不能为nullptr因为有可能出现不进循环的情况Node* minRight cur-_right;//我们选择找右数最小节点while (minRight-_left ! nullptr)//找到最左节点但是需要注意这个最左节点如果有右树那就需要最左节点的父节点接管{pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;//替换相当于删除if (pminRight-_left minRight)//最左节点的父节点托管最左节点的右树注意可能有两种情况{pminRight-_left minRight-_right;}else if (pminRight-_right minRight)//最左节点的父节点托管最左节点的右树注意可能有两种情况{pminRight-_right minRight-_right;}delete minRight;}return true;}}return false;}bool eraseR(const K key){return _eraseR(_root, key);}//3.查找bool find(const K key){Node* root _root;while (root){if (root-_key key){root root-_right;}else if (root-_key key){root root-_left;}else{return true;}}return false;}bool findR(const K key){return _findR(_root, key);}//4.打印void inOrder(){_inOrder(_root);cout endl;}private://1.销毁提供给析构void destroy(Node* root){if (root nullptr)return;destroy(root-_left);destroy(root-_right);delete root;root nullptr;}//2.拷贝提供给拷贝构造Node* copy(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.插入提供给递归插入bool _insertR(Node* root, const K key)//注意root是引用{if (root nullptr){root new Node(key);//这里由于传递的是引用那么root就是上一级递归的root-_left或者root-_rightreturn true;}if (root-_key key){return _insertR(root-_right, key);}else if (root-_key key){return _insertR(root-_left, key);}else{return false;}}//4.删除提供给递归插入bool _eraseR(Node* root, const K key){if (root nullptr)return false;if (root-_key key){return _eraseR(root-_right, key);}else if (root-_key key){return _eraseR(root-_left, key);}else//root-_key key{Node* del root;//保存要删除的节点if (root-_right nullptr){root root-_left;}else if (root-_left nullptr){root root-_right;}else//左右均不为空{Node* maxleft root-_left;while (maxleft-_right ! nullptr)//找左树的最大节点{maxleft maxleft-_right;}swap(root-_key, maxleft-_key);return _eraseR(root-_left, key);//由于左树的最大节点必有一个空孩子节点因此使用递归删除即可可以看到递归的删除比非递归及其的简单明了注意不可以直接传递maxleft这是一个局部变量}delete del;return true;}}//5.查找提供给递归查找bool _findR(Node* root, const K key){if (root nullptr)return false;if (root-_key key)return true;if (root-_key key){return _isRecursionFind(root-_left, key);}else//root-_key key{return _isRecursionFind(root-_right, key);}}//6.打印提供给递归打印void _inOrder(Node* root)//注意这里不能直接就拿_root当作缺省值了因为缺省值只能是常量或者全局变量而_root需要使用this-_root而this指针是函数形参不一定传过来了别谈使用_root了{if (root nullptr)return;_inOrder(root-_left);cout root-_key ;_inOrder(root-_right);}//.成员变量Node* _root;
};这里我还为您提供了三个测试样例
//普通测试
void test_1()
{BinarySearchTreeint b;b.insert(6);b.insert(2);b.insert(1);b.insert(4);b.insert(-2);b.insert(10);b.insert(9);b.insert(11);b.inOrder();b.erase(6);b.inOrder();b.erase(2);b.inOrder();b.erase(10);b.inOrder();b.erase(1);b.inOrder();b.erase(4);b.inOrder();b.erase(9);b.inOrder();b.erase(11);b.inOrder();b.erase(-2);b.inOrder();
}
//头删测试需要该_root为公有成员才可以测试
void test_2()
{BinarySearchTreeint b;b.insert(6);b.insert(2);b.insert(1);b.insert(4);b.insert(-2);b.insert(10);b.insert(9);b.insert(11);//b.inOrder();//b.erase(b._root-_key);//b.inOrder();//b.erase(b._root-_key);//b.inOrder();//b.erase(b._root-_key);//b.inOrder();//b.erase(b._root-_key);//b.inOrder();//b.erase(b._root-_key);//b.inOrder();//b.erase(b._root-_key);//b.inOrder();//b.erase(b._root-_key);//b.inOrder();//b.erase(b._root-_key);//b.inOrder();
}
//递归测试
void test_3()
{BinarySearchTreeint b;b.insertR(6);b.insertR(2);b.insertR(1);b.insertR(4);b.insertR(-2);b.insertR(10);b.insertR(9);b.insertR(11);BinarySearchTreeint b1(b);b.inOrder();b.eraseR(6);b.inOrder();b.eraseR(2);b.inOrder();b.eraseR(10);b.inOrder();b.eraseR(1);b.inOrder();b.eraseR(4);b.inOrder();b.eraseR(9);b.inOrder();b.eraseR(11);b.inOrder();b.eraseR(-2);b.inOrder();b1.inOrder();b.inOrder();
}3.二叉搜索树应用
3.1.Key模型
考虑“在不在”的问题例如
门禁系统车库系统单词检查、搜索…
查找对象是否在数据库中存在这样的场景在现实中有很多。
3.2.Key/Value模型
通过一个值查找另外一个值例如
中英文互译电话号码查询快递信息验证码查询信息…
只需要在一个节点中包含一个数据对即可。
另外我们之前说过二叉搜索树一般不存储重复的元素如果相同的元素可以让该元素绑定一个int元素形成键值对这种情况的实际应用有统计高频词汇。 补充实际上上面的这两种模型对标的是C的set和map容器这些我们后续学习。 4.二叉搜索树分析
由于缺失平衡性二叉搜索树在最不理想的状态一颗斜树查找的时间复杂度是 O ( n ) O(n) O(n)最好的效率是 O ( l o g 2 ( N ) ) O(log_{2}(N)) O(log2(N))。
