复习数据结构做的笔记：

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

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

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

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

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

1. 12>2^3，即最大能画出3层的满二叉树，接着将剩余5个结点插入该树
   

2. 先插入h，a的左右子树结点个数都为3，则到c，c的左右子树结点个数都为1，接着到g，g的左右子树都为0，最后h到了g的右边
   

3. 先插入i，a的左子树结点个数为3小于右子树的4，则到b，b的左右子树结点个数都为1，接着到e，e的左右子树都为0，最后i到了e的右边
   

同理后面插入J,K,L

折半查找判定树就完成了

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

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

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

​