数据结构吧 关注：104,490贴子：883,542
- 13回复贴，共1页
解析:
折半查找判定树实际上是一棵二叉排序树，它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素，符合折半查找规则的树即是所求。
选项A符合折半查找规则,因此正确。10个元素时的折半查找判定树应是A答案的图（向上取整）
11个元素时折半查找判定树（向上取整）
其实在代码实现的时候到底用是向下取整，还是向上取整并不重要，只要保持一致性，即要么一直向下取整，要么一直向上取整，就能实现折半查找。
下面是分别是10个与11个元素向下取整实现的折半查找判定树，不难发现其结正好与个数相同的向上取整的判定树水平对称。
技巧：
当表中元素个数为偶数个时，那么折半所产生的子表中，必然会出现两种情况：①前子表比后子表多一个元素（向上取整）；②后子表比前子表多一个元素（向下取整）；那么以这种结构推其后所有的子表应均满足此结构，如果按惯例坚持向上取整的话可以排除D答案。
当表中元素个数为奇数个时，那么折半所产生的子表中，只会产生一种情况，即前后子表元素个数相同，那么以这种结构推其后所有的子表应均满足此结构。折半查找判断树是执行折半查找过程中形成的树，那么他的子树有着相同的结构,但不可能是对称结构。可以排除B、C答案，若二叉树出现例如上题中BC此类关于根节点对称的结构，那么它一定不是折半查找二叉树。
代码：
另外，书上的这个程序与许多网站代码都用的是int mid = (low + high) / 2 来求中位数; 但这名代码low与higth两个加起是基数时，要用靠后面数为中位数，如1，...,10,应取6为中位数，要向上取整用前面的代码无法实现，应该是int mid = (low + high+1) / 2才对的；而int mid = (low + high+1) / 2则是向下取整的代码。
折半查找判定树实际上是一棵二叉排序树，它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素，符合折半查找规则的树即是所求。
选项A符合折半查找规则,因此正确。10个元素时的折半查找判定树应是A答案的图（向上取整）
11个元素时折半查找判定树（向上取整）
其实在代码实现的时候到底用是向下取整，还是向上取整并不重要，只要保持一致性，即要么一直向下取整，要么一直向上取整，就能实现折半查找。
下面是分别是10个与11个元素向下取整实现的折半查找判定树，不难发现其结正好与个数相同的向上取整的判定树水平对称。
技巧：
当表中元素个数为偶数个时，那么折半所产生的子表中，必然会出现两种情况：①前子表比后子表多一个元素（向上取整）；②后子表比前子表多一个元素（向下取整）；那么以这种结构推其后所有的子表应均满足此结构，如果按惯例坚持向上取整的话可以排除D答案。
当表中元素个数为奇数个时，那么折半所产生的子表中，只会产生一种情况，即前后子表元素个数相同，那么以这种结构推其后所有的子表应均满足此结构。折半查找判断树是执行折半查找过程中形成的树，那么他的子树有着相同的结构,但不可能是对称结构。可以排除B、C答案，若二叉树出现例如上题中BC此类关于根节点对称的结构，那么它一定不是折半查找二叉树。
代码：
另外，书上的这个程序与许多网站代码都用的是int mid = (low + high) / 2 来求中位数; 但这名代码low与higth两个加起是基数时，要用靠后面数为中位数，如1，...,10,应取6为中位数，要向上取整用前面的代码无法实现，应该是int mid = (low + high+1) / 2才对的；而int mid = (low + high+1) / 2则是向下取整的代码。
