数据结构笔记–二叉查找树 (一)基本概念 二叉查找树也叫二叉搜索树或是二叉排序树，它的规则如下：左子树中的所有结点的值，均小于其根节点的值。右子树中所有结点的值，均大于其根节点的值。由这两个规则，我们也可以知道，二叉搜索树的子树也是二叉搜索树。
二叉查找树举例
(二)具体实现： (1)首先我们依旧定义一下基本的结构体： (2)插入操作： 插入操作的实现很简单。首先和根节点比较，如果它的值比根节点小，则对它的左子树递归调用，并将递归调用的结果赋给它的左子树。反之，则对它的右子树递归调用，并将递归调用的结果赋给它的右子树。 这样下去后，总会遇到root -> left == NULL或者root -> right == NULL的情况。这个时候，说明我们找到需要插入的地方了，我们此时创建新结点即可。 (3)删除操作： 删除操作有两种情况需要考虑。 第一种情况(需要删除的结点没有左右孩子)：如下图所示，我们需要删除24这个结点。此时我们只需要找到他，然后将其删除。
第二种情况(需要删除的结点有一个孩子)：如上图所示，我们要删除22这个结点。此时我们找到22这个结点将其删除后，还需要将它的孩子(24)连上去(28)。 第三种情况(需要删除的结点有两个孩子–即左右孩子都有)：这个时候我们有两种选择。第一种是选取其左子树中最大的结点上位，第二种是选取其右子树中的最小结点上位。我们此处以第一种方法为例。比如我们需要删除28这个结点，但是它有两个孩子，那么我们找到左子树中的最大结点(24)，将其值覆盖28。然后对24递归调用删除函数，此时则变为了情况一，也即没有孩子的情况，直接删除即可。 在第三种情况中，我们需要找到左子树上的最大结点，所以我们需要一个函数来帮助我们实现： 然后就是删除的代码： (4)查找操作： 看完删除操作后，查找操作就很简单了，所以我们直接给出代码：
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/25928.html
