折半查找的二叉判定树是不是完全二叉树？为什么？

不一定，完全二叉树是序号和满二叉树一样。二叉判定树不一定序号相同，或者说极少序号相同！

不一定。我们可以递归地来证明。（嫌太繁琐的话，看每段第一句应该能有个大概。。。【】里面的就省了吧）

• 首先，二叉树每个根结点P一定是有序序列｛｛左子树｝，根结点P，｛右子树｝｝的中间值。

• 其次，由于二叉判定树与二分查找紧密联系，所谓中间值从“二分法”mid=（bot+top）/2取得（前提是有序序列，不妨设一维数组a[n]元素非递减，零元素a[0]不用，mid，bot，top为数组下标），直观上就“取奇数序列的正中间，偶数序列前半部分的末尾”（数学知识，就不多讲，随便代入两三个数就知道了）。

• 【例如，奇数情况，｛……，1，2，3，……｝的中间值取为2，｛……，1｝为其左子树，｛3，……｝为其右子树；偶数情况，｛……，8，9，……｝的中间值取为8，｛……｝为其左子树，｛9，……｝为其右子树。（“……”可以为空）】

• 之后，不难发现，对于二叉判定树的任意一个非叶子结点P，只有“同时存在左右子树”和“仅存在右子树”两种情况。

• 又这样的结点P若是出现在倒数第一层、倒数第二层以外的地方，不可能出现“仅有右子树”的情况。【（否则论证结点P一定单独出现的情况）若结点P成对出现，则总层数从原来的k层退化为k-1层，P在倒数第几层也就要重新判断了；若结点P单独出现，P与其兄弟结点上加挂子树的总结点数不同，这与mid的求法矛盾，不可能存在。】

• 故而，【二叉判定树的任意一个非叶子结点P，倒数第二层向上，只有“同时存在左右子树”的情况，而倒数第二层有“同时存在左右子树”和“仅存在右子树”两种情况】。简言之，就是k层二叉判定树，1~k-1层是满二叉树，第k层呢，左结点存在时右结点一定存在，右结点存在时左结点不一定存在。

• 综上所述，具有n个结点的判定树，与具有n个结点的完全二叉树的深度完全相同。

——————————————————————————————————————

不好意思，我也是大二刚学数据结构，这段论证也是看到问题才开始想的，就五分钟左右，有点仓促，如果不严密不要介意哈/laugh.