电子商务网站进度的基本流程,wordpress编辑器添加商品,软件制作流程,什么网站有高端定制案例作者#xff1a;几冬雪来 时间#xff1a;2023年11月7日 内容#xff1a;C的搜索二叉树讲解 目录
前言#xff1a;
什么是搜索二叉树#xff1a;
搜索二叉树的增删查改#xff1a;
搜索二叉树的定义初始化#xff1a;
搜索二叉树增操作#xff1a;
搜索二叉树找… 作者几冬雪来 时间2023年11月7日 内容C的搜索二叉树讲解 目录
前言
什么是搜索二叉树
搜索二叉树的增删查改
搜索二叉树的定义初始化
搜索二叉树增操作
搜索二叉树找操作
搜索二叉树删操作
搜索二叉树增删查改递归版本
搜索二叉树查操作递归版本
搜索二叉树增操作递归版本
搜索二叉树删操作递归版本
其余操作
析构函数
深拷贝
赋值
搜索二叉树的应用
代码
结尾 前言 在上一篇博客中我们艰难的结束了C部分多态知识的讲解多态属于C的一个重要的知识。而在多态结束之后下来要讲解的就是C语言时期二叉树进阶部分的知识那在讲解二叉树的进阶之前这里要先了解一下搜索二叉树。 什么是搜索二叉树
在学习搜索二叉树之前我们先要了解什么是搜索二叉树。
在C语言学习时期我们就有学习过普通的二叉树而搜索二叉树就是在普通二叉树中再添加一些新的特征。
那么它有什么不同的特征就成为了讨论的话题。 在这个地方如果左子树所有的节点都小于根右子树的所有结点都大于根每一棵子树都满足这个特征这里这棵二叉树就是搜索二叉树。
那为什么这样的树被称为搜索二叉树
这里的搜索二叉树就是字面意思方便搜索因为这里左树的节点都小于根右树的结点都大于根加入我们要寻找的一个值比根大这个地方我们就可以直接访问右树不用理会左树节点的值。
那么在这个地方如果要从搜索二叉树中找到一个值那么它最多是不是找高度次O(N)。 其实不然通常我们的二叉树都是左边这种形式都是如果将左边这棵二叉树换成根节点非常大的话就会变成右边这样的树。
这个时候我们就不能简单的去分析它们搜索所用的时间。
那么这个地方就会涉及到另外两棵树——红黑树和AVL树。 与此同时在这个地方搜索二叉树也可以被叫做二叉查找树和二叉排序树。
那么它为什么又被叫为二叉排序树呢这里就要谈一谈这棵树的中序或者中序遍历是一个什么样子的情况了。
如果搜索二叉树在这里走的是中序的话那么它最后出来的结果就是有序的因为搜索二叉树是左小右大的形式中序排序的结果就是——左-中-右所以说它的结果是有序的。
那么接下来我们就来书写搜索二叉树的代码了。
搜索二叉树的增删查改
再接下来我们就要讲解搜索二叉树的增删查改了。
在C语言时期我们并没有书写普通二叉树的增删查改这并不意味着二叉树的增删查改没有书写的必要知识因为在普通二叉树中因为插入的地方没有限制哪里都可以进行插入操作所以使得这些操作没有意义。 但是类似搜索二叉树这种特殊二叉树对比起普通二叉树它就有限制插入的地方所以特殊二叉树的增删查改是有意义的。
搜索二叉树的定义初始化
还是一样写二叉树的时候我们通常都会通过定义一个类来存储节点的左节点右节点和它自己本身的值 。 这个地方的第一个模板我们用其来构造左右节点。
第二个模板在私有处定义一个_root来作为头节点。
最后的在第二个模板之中我们要typedef第一个模板将它重新命名然后再对我们的头节点进行初始化。
搜索二叉树增操作
定义和初始化搜索二叉树之后接下来我们就要根据搜索二叉树来书写它的增的操作。 在这个地方我们定义一个bool函数再然后就是进行判断。
这里进行判断如果一开始我们的树里面没有值也就是树为空。这个时候就需要我们new一个节点作为我们的头节点使用。
如果这棵树不是空的话这里就要定义一个cur和parent指针然后进入循环判断以cur为条件如果cur为空就意味着到了空节点。
然后就是判断如果父节点存放的值小于要插入的值这个地方就放在左边反之则放在右边这里注意有一个特殊情况那就是要存的值和节点的值相同这种情况我们的数据就不能进行存储这里就需要返回false。 但是上边的代码只是单纯的进行比较确定位置而已这个地方要完成最终的插入操作的话这里还要创建一个新的节点给cur。
然后进行第二次比较因为parent这个时候因为没有进行重新的赋值初始化因此这里只需要判断一次然后将节点插入即可。 这里的最后就是书写二叉树中序遍历的代码先走左边然后走中间最后走右边三者都是以递归的形式。
搜索二叉树找操作
然后就是搜索二叉树中一个比较简单的操作也就是查找操作。
那么搜索二叉树的查找操作的代码要如何书写呢 这里就是我们查找操作的代码它的代码甚至可以沿用搜索二叉树中增操作的代码 因为查找操作比较简单因此也不过多的讲解。
搜索二叉树删操作
与搜索二叉树查找操作的难度不同删除可谓是搜索二叉树中增删查改里面最为困难的一个操作删除操作才是搜索二叉树的重点。
这个地方的删除操作分为几种情况。 第一种情况就是要删去这棵树值为7的节点这里因为值为7的节点刚刚好是我们的叶子节点因此这个地方只需要将值为6节点的右子树置空即可。
接下来就是第二种情况要删除的节点是值为14的节点。这里值为14的节点只有一个叶子节点这里也是十分的容易只需要将值为10的节点右子树链接上值为13的节点即可。
当然以上两种删除都是较为简单的问题接下来就是搜索二叉树难操作的地方了。 最后一种情况就是该节点有两个子节点这里拿头节点举例子假如这个地方我们将头节点删去那么这棵树要怎么进行调整。
这个地方我们不能顺便的拉一个节点来作为这棵树的头节点。
这里解决问题的方法就是从这一棵树中找出左树最大值的节点又或者是右树最小值的节点来作为我们的头节点这样才能真正的解决问题。
接下来我们就来书写搜索二叉树删除操作的代码。 这个地方要实现删除操作首先还是要定义一个自身节点和父节点然后对其进行初始化的操作。
如果然后就是判断节点值与左右子树的大小如果我们要查找的值小于父节点的值就像左走反之向右走。
然后就是找到了的情况这里先处理两个简单的情况那就是这个地方删除的节点刚好左右子树右一边为空。
然后对要删除的值之后就需要进一步的进行判断最后进行链接然后将cur的值进行删除即可。但是这个地方还有一种特殊的情况需要处理。 如这里的这张图这棵树只有右树如果这里要删除的节点是数据为8的节点这会导致程序的崩溃。
而且应对这个问题的方法就是将根节点进行转移从值为8节点转移到下一个节点中去。 解决这种情况的方法就是在判断是否为空之后对根节点进行判断如果根节点就是我们要删除的值这里就将下一个值定为新的根节点。
接下来还有一种最复杂的情况那就是左右都不为空的情况。 这个地方如果左右都不为空的话就需要我们去找左树的最大值又或者右树的最小值和这里要删除的值进行一个替换操作。
这里我们就找左树的最大值这里一开始就走节点的左边接下来就是进入循环因为我们这棵树是搜索二叉树因此条件就是节点一直走右边直到空为止。
但是这里的代码还有许多坑的地方存在。 首先就是替换的问题因为在图中7和8节点替换之后这里我们就要重新编译一遍所以为了防止找不到要替换的值这里我们需要找到父节点。
然后就是它的代码。 但是如果这样子书写的话又会有特殊情况的出现。
特殊情况也会导致最后代码的崩溃。 就如上图原本值为3的节点有左树无右树同时它也是根节点的下一个节点。这个地方如果要3和8的节点进行调换的话。
如果是这种情况的话判断条件的leftMax-_right指向的刚刚好是空这会导致循环进不去有间接的让父节点依旧为空。 这里经过一系列的修改之后我们的代码呈现这个样子。首先为了防止父节点为空的情况发生一开始我们就不将它初始化为空。
然后就是判断如果父节点的下一个结点正好是左树最大节点要删除的节点同时这个它的右树为空。
这里我们就要将父节点的左给leftMax的左反之则是父节点的将leftMax的左给父节点的右。最后将leftMax给给cur然后将cur进行delete操作即可删除这个值的节点。
搜索二叉树增删查改递归版本
上边讲解了搜索二叉树的增删查这个地方我们并没有再写搜索二叉树修改数据的代码因为在这之前我们要实现搜索二叉树增删查递归方式的书写。
这里就要查找操作来举例。
这里要注意一个点那就是在C当中凡是要递归走树型结构我们都需要写一个东西。 这个地方要想写搜索二叉树增删查改递归版本的话首要的就是要在私有类中书写一个子函数因为这里我们要实行递归操作就必须有数的变化。有变化才能递归
因此如果要书写搜索二叉树递归部分的代码的话我们就要将可能会发生变化的root加上。
搜索二叉树查操作递归版本
知道了这一个知识点之后接下来我们就来书写搜索二叉树查操作的代码。
这里的查操作的递归相较于删和增的递归版本要容易一些。 这个地方我们的代码这样书写即可。如果值大于要找的值这个地方就进入递归它的右边如果小的话就递归它的左边如果找到的话这里我们就只需要返回true即可。
这就是查找操作递归方法的书写。
搜索二叉树增操作递归版本
在讲解完了二叉树递归版本的查找数据后接下来就来讲解搜索二叉树的增操作代码要如何去书写。 这就是我们插入时候的代码了中间查找比较大小的操作这段代码可以直接将查操作的代码拿过来使用这里就不过多的讲解了。
但是这个地方的代码有些许的不同可以看见在函数对象中我们为root加入了一个引用操作。
这是因为要在递归判断之后顺便将我们要插入的节点插入进去。 对象中引用操作也就是在这里进行使用这里root如果为空的话也就是找到了要插入的位置。这个地方就不需要像以前一样重新遍历一遍找到父节点进行插入。
因为有引用的存在这个地方如果root为空找到插入的位置因为是引用因为我们就能直接new一个新节点出来将值放进去这样就能完成需求。
搜索二叉树删操作递归版本
在这个地方搜索二叉树的删除操作递归形式可以算我们增删查改中最为困难的一个操作了。
在平时考试问答搜索二叉树的问题一般都是提问搜索二叉树增删查改中删除操作那么下面我们就来看看删除操作要怎么书写 这个地方要进行删除操作的话首先还是免不了使用查找操作来找到我们想要删掉值的节点这里简单来说就是进行比较。
如果大于就走左边小于就走右边。
最后也是当我们找到要删除值的节点了这里的代码是最具有难度的因为删除操作要兼顾三种情况也就是左为空右为空和左右都不为空的情况。 这里如果两边有一边为空的情况我们就像上图一样书写这个地方在一开始要为root加一个引用这样子就可以通过引用来改变指向从而做到删除的作用。
类似有一个值为14的节点它有一个父节点和一个右边的子节点这里判断后将root-_right赋给root这样就使得递归回去14的父节点会指向14的子节点。
然后就是两边都不为空的情况。 这里先定义一个del在else中我们先找左树的最大节点找到那个节点之后在将根节点和这个左树最大节点替换。
然后再走一遍EraseR进行删除操作这个地方要记得传的参数为root-_left而不是leftMax这是因为leftMax为临时变量如果传临时变量的话再怎么修改递归中的root它都没有实际效果。
其余操作
在讲解完了两个版本的增删查改后接下来我们就简单将剩下的一些操作的代码给它写上和补齐。
析构函数
有一开始有构造函数那么结束的时候就有析构函数在这里我们就来书写搜索二叉树的析构函数用递归的形式。 书写析构函数之前需要我们去写出它的一个子函数因为我们析构递归没有参数。
这里使用递归去析构函数而不是循环是因为通常析构二叉树或者多叉树都是从数的叶子结点开始往回析构都是后序遍历删除比较容易循环析构比较麻烦。
这里我们就只需要递归一下左边再递归一下右边然后将root节点删除最后要记得参数加上引用符合后将删除的节点进行置空操作。
深拷贝
然后接下来因为上面的析构为递归式的析构因此在这里会发生浅拷贝的问题这里就需要我们写一个深拷贝的代码来解决这个问题。 这里我们就需要拷贝一棵新树出来先将这棵树传出去然后判断是否为空树如果为空树那么就返回空。
如果不为空树那就先创建一个头节点出来然后就是前序遍历拷贝递归拷贝先拷贝左在拷贝右。将这棵树拷贝出来最后返回这棵树的根节点即可。
赋值
最后的一个常用操作就是赋值操作这里就直接写代码即可。 这里就是简单的交换操作。
最后返回this指针即可。
搜索二叉树的应用
在了解完了搜索二叉树后我们就要来了解搜索二叉树会在哪些地方被应用到。 如上图搜索二叉树通常都是用来解决K(key)V(value)问题。
代码
#pragma oncetemplateclass K
struct BSTreeNode
{BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr),_right(nullptr),_key(key){}
};templateclass K
class BSTree
{typedef BSTrssNodeK Node;
public:BSTree():_root(nullptr){}BSTree(const BSTreeK t){_root Copy(t._root);}BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}~BSTree(){Destory(_root);}bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* cur _root;Node* parent cur;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);if (parent-_key key){parent-right cur;}else{parent-left cur;}return true;}bool 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 false;}}}}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 (cur _root){_root cur-_right;}else{if (parent-_right cur){parent-_right cur-_right;}else{parent-_left cur-_right;}}}else if(cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (parent-_right cur){parent-_right cur-_left;}else{parent-_left cur-_left;}}}else{Node* parent cur;Node* leftMax cur-_left;while (leftMax-_right){parent leftMax;leftMax leftMax-_right;}swap(cur-_key, leftMax-_key);if (parent-_left leftMax){parent-_left leftMax-_left;}else{parent-_right leftMax-_left;}cur leftMax;}delete cur;return true;}}return 0;}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root NUll){return;}_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}bool FindR(const K key){return _FindR(_root, key);}bool InsertR(const K key){return _InsertR(_root, key);}bool EraseR(const K key){_EraseR(_root, key);}private:Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* copyroot new Node(root-_key);copyroot-_left Copy(root-_left);copyroot-_right Copy(root-_right);return copyroot;}void Destory(Node* root){if (root nullptr){return;}Destory(root-_left);Destory(root-_right);delete root;root nullptr; }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{Node* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{Node* leftMax root-_left;while (leftMax-_right){leftMax leftMax-_right;}swap(root-_key, leftMax-_key);return EraseR(root-_left, key);}delete del; return true;}}bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (root-_key key){return _FindR(root-_right, key);}else if (root-_key key){return _FindR(root-_left, key);}else{return true} }bool _FindR(Node* root,const K key){if (root nullptr){return false;}if (root-_key key){return _FindR(root-_right, key);}else if (root-_key key){return _FindR(root-_left, key);}else{return true}}private:Node* _root;
};void TestBSTree1()
{}
结尾 到这里我们的搜索二叉树的基本内容就讲解完了但是这并不意味着它的结束在上文我们有说过。搜索二叉树还涉及到我们C中的AVL树和红黑树同时K,V问题也是后面我们要学习好了解的问题最后希望之篇博客能带来帮助。
