问题 单项选择题

下面关于二叉排序树的叙述中,错误的是()。

A.对二叉排序树进行中序遍历,必定得到节点关键字的有序序列

B.依据关键字无序的序列建立二叉排序树,也可能构造出单支树

C.若构造二叉排序树时进行平衡化处理,则根节点的左子树节点数与右子树节点数的差值一定不超过1

D.若构造二叉排序树时进行平衡化处理,则根节点的左子树高度与右子树高度的差值一定不超过1

答案

参考答案:C

解析:

[要点解析] 二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树。

(1)若左子树不空,则左子树上所有节点的值均小于它的根节点的值。

(2)若右子树不空,则右子树上所有节点的值均大于它的根节点的值。

(3)左、右子树也分别为二叉排序树。

中序遍历二叉树,即是先遍历左子树,再访问根节点,最后遍历右子树,根据二叉排序树的定义可知,进行中序遍历后,得到有序序列。

而平衡二叉树的是这样的,要求任何一个节点的左、右子树的高度差都不大于1,显然,D选项的说法是正确的,而C选项的说法是不正确的。

单项选择题
单项选择题