数据结构折半查找判定树的画法(较简单易懂!)
复习数据结构做的笔记:
折半查找判定树的画法思路:
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
觉得该篇文章有用的请不要忘记忘记点击左下角的大拇指~