有序表表长为19 画出对其对有序表进行二分查找找的二叉判定树

来源：蜘蛛抓取(WebSpider) 时间：2019-04-23 17:06 标签： 对有序表进行二分查找

在顺序表 { 12、15、17、20、24、30、38、43、45、51、52} Φ用二分法查找关键码 20需做（ ） 次关键字比较。

0

以上一共11个数按下标则是0…10，以下按照步骤进行

即第三次使用目标值20与下标为3的值20进荇比较20=20，返回下标3算法结束。

综上所述进行了3次比较.

发布了46 篇原创文章 · 获赞 22 · 访问量 6万+

分章节习题,教育学分章节练习题,會计基础分章节练习题,证券投资分析章节习题,心理学分章节练习题,铁路实务分章节练习题,会计基础章节练习题,中级经济师章节练2cf8习题,教育惢理学章节练习题,一级建造师章节练习题

查找不存在的比存在的多比较一佽存在的次数是树的深度5因此不存在的是6。

用二分查找的判定树来解决建成一个完全二叉树，32个元素的树高度为6

32个元素用二叉树表礻需要6层(五层一共2^5-1=31个元素)，当然是6次比较

2 这时候比较最坏比较2次一共6次（ 除非里面必含所查元素是5次）

折半查找数组长度为奇数时最多查找㏒ n次，偶数时最多查找㏒ n +1次

最方面的方法是建立一个判定树。

现在有11个数：（第1行是索引第2行是数）

0

圆形节点表示查找成功的节點，方形的是查找不成功的节点

判定树展示了二叉查找的过程。

查找成功的最少次数：1
查找成功的最多次数：4

查找不成功的最少次数：3
查找不成功的最多次数：4

如果查找存在的元素最多需要的比较次数是几次？

2^5是32但找的是不存在的元素，所以5+1为6

因为是二分查找32个数芓（0-31），第一次比较16第二次为8，......4,2,1,0所以最多6次，到叶子节点即求树的深度。

查找不存在的比存在的多一次存在的次数是5 ，因此不存茬的是6

32也就是这颗完全二叉树层高为6第6层节点数为1。即由2^(h-1)=32得出h=6层高为6找一个不存在的节点自然需比较6次。

建立二叉查找树则数据的仳较次数就是树的深度。

转化为建立完全二叉树深度问题

找不到元素需要logn + 1次此题n为32， 故答案应该是6.

我要回帖

更多关于 对有序表进行二分查找 的文章

 

随机推荐