wordpress去category,,关键词排名快照优化,东莞网络公司电话,网页制作培训班课程文章目录 前言1. 二叉搜索树的概念2. 二叉搜索树的结构2.1 结点结构2.2 树结构 3. 插入操作#xff08;非递归#xff09;3.1 思路分析3.2 代码实现3.3 中序遍历#xff08;测试用#xff09; 4. 查找操作#xff08;非递归#xff09;4.1 思路分析4.2 代码实现 5. 删除操… 文章目录 前言1. 二叉搜索树的概念2. 二叉搜索树的结构2.1 结点结构2.2 树结构 3. 插入操作非递归3.1 思路分析3.2 代码实现3.3 中序遍历测试用 4. 查找操作非递归4.1 思路分析4.2 代码实现 5. 删除操作非递归-重难点5.1 情况分类及思路分析5.2 代码实现 6. 查找递归版本6.2 思路分析6.2 代码实现 7. 插入递归版本7.1 思路分析7.2 代码实现 8. 删除递归版本8.1 思路分析8.2 代码实现 9. 其它相关成员函数的实现9.1 析构9.2 构造和拷贝构造9.3 赋值重载 10. 完整代码10.1 BSTree.h10.2 BSTree.cpp 前言
二叉树在前面C数据结构阶段已经讲过本节取名二叉树进阶是因为 map和set特性需要先铺垫二叉搜索树而二叉搜索树也是一种树形结构。二叉搜索树的特性了解有助于更好的理解map和set的特性。二叉树中部分面试题稍微有点难度在前面讲解大家不容易接受且时间长容易忘。有些OJ题使用C语言方式实现比较麻烦比如有些地方要返回动态开辟的二维数组非常麻烦。 因此本节用C语言对二叉树部分进行收尾总结。
我们之前学的普通的二叉树其实意义不大因为如果只是用二叉树来存储数据的话还不如直接用链表或者顺序表等这些顺序结构。
那二叉树搜索树相对来说就比较有意义了。
1. 二叉搜索树的概念
那什么是二叉搜索树呢先来了解一下它的概念 二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树 若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树即它的每一棵子树也满足其左子树所有结点的值都小于根结点的值右子树的所有结点的值大于根结点的值 为什么又叫二叉排序树呢 仔细观察我们会发现如果对一棵搜索二叉树进行中序遍历的话 其实就能得到一个结点值的升序序列。 那了解了搜索二叉树的概念接下来我们就来手撕一个搜索二叉树。
2. 二叉搜索树的结构
首先我们来定义一下结点和搜索二叉树的结构 我们之前定义一个模板类一般都喜欢用Ttype但是在这里比较喜欢用Kkey 2.1 结点结构 2.2 树结构 相信大家很容易都能看懂那这里我就不详细解释了。
3. 插入操作非递归
接下来我们来实现一下向搜索二叉树中插入元素的操作。
3.1 思路分析
首先对于搜索二叉树来说它的插入应该有插入成功和插入失败因为搜索二叉树一般不允许出现重复元素两种情况。
我们来分析一下
首先看插入成功的情况 在搜索二叉树中要插入一个元素时如果可以 插入那么它插入的位置一定是确定的。 举个栗子 还是以这棵树为例假设我们现在要插入一个12 那要怎么做呢 其实就是从根结点开始去找出那个合适的位置然后把12放进去。 根结点的值是812大于8所以应该去右子树找8的右子树是1012依然大于10那再看10的右子树是14此时12小于14所以就要往14的左子树14的左子树为1312小于13所以再看13的左子树是空。 所以12就应该放在13的左子树上。 此时就插入成功了 那失败的情况呢 比如我们现在要插入一个13 首先还是根据大小去比较找合适的位置但是走到13的位置发现要插入的值和已经存在的值相等那就直接return false插入失败。 当然如果插入的是第一个结点那就不需要比较了直接让它成为根结点。
3.2 代码实现
那我们来写一下代码
首先第一个插入的结点是比较特殊的因为第一个要作为根结点 那怎么判断是不是第一个插入的呢 插入第一个的时候根结点是不是还是空的啊 所以 如果根结点为空那就证明是第一次插入就把它作为根结点。 那其它情况呢 那后续的插入就需要我们从根结点开始比较大小去找到合适的位置插入了思路上面已经讲过了这里就直接写代码了 按照我们上面讲的思路走到红框这里就走到key要插入的正确位置了。 那现在问题来了如何正确的插入key对应的结点并链接到搜索二叉树上 大家看这样可以吗 有没有什么问题 这样写会存在两个问题 第一个 这里的cur是一个函数里面的局部变量函数调用结束cur这个指针变量就被销毁了销毁了不说目前我们这样写是不是还会存在内存泄漏啊cur被销毁了但是它指向的空间还没释放。 那cur指向的空间不是属于这棵二叉树了嘛不是最终可以随着搜索树的析构释放吗 你把key的结点赋给cur就链接到树上了嘛并没有 这就是第二个问题 把结点给cur并没有链接到树上。 还看这个例子 走到上面红框的地方cur只是存了13这个结点假设取名为parent的左孩子指针即parent-left的一个指针变量相当于是parent-left的拷贝把结点赋给它并没有真正链接到13的左孩子上。 那怎么解决呢 我们在cur不断向左或向右去找到过程中记录它的父亲结点最终cur走到正确的位置把key的结点直接链接到父亲结点上就可以了 我们来修改一下 代码 bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* parent nullptr;Node* cur _root;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为空就是key应该插入的位置cur new Node(key);//链接if (key parent-_key)parent-left cur;if (key parent-_key)parent-right cur;return true;}实现好了行不行呢测试一下 构建我们示例中的那棵树看看结果一不一样 那我们构建好可以中序遍历打印一下看看中序遍历刚好是一个升序。 3.3 中序遍历测试用
那我们写个中序遍历 二叉树的遍历我们在初阶已经学过相信现在对于大家已经很简单了 ps之前left和right没加_现在补上了 那写好我就可以调了但会有一个问题 这里调用得传根结点因为要递归这个参数不能省但是类外无法访问私有成员_root把它放成共有的不太好。 那大家思考一下这里可不可以给缺省值 缺省值给一个_root不就行了。 是不行的因为缺省值必须是常量或者全局变量但一般不用全局变量 这个我们在C的第一篇文章有提到大家可以去复习。 而且在参数列表其实根本拿不到成员变量_root因为访问非静态成员要用this指针而this指针只能在成员函数内部使用参数列表也不行。 两个解决方法 提供一个GetRoot的成员函数/方法传参的时候通过该方法获取_root。 但C里不喜欢这样 那其实有另外一种比较简便得方法给InOrder函数在套一层封装一下 这样调的时候就不用传参了当然我就可以把_InOrder变成私有的了 然后我们来测试一下 就可以了。 4. 查找操作非递归
接着我们来看一下查找
4.1 思路分析 那查找其实是比较简单的 我们要查找某个结点那就从根开始比较查找比根大则往右边走查找比根小则往左边走查找找到的话返回true 最多查找高度次走到空还没找到则这个值不存在返回false 4.2 代码实现
写一下代码 bool 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 true;}}return false;}测试一下 没问题 5. 删除操作非递归-重难点
那如果要删除二叉搜索树中的某个结点应该怎么处理呢
5.1 情况分类及思路分析
首先查找元素是否在二叉搜索树中如果不存在则直接返回false 否则要删除的结点可能分下面四种情况
要删除的结点无孩子结点 比如 我们现在要删除4这个结点 那这种情况是不是直接删除就好了把4这个结点释放让6的左孩子指向空就行了。 要删除的结点只有右孩子结点左为空 比如我们现在要删除6 6要怎么删那这里关键在于把6删了他还有一个孩子怎么处理 现在这种情况我们要删除的结点6只有一个孩子而6被删除的话它的父亲结点3就只剩下一个孩子了而二叉树中一个结点最多可以有两个孩子所以6被删除之后我们是不是可以把它的孩子7托管给6的父亲3的右孩子结点啊。 不一定都是托给右要进行判断要看被删除结点是父结点的左还是右孩子 要删除的结点只有左孩子结点右为空 比如我们现在要删除14 那这种情况处理方法其实和上一个一样也是把被删除结点的孩子托管给其父亲结点那这里也是托给父亲的右孩子。 另外其实第一种情况也可以归到第二种或第三种里面第一种是两个孩子都为空那也可以归到左为空或者右为空的情况里面。 要删除的结点有左、右孩子结点 比如我们要删除3或8怎么删 首先这里我们上面用到的托管给父结点的方法就不管用了因为每个结点最多管两个孩子而现在要删除的这个结点就有两个孩子如果父亲原本就有两个那这样父亲要管三个就超了。 况且对于8也就是根结点来说它根本没有父结点。 那这种情况该如何处理呢 对于这种情况我们使用的方法叫做——替换法删除法/伪删除法 以删除8为例大家看如果把8删了谁能够坐到8这个位置呢 那对于8这棵树来说其实这个替代者可以有两个人选 左子树的最大值右子树的最小值 那对于当前这棵树其实就是7或者10。 其实仔细观察我们会发现对于一棵搜索二叉树来说 整棵树中最大的结点就是最右边的那个结点最小的结点就是最左边的那个结点。 那对于子树来说也是这样我们看到7其实就是左子树的最右边的结点10就是右子树最左边的结点。 所以这里要想8可以选择用7替换也可以用10。 以用7为例怎么进行替换删除呢 把7这个结点的值赋给8这个结点然后把原始的7结点删除了就行了 那总结一下 虽然上面我们分析了四种情况但是我们说了第一种即被删除结点没有孩子的情况可以归到左为空或者右为空的情况里面。 所以总共有三种 左为空右为空 这两种都是托管但注意具体的代码处理是不一样的因为一个右为空一个左为空。左右都不为空 替换删除/伪删除法 5.2 代码实现
那下面写一下代码吧
首先我们得查找要删除的元素 那接下来就是实现删除的逻辑了
左为空或者右为空得删除其实比较好处理托管给父亲结点即可 最后来实现一下比较难搞的替换删除 那我们上面说了这个替换结点可以是左数得最大结点最右边的那个结点也可以是右树得最小结点最左边。 那这里我选择右树的最小结点。 这里的替换删除分为两步 第一步——找到右树最小结点然后替换要删除的结点 第二步——删除替换结点 那这里其实有一些需要注意的地方 我们在这里选择的是右树的最小结点即右子树最左边的结点那既然是最左边他一定没有左孩子了但是它可能会有右孩子。 比如像这样 所以这里删除替换结点也要用托管的方式去删那就需要保存一下替换结点的父亲 那这里还有一些需要特别注意的点 首先我问大家现在不是需要保存替换结点的父结点吗这个父结点的初始值可以给nullptr吗 如果看上面那个例子是可以的因为会进入循环更新parent的值。 但是如果是这样的情况呢 大家看这种情况是不是不会进入while循环啊所以pminRight不会更新那后面托管的时候就会对空指针解引用所以这里初始值可以赋cur即要进行删除的那个结点伪删除。 Node* pminRight cur; 另外我们上面的那个例子 就这个最终托管的时候是链接到父亲的左子树上但是不要认为这里找到是最左结点就一定链接到左子树上。 我们现在这个例子 是不是就是链接到pminRight的右子树上了所以要去看minRight即替换结点在pminRight的那边。 所以补充完毕应该是这样的 最终删除成功就return true。 但是呢其实改到现在还有一个问题 我们能看出来这个测试结果是不正确的。 问题出在哪里呢 我们直接删除根是没什么问题的现在 但是如果这样 大家看这种其实就是挂了我们见过很多次了调试一下 出现了一个空指针异常这里是在删除8的时候跳出来这个异常的怎么回事呢 我们来分析一下 这次我们先删除了10、14、13所以在删除8的时候是这样的 那为什么此时再去删除8就出现parent是空指针的情况呢 那问题在于 现在要删8是右为空的情况 因为根结点没有父亲结点。 那我们怎么解决呢 那对于这种情况我们可以单独处理一下其实可以直接更改一下根结点直接让3成为新的根然后把8删了就行 那然后我们再来测试 就可以了随便删 bool Erase(const K key)
{Node* parent nullptr;Node* cur _root;while (cur){if (key cur-_key){parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}else{//key cur-_key就是找到了进行删除//1.左为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (cur parent-_left)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;}//2.右为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_left)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;}else//左右都不为空{//这里选择右树的最小结点最左边替换Node* pminRight cur;Node* minRight cur-_left;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;//删除替换结点if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight;}return true;}}//找不到直接返回falsereturn false;
}那搜索二叉树主要的操作其实就这些但是呢我们上面都是用循环实现的那搜索二叉树这里呢其实也可以用递归去搞这三个操作的递归实现我们也有必要去学一下。
6. 查找递归版本
查找用递归要怎么写呢 在类里面定义的递归一般我们都要套一层写成这种原因就和我们上面写中序遍历那里一样。 6.2 思路分析
那具体怎么实现呢 我们来分析一下 首先来回顾一下递归的思想 它通常把一个大型复杂问题层层转化为一个与原问题相似的规模较小的问题来求解每个子问题都可以进一步分解为更小的子问题直到达到基本情况终止条件然后逐层返回结果最终得到整个问题的解。 所以这里的思路是这样的 查找嘛那就从根结点开始如果大于根结点的值就转换为去右子树里面查找如果小于根结点就转换为去左子树查找如果等于就直接返回那对于子树也是这样一步步转换为子问题。 如果最后都没找到一直到空那就返回false。 那我们写一下代码
6.2 代码实现
这个没什么难度我就直接上代码了
bool FindR(const K key)
{return _FindR(_root, key);
}bool _FindR(Node* root, const K key)
{if (root nullptr)return false;if (key root-_key){return _FindR(root-_left, key);}else if (key root-_key){return _FindR(root-_right, key);}else{retrun true;}
}试一下 7. 插入递归版本
7.1 思路分析 那插入用递归怎么做呢 那也是类似的思路从根节点开始如果要插入的结点大于根就转换为去右子树插入如果要插入的结点小于根就转换为去左子树插入如果相等返回flase如果一直走到空那就就在该位置插入就行了。 7.2 代码实现 但是有一个问题我们找到空插入的时候如何和它的父亲链接起来 我们可能会想到这样的方法比如把父亲作为递归的参数进行传递或者去判断root的子树为空而不是它本身为空。 但是最好的方法我觉得是这样 直接用root的引用就可以了。 因为引用的话走到空他就是那个位置指针的引用直接赋给它就链接上了。 还不用像上面循环实现的那样去判断要连接到那边。 那大家思考一下我们上面循环的方式可以用引用吗 不可以的因为C中的引用是不能改变指向的引用一旦引用一个实体之后就不能再引用其他实体 而这里递归的话每次递归都相当于创建了一个新的引用而不是改变上一层的引用的指向。 测试一下 8. 删除递归版本
然后是删除
8.1 思路分析
怎么实现呢 那其实大致的思路还是一样的从根结点开始判断如果要删除的值大于根转换为去右子树删小于根转换为去左子树删等于就进行删除如果走到空那就是找不到。 所以关键还是在于如何进行删除。 8.2 代码实现
那我们来分析一下 其实还是我们上面分析的那三种情况 左为空、右为空或者左右都不为空。 那这里我们用引用写起来还是比较简便的。 先写一下左为空和右为空的情况这两个比较好处理 然后看一下比较麻烦的左右都不为空的情况 我们之前非递归版本的实现是找一个符合条件的结点替换它然后把替换的结点删除掉 这里也可以用同样的方法但我觉得比较简便的方法是这样的 还是先找一个可以替代要删除结点的结点左子树最大结点或右子树最小以左子树最大结点替换为例 交换它们两个的值然后删除左子树里面的8key这个结点就行了 测试一下 没问题 bool EraseR(const K key)
{return _EraseR(_root, key);
}bool _EraseR(Node* root, const K key)
{if (root nullptr)return false;if (key root-_key){return _EraseR(root-_left, key);}else if (key root-_key){return _EraseR(root-_right, key);}else{//删除Node* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{Node* maxLeft root-_left;while (maxLeft-_right){maxLeft maxLeft-_right;}swap(maxLeft-_key, root-_key);return _EraseR(root-_left, key);}delete del;return true;}
}9. 其它相关成员函数的实现
如果我们想在相对搜索二叉树的对象进行拷贝构造可以吗 是可以的虽然我们没写但是拷贝构造属于默认成员函数编译器会自动生成不过默认生成的只完成浅拷贝。 现在没有报错的原因是因为我们没写析构如果有析构就会出问题因为搜索二叉树涉及资源申请这样如果是浅拷贝的话在析构的时候就会对一块空间析构两次所以就会出问题。 这都是我们之前学过的内容。 9.1 析构
那我们可以先来写一下析构。
那析构的话我们这里还是用递归来搞也可以用循环但是比较麻烦 那实现一下Destory就行了关于二叉树的销毁我们初阶也讲过比较好的做法是后续销毁 那现在不出意外有了析构我们的浅拷贝就要出错了 调式一下 9.2 构造和拷贝构造
那我们就来写一个深拷贝的拷贝构造我们还是用递归来实现 那也比较简单先序去拷贝创建就行了 那有了拷贝构造我们得实现一下构造函数 因为现在有了拷贝构造编译器就不会生成默认的构造函数了那就需要我们自己写了 另外C11有一个关键字——default可以强制编译器生成默认构造这个我们后面也会讲 那有了默认构造我们下面给了缺省值它走初始列表的时候就会用缺省值去初始化。 现在就可以了。 9.3 赋值重载
那赋值重载我们也搞一下吧
跟我们之前玩的一样
BSTreeK operator(const BSTreeK t)
{swap(_root, t._root);return *this;
}那关于搜索二叉树的实现差不多就到这里了
10. 完整代码
gitee
10.1 BSTree.h
#pragma oncetemplate class K
struct BSTreeNode
{BSTreeNode(const K key):_left(nullptr),_right(nullptr),_key(key){}BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;
};template class K
class BSTree
{typedef BSTreeNodeK Node;
public:bool Insert(const K key){if (_root nullptr){_root new Node(key);return true;}Node* parent nullptr;Node* cur _root;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为空就是key应该插入的位置cur new Node(key);//链接if (key parent-_key)parent-_left cur;if (key parent-_key)parent-_right cur;return true;}bool 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 true;}}return false;}bool Erase(const K key){Node* parent nullptr;Node* cur _root;while (cur){if (key cur-_key){parent cur;cur cur-_left;}else if (key cur-_key){parent cur;cur cur-_right;}else{//key cur-_key就是找到了进行删除//1.左为空if (cur-_left nullptr){if (cur _root){_root cur-_right;}else{if (cur parent-_left)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;cur nullptr;}//2.右为空else if (cur-_right nullptr){if (cur _root){_root cur-_left;}else{if (cur parent-_left)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;cur nullptr;}else//左右都不为空{//这里选择右树的最小结点最左边替换Node* pminRight cur;Node* minRight cur-_left;while (minRight-_left){pminRight minRight;minRight minRight-_left;}cur-_key minRight-_key;//删除替换结点if (pminRight-_left minRight){pminRight-_left minRight-_right;}else{pminRight-_right minRight-_right;}delete minRight;minRight nullptr;}return true;}}//找不到直接返回falsereturn false;}void InOrder(){_InOrder(_root);cout endl;}bool 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);}/*BSTree():_root(nullptr){}*/BSTree() default;~BSTree(){Destory(_root);}BSTree(const BSTreeK t){_root copy(t._root);}BSTreeK operator(const BSTreeK t){swap(_root, t._root);return *this;}
protected: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;}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 (key root-_key){return _EraseR(root-_left, key);}else if (key root-_key){return _EraseR(root-_right, key);}else{//删除Node* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else{Node* maxLeft root-_left;while (maxLeft-_right){maxLeft maxLeft-_right;}swap(maxLeft-_key, root-_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 (key root-_key){return _InsertR(root-_right, key);}else if (key root-_key){return _InsertR(root-_left, key);}else{return false;}}bool _FindR(Node* root, const K key){if (root nullptr)return false;if (key root-_key){return _FindR(root-_left, key);}else if (key root-_key){return _FindR(root-_right, key);}else{return true;}}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_key ;_InOrder(root-_right);}
private:Node* _root nullptr;
};10.2 BSTree.cpp
#define _CRT_SECURE_NO_WARNINGS
#include iostream
using namespace std;
#include BSTRee.hvoid BSTreeTest1()
{BSTreeint t1;int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e:a){t1.Insert(e);}t1.InOrder();cout t1.FindR(10) endl;cout t1.FindR(19) endl;}
void BSTreeTest2()
{BSTreeint t1;int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a){t1.Insert(e);}t1.InOrder();t1.Erase(10);t1.InOrder(); t1.Erase(14);t1.InOrder();t1.Erase(13);t1.InOrder();t1.Erase(8);t1.InOrder();for (auto e : a){t1.Erase(e);t1.InOrder();}
}
void BSTreeTest3()
{BSTreeint t1;int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a){t1.InsertR(e);}t1.InOrder();for (auto e : a){t1.EraseR(e);t1.InOrder();}}
void BSTreeTest4()
{BSTreeint t1;int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto e : a){t1.InsertR(e);}t1.InOrder();BSTreeint t2t1;t2.InOrder();}
int main()
{BSTreeTest4();return 0;
}
