浙江大学-数据结构-二叉搜索树4.1.1 由于我只要写ElasticSearch的json搜索接口，现在导数据，还是利用点零碎时间来学习数据结构2333。。。 什么是二叉搜索树 查找问题静态查找与动态查找针对动态查找，数据如何组织 静态查找：找的集合的素是不动的，也就是在一个集合上主要做的是find操作，而没有delete, insert这种操作发生。 另外一种查找呢，就是我们要找的对象集合本身会动态的发生变化，也就是经常要发生插入删除，除了查找之外，还有插入删除发生。 静态查找问题呢，我们前面提到过，一个很好的方法，就是二分查找，二分查找把一般查找的时间复杂性
降到了 ,为什么二分查找效率这么好，其中很重要的原因，我们把要查找的数据事先进行了有效的组织，把它有序化，这样的话，给定了n个数，我们查找的顺序可以形成判定树这样的一种结构，所以把一个线性的查找过程，变成一个类似树的查找过程，而它的查找效率就是树的高度，所以从这里面我们得到一个启示，有没有可能直接把素就放到树上，不要放在数组里面，放在树上的一个好处，树的动态性比较强，要插入删除比在线性里面做要方便，这就是我们要讲的二叉查找树，或者叫二叉搜索树。 我们怎么把素放在树上面，从前面我们的判定树里面我们可以得到一个启示，我们有没有可能把数据按这种方式来组织，也就是树上的任何一个节点，它的值比所有左子树的值都要来的大，比右子树的所有节点值都要来的小，这样我们的查找过程就变成对当前结点的一个判断，是大于，小于，还是等于，等于就找着了，如果比当前的根结点要小，那么我们就到左边去找，如果比它大，到右边去找，这样也能把我们的查找过程缩小一大部分。所以这就是我们所说的二叉搜索树。 二叉搜索树（BST, Binary Search Tree), 也称二叉排序树或二叉查找树 二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：非空左子树的所有键值小于其根结点的键值。非空右子树的所有键值大于其根结点的键值。左，右子树都是二叉搜索树。
因为5这个结点比10小，二叉搜索树的右子树应该比根结点大。
这里的所有结点数都满足。
二叉搜索树操作的特别函数：
二叉搜索树的查找操作：Find 查找从根结点开始，如果树为空，返回NULL 若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：若X小于根结点键值，只需在左子树中继续搜索；如果X大于根结点的键值，在右子树中进行继续搜索；若两者比较结果是相等，搜索完成，返回指向此结点的指针。
这里是用递归的方式来实现，递归实现的方式不是很高，而且我们注意到，这种递归叫尾递归，就是在程序分支的最后，需要返回的时候实现递归。从编译的角度来讲，尾递归都可以用循环来进行实现 由于非递归函数的执行效率高，可将”尾递归”函数改为迭代函数 查找的效率决定于树的高度 因为我们可能一直找，找到叶结点为止，而对同样的n个结点来讲，树的高度跟树的结构是很有关系的，如果树的结构不好，都只有左儿子，没有右儿子，全部串在一起，形成一条链，往左边倾斜，它的高度是n-1,这是最坏的情况，当然还有一种情况大家都往右边靠，那么就是在右边形成一条链，那这就达到我们想要的log(n)这样的一种效果，所以总的来讲我们希望树看起来比较平衡，就不往一边倒，所以这就是我们后面要提到的一个重要的议题，叫平衡二叉树 查找最大和最小素 最大素一定是在树的最右分枝的端结点上 最小素一定是在树的最左分枝的端结点上
查找最小素的递归函数 查找最大素的迭代函数
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/39935.html
