永发信息网

二叉判定树怎么画,画出对长度为10的有序表进行折半查找的判定树

答案:1  悬赏:50  手机版
解决时间 2021-07-28 07:36
二叉判定树怎么画,画出对长度为10的有序表进行折半查找的判定树
最佳答案
长度为n的折半查找判定树的构造方法为:
⑴ 当n=0时,折半查找判定树为空;
⑵ 当n>0时,折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树,根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。
题目中 长度为10的折半查找判定树的具体生成过程为:
⑴ 在长度为10的有序表中进行折半查找,不论查找哪个记录,都必须先和中间记录进行比较,而中间记录的序号为(1+10)/2=5(注意是整除即向下取整),即判定树的根结点是5,如图(a)所示;
⑵ 考虑判定树的左子树,即将查找区间调整到左半区,此时的查找区间是[1,4],也就是说,左分支上为根结点的值减1,代表查找区间的高端high,此时,根结点的左孩子是(1+4)/2=2,如图(b)所示;
⑶ 考虑判定树的右子树,即将查找区间调整到右半区,此时的查找区间是[6,10],也就是说,右分支上为根结点的值加1,代表查找区间的低端low,此时,根结点的右孩子是(6+10)/2=8,如图(c)所示;
⑷ 重复⑵⑶步,依次确定每个结点的左右孩子,如图(d)所示。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
句子The marathon is the longest race at th
从下列每组单词中找出画线部分读音与其余三个
传统文化感谢捐款语句,给朋友买的礼物上刻一
As we can see from the second chart that t
下列等式一定成立的是,下列不等式一定成立的
你有高中3500英语单词的mp3 要读完英文又读中
甘甜的拼音是什么,甜的读音是什么
一竖一撇有什么字,一点一竖一撇是什么手旁
有关于秋天的现代诗歌,现代版有关秋天的诗词
某工程需要在规定日期内完成,如果甲工程队单
超市运来一批大米,第一天卖出总数的3分之1,第
巨型古牧犬多少钱一只,古牧属于巨型犬么
回忆少年时代的句子,回忆少年时代的往事的诗
飞机燃烧什么油,飞机烧的是什么油
谁帮我翻译下 谢谢Thank you for contacting
推荐资讯
马桶吸盘怎么用视频,马桶揣子怎么用
不给玻璃加热时,小灯泡不会发光,当给玻璃加热
最让你心酸的情话,说一句你认为最好听的情话
道教最高境界除了飞升,还有别得吗?
求一歌名有歌词I LOVE YOU男的唱的
My brother is a person who collects coins.
诺基亚 5320diXM和诺基亚 6121c 那一款性价比
电视购物上和市场卖的钛锗磁的链子有效吗?
大学生活有点无聊,谁能帮我找点事情做呀…
关于柠檬片的用法..
现在有在用电脑提问上吗?
你最喜欢的歌告诉我好吗?
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?