折半查找的判定树-Toy模板网

这篇具有很好参考价值的文章主要介绍了折半查找的判定树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

定义

二叉判定树是用于描述解决问题的思路，比如可以使用判定树描述N个数的比较过程，是一种对过程的描述。
它也可以用于描述二分查找（即折半查找，以下都作二分查找）的过程。

描述二分查找的二叉判定树，我们也可以叫折半查找判定树，
从这样的判定树，我们可以分析二分查找算法的效率

当n=0时，折半查找判定树为空；
当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。

首先找根节点：mid = （18+1） / 2 = 9 （向下取整）

判断左子树：左子树的查找范围是（1 ~ 8），mid = ( 1 + 8 ) / 2 = 4

判断右子树：右子树的查找范围是（10 ~ 18），mid = ( 10 + 18 ) / 2 = 14

递归进行下去，得到结果：

折半查找的判定树

平均查找长度：（1 + 2*2 + 4*3 + 8*4 + 3*5）/ 18 = 32 / 9

我们刚刚做出的这个判定树是采取了向下取整，但向上向下都是可以的，

必须注意的一点是：在一颗判定树中，要向下取整，全都向下取整，不能混有向上取整

折半查找判定树的中序遍历，刚好是原来那些数排好序的样子文章来源地址https://www.toymoban.com/news/detail-481407.html

到了这里，关于折半查找的判定树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！