数据结构折半查找判定树的画法(较简单易懂!)
发布于 3 年前 作者 gangtian 723 次浏览 来自 分享

复习数据结构做的笔记:

折半查找判定树的画法思路:

1. 先画出满足有序表长度的最大满二叉树,然后将剩下的结点个数一个个插入该树

2. 从上往下看,比较每个结点的左右子树结点个数,如果左右子树结点个数相同优先放右边,左边比右边少就放左边,直到往下塞到二叉树底部成为叶子结点。

对于步骤1和2的具体做法,见下列实例分析:

长度为12的有序表画出折半查找判定树

12>2^3,即最大能画出3层的满二叉树,接着将剩余5个结点插入该树  
![](https://image.wxopen.club/content_754bd490-50a8-11ec-8083-001a7dda7111.png)
先插入h,a的左右子树结点个数都为3,则到c,c的左右子树结点个数都为1,接着到g,g的左右子树都为0,最后h到了g的右边  
![](https://image.wxopen.club/content_756ad0a8-50a8-11ec-9c57-001a7dda7111.png)
先插入i,a的左子树结点个数为3小于右子树的4,则到b,b的左右子树结点个数都为1,接着到e,e的左右子树都为0,最后i到了e的右边  
![](https://image.wxopen.club/content_75b4f8e1-50a8-11ec-82d3-001a7dda7111.png)

同理后面插入J,K,L


折半查找判定树就完成了

如果要求各元素查找概率相同的情况下平均查找长度,则

n=(1*1+2*2+4*3+5*4)/12=37/12

觉得该篇文章有用的请不要忘记忘记点击左下角的大拇指~

3 回复

大拇指点了

能折半查找的话,不应该是比较待插入结点和当前结点的值之间的大小,来决定应该落到左子树还是右子树吗?

二叉树的定义不是某节点一边子树不大于该节点,另一边不小于该节点吗,如果按字母顺序定大小,树的结构就不是这样的了。为了构造最优二叉树,根节点应该是最近中间值那个。

回到顶部