问题
单项选择题
下面关于二叉排序树的叙述中,错误的是()。
A.对二叉排序树进行中序遍历,必定得到节点关键字的有序序列
B.依据关键字无序的序列建立二叉排序树,也可能构造出单支树
C.若构造二叉排序树时进行平衡化处理,则根节点的左子树节点数与右子树节点数的差值一定不超过1
D.若构造二叉排序树时进行平衡化处理,则根节点的左子树高度与右子树高度的差值一定不超过1
答案
参考答案:C
解析:
[要点解析] 二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树。
(1)若左子树不空,则左子树上所有节点的值均小于它的根节点的值。
(2)若右子树不空,则右子树上所有节点的值均大于它的根节点的值。
(3)左、右子树也分别为二叉排序树。
中序遍历二叉树,即是先遍历左子树,再访问根节点,最后遍历右子树,根据二叉排序树的定义可知,进行中序遍历后,得到有序序列。
而平衡二叉树的是这样的,要求任何一个节点的左、右子树的高度差都不大于1,显然,D选项的说法是正确的,而C选项的说法是不正确的。