株洲网站优化找哪家,男女直接做性视频网站,公司内部网站建设方案,东莞职业技术学院二叉搜索树 前言正式开始模拟实现树节点以及树框架增中序遍历查找删除 递归实现增删查查插删 析构拷贝构造赋值重载时间复杂度分析应用场景两道题 前言
本来想先把搁置了一个月的Linux讲讲的#xff0c;但是里面有些内容需要用到一些比较高级的数据结构#xff0c;用C写的话… 二叉搜索树 前言正式开始模拟实现树节点以及树框架增中序遍历查找删除 递归实现增删查查插删 析构拷贝构造赋值重载时间复杂度分析应用场景两道题 前言
本来想先把搁置了一个月的Linux讲讲的但是里面有些内容需要用到一些比较高级的数据结构用C写的话比较麻烦所以还是接着我前面的C讲。
本篇主要讲二叉搜索树先说概念然后直接上手实现。再给一些生活中的场景最后用这里的二叉搜索树来解前面我写数据结构阶段的两道链表题。
正式开始
二叉搜索树搜索二叉树也叫二叉排序树。如果某棵二叉搜索树不是空树则其具有以下性质 若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 简单来说就是 左 根 右。搜索树不允许有重复值所以没有相等的情况。
二叉搜索树是第一个二叉树的应用还是比较有用的。概念讲完了就直接开始实现。
模拟实现
就实现三个功能一般的数据结构都是增删查改四个基本功能这里二叉搜索树少了一个改的功能具体为什么各位等会看其余的三个实现就懂了。
二叉搜索树分为两类一类是key模型一类是key/value模型至于什么意思暂时讲不了但是你们先看模拟实现就行了 这里先实现key模型的看完模拟实现就懂了。
树节点以及树框架
二叉搜索树的英文名字叫binary search tree缩写就用的是BST。
先是树节点这模版中的模版参数用的是K而不是平常的T主要是为了标志出这里的实现是key模型的实现 上面的是struct而不是class是因为等会实现的时候节点中的左右孩子指针和val一直都要用到。跟前面我在list的模拟实现那篇中同理。
然后就是树的框架
在里面typedef一下树节点用起来比较方便。初始情况下root为空。
然后就可以写增删查了。
增
就是往树里面插入。不过这里有点要求。就是插入树节点的时候要保证 左 根 右。所以要先找到合适的位置然后再在该位置上插入。
我们就用 int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13}; 这几个数来挨个插入。
先把图解画出来
那么上面的这棵树就是二叉搜索树如上面的过程能看懂那么我觉得二叉搜索树的插入思想你就明白了。
就是找合适的位置插入即可。
先给个接口 用bool作为返回值因为前面说了搜索树中不能有相同的数值。如果有了相同的数值就返回false。
中间要创建节点值为val的新节点所以我们可以在BSTreeNode中写一个构造
然后就是找合适位置了 cur经过如上代码就可找到要插入的位置。
如果数据结构学的不是很扎实的同学可能会犯如下错误 这种情况下直接返回。
屏幕前的你知道哪里出问题了吗 仔细捋一捋就能发现cur本来已经找到了该插入的位置的但是new了之后cur的值就变成了val新节点的地址了这里根本就没有插入就只是将cur不断地赋值而已。
那么要改一改插入的时候要插入到合适的位置要插入到某一个节点的孩子位置最重要的是要知道插入位置的父节点。
所以找插入位置的过程要不断记住路程中的父节点这样才能保证插入的位置是在树上的而不是随机找个节点插。
最终代码如下
再来写一个中序遍历验证一下
中序遍历
如果写成下面这样 调用的时候就有点小问题。
这样的写法在用对象调用的时候必须要将树的根节点指针传过去但是又有一个问题我实现的树里面根节点是私有的。
想要解决的话可以给一个接口来专门返回根节点的地址或者还可以用友元。
有的同学说可以给缺省参数将函数的缺省参数给为_root这样的做法是错误的
这里有一个最优解法就是搞一个子函数。 像下面这样 就可以直接不传参调用InOrder。 因为不支持插入重复元素所以这里绝对不会打印出重复元素。中序打印出来的结果完全就是排好序的。因为左根右的遍历方式打印出来就是有序的不理解的自己想一想。
然后来说查找。
查找
查找是这三个里面最简单的。 这里不需要返回节点什么的只要能判断在不在就可以了这也是key模型的关键所在等会也会讲对应的应用场景。
测试一下
再来说删除。
删除
这个最麻烦主要是删除一个数后要保持其仍然是一个二叉搜索树。
被删除的节点可以分三种情况
没有孩子有一个孩子有两个孩子
分别来画图看看 没有孩子 节点删除之后将树中的该位置改为nullptr就行。 实现起来的话先找到13删除13再让14的左指向空。 有一个孩子 子替换父即可。
实现起来的话就是先找到14然后让10的右指向13再删除14。 有两个孩子 删除的时候要用到替换法。 最麻烦的就在这里。
两种解决方式
让删除节点的左树中最大的替换到删除节点处让删除节点的右树中最小的替换到删除节点处
观看理论比较晦涩看图 这样替换下来仍能够保持其是一棵二叉搜索树。 实现起来的话两种方法 左子树先找到3再去3的左子树中找最大值1然后让二者的值交换这 样1就跑到了根3就跑到左子树上了再删除交换后的3处的节点。右子树先找到3再去3的左子树中找最小值4然后让二者的值交换这样4就跑到了根3就跑到右子树上了再删除交换后的3处的节点。 再来个例子
树的根节点的删除比较特殊这里没看懂的话没关系等会会详谈。
根据上面的思想删除两个孩子的节点方法可以总结如下
先找到删除的节点删除的时候只用选择 去左树中找最大值 或者 去右树中找最小值 就行了。 如果去左树中那么就是左树的最右边就是左树的最大值。 如果去右树中那么就是右树的最左边就是右树的最小值。
上面孩子的三种情况都要先找到删除的节点然后再分情况讨论即可。 那就可以写代码了
因为删除后要让删除的位置为空所以要定义出一个不断更新的父节点来找到最后删除位置的父节点。 根据二叉搜索树的特性先找到节点 然后再分孩子的情况讨论我们这里可以把没有孩子的和有一种孩子的放到一块先不说为什么各位看图 没有孩子比如删13的话此时就是这样 删除13然后让14的左为空可以直接让14指向13的任意一个节点因为13的任意节点的值都为空。 有一个孩子比如删14的话此时就是这样 如果删除14的话可以让10的右指向14的左13然后再删除14。 二者都能让 parent节点的左/右 指向 cur的左/右 就能实现替换这一过程替换之后再删除cur即可。
如下
然后内部还要分cur是parent的左还是右 上面删除cur的地方代码冗余了等会再搞。
但是还有问题如果是删除根节点的话上面的代码就出bug了。 比如说这样
因为如果val就是根节点的值话cur的while循环就进不去那么parent此时就是nullptr上面的代码就解引用空指针。所以还要分parent是否为空的情况 再来说左右都不为空的节点对应删除3 这里我们以找右树的最小值为例
右子树的最左边就是最小值
然后将3和4的值交换然后再删除min节点就可以了但是还要将6的左置空所以又得产生一个不断变换的父节点来记录min的父节点。
所以最终就是这样
这里不用判断parent是否为空的情况因为节点的数值交换了。
代码
这样删除工作就做好了可以说还是比较麻烦的。
测试一下 成功。
这里把完整的删除代码给出来
bool Erase(const K val)
{Node* parent nullptr;Node* cur _root;while (cur){if (cur-_val val){parent cur;cur cur-_right;}else if (cur-_val val){parent cur;cur cur-_left;}else // cur 就是要删除的节点{if (cur-_left nullptr){ // 左树为空的情况分两种// 1.包含了左右都为空 2.只有左为空 对应到图中就是删除13和删除10// 判断val是否为_root的valif (parent nullptr) // 也可用 cur _root 来判断{ // 这里cur左右都为空的情况也成立_root cur-_right;}else{// 看cur是parent的左树还是右树if (cur parent-_left) // cur是parent的左树parent-_left cur-_right;else // cur是parent的右树parent-_right cur-_right;}delete cur;cur nullptr;}else if (cur-_right nullptr){ // 右树为空的情况上面已经包含左右都为空的情况所以这里只有一种情况// 就是只有右树为空的情况对应到图中就是删除14// 判断val是否为_root的valif (parent nullptr){_root cur-_left;}else{// 看cur是parent的左树还是右树if (cur parent-_left) // cur是parent的左树parent-_left cur-_left;else // cur是parent的右树parent-_right cur-_left;}delete cur;cur nullptr;}else { // 左右都不为空Node* min cur-_right;Node* parentMin cur;// 去右树中找最小值while (min-_left){parentMin min;min min-_left;}swap(min-_val, cur-_val);if (parentMin-_left min)parentMin-_left min-_right;elseparentMin-_right min-_right;delete min;min nullptr;}// 删除成功return true;}}// 没有删除的节点return false;
}三个功能均已经实现了我们还可以用递归的方式实现。
递归实现增删查
先说最简单的查。
查 再说插入
插
直接看代码
这里非常巧妙运用了引用。
第一个参数root类型为Node*什么意思呢就是一个Node的引用也就是一个Node变量的别名。
当我们找到了要插入的位置的时候一定是一个子节点传过来的一定是root-_left 或者 root-_right 。所以引用的就是父节点左/右的指针。
所以当root为空的时候就是要插入的时候这时候root就是父节点左/右的指针就可以直接用new将开辟的空间赋值给root等价于直接将开辟的空间赋值给了父节点左/右的指针。
删
先给出大致框架
然后跟上面非递归的删除一样也要判断孩子的情况
又因为我们删除节点之后还要置空但是递归想要找父节点还要多传一个参数我们此时就可以再将参数改为的。也就是Node* root。这样root就直接变成了父节点的左/右指针了。
这里也不需要再考虑删除的位置是否为数的根了看代码
整个递归erase的代码如下
bool _EraseR(Node* root, const K val)
{if (root nullptr)return false;if (root-_val val){if (root-_left nullptr){Node* right root-_right;delete root;root right;}else if (root-_right nullptr){Node* left root-_left;delete root;root left;}else{Node* min root-_right;while (min-_left)min min-_left;swap(min-_val, root-_val);_EraseR(root-_right, val);}return true;}if (root-_val val)return _EraseR(root-_left, val);if (root-_val val)return _EraseR(root-_right, val);
}到这里这三个功能正式讲完。 注意上面的所写的函数都是子函数都是私有的公有的只提供了接口。 再说点别的。
析构
给出如下代码 运行结束之后会崩掉吗
答案是不会因为我还没有写析构。
那么二叉树的析构很简单。后序递归即可。
但是析构函数没有参数所以也是搞一个子函数就行。 然后上面的代码运行起来就崩掉了因为拷贝构造是默认生成的内置类型做浅拷贝。只是把cp的根节点指向了bst的根节点上两个值相同。所以析构就崩掉了。
拷贝构造
也是递归构造要写子函数。 测试 出错了编译器说我没有默认的构造函数可用。 因为生成了一个构造函数之后编译器就不再提供默认的构造函数了。拷贝构造也算构造。所以此时加上一个构造函数就行。
此时运行就崩不了。
赋值重载
这个还是老方法直接参数传值交换即可。 下面说说引用场景。
时间复杂度分析
二叉搜索树听名字就能知道主要是用来搜索的。那么其查找的时间复杂度是多少呢
可能有的同学认为是logN其实不是当树不是接近满二叉树或者完全二叉树时效率可能比较低比如棵单边树 这样查找效率就很低了就是O(N)的。
总的来说二叉搜索树的查找效率是取决于树形状的。
所以二叉搜索树控制插入的根节点的值非常重要但是一般很难决定。后面还有AVL树来平衡整棵树。
应用场景
上面写的是key模型的主要用来判断关键字在不在比如说 学生刷卡进宿舍楼。 这里就是学生卡中记录学生的某一项信息比如学号记录到卡的芯片中然后数卡的时候通过二叉搜索树来查找是否存在如果二叉搜索树比较均匀的话满或完全二叉树查找的效率就非常高当然AVL树比二叉搜索树方便点但原理都一样。检查一段英文中每个单词拼写是否正确。 记录正确的拼写然后查找单词是否存在就行了。 还有一种模型是key/value模型其原理是通过key来找value。key模型和key/value模型非常相似key/value模型还是通过key比较value只是一个附加项。例子有 英文单词译为中文 统计……出现的次数 这里简单写一个key/value模型
代码如下
templateclass K, class V
struct BSTreeNode
{BSTreeNodeK, V* _left;BSTreeNodeK, V* _right;K _key;V _value;BSTreeNode(const K key, const V value):_left(nullptr), _right(nullptr), _key(key), _value(value){}
};templateclass K, class V
class BSTree
{typedef BSTreeNodeK, V Node;
public:bool 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 nullptr;}bool Erase(const K key){//...return true;}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;
};拿第一个例子 插入的时候是按照英文字符串进行比较的。
两道题
这两道题说一下思路 链表相交 key模型先入一个链表再遍历另一个链表查找某节点是否存在若存在就返回存在的节点不存在就继续遍历链表直至遍历完毕。 复制带随机指针的链表 key/value模型建立原节点和拷贝节点的映射关系。
比如 黑色为原节点蓝色为拷贝节点。1和1,2和2,3和3建立映射。
1的random为3那么蓝色的1random也为3我们可以通过映射关系通过黑色的3找蓝色的3继而找到蓝色的random然后连接1、3即可。其余同理。
到此结束。。。
