Question

以下关于二叉排序树（或二叉查找树、二叉搜索树）的叙述中，正确的是（　　）。

A.对二叉排序树进行先序、中序和后序遍历，都得到结点关键字的有序序列
B.含有n个结点的二叉排序树高度为log2n+1
C.从根到任意一个叶子结点的路径上，结点的关键字呈现有序排列的特点
D.从左到右排列同层次的结点，其关键字呈现有序排列的特点

Answer 1

【答案】：D
对于二叉排序树的遍历，只有中序遍历可以得到递增的有序序列，而后序遍历和先序遍历都不可以，因此A选项错误。
对于二叉排序树的构造，最差可能会形成单枝树，因此节点数与树的高度，没有绝对的关系，B选项错误。
对于二叉树的路径，只能保证当前节点与其子节点的大小关系，而对于下层节点，并不能保证与其他节点的大小。比如，对于根节点为30，其左孩子为19，右孩子为40；对于19的左孩子为10，右孩子为25；则从30→25，路径为30，19，25，并不是有序序列。因此C选项错误。
对于D选项，对于二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树
那么同层次的节点，右子树大于根节点，根节点大于左子树，则右子树大于左子树，则同层次有序排列。