参考答案：

解析：假设判定树的内部结点的总数为n=2^h-1。则判定树是深度为h=lg(n+1)的满二叉树，树中第k层上的结点的个数为2^h-1，查找它们所需要比较的次数是k。则在等概率下，二分查找成功时的平均查找长度为：，如果n很大，则可以用如下近似公式：lg(n+1)-1，作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上，所以n个结点的判定树的深度和n个结点的完全二叉树的深度相同，即为lg(n+1)，所以，二分查找的最坏性能和平均性能十分接近。