2. 计算机
  3. 下面关于二叉排序树的叙述，错误的是(27)。

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

admin2010-05-22  65
问题 下面关于二叉排序树的叙述，错误的是(27)。
选项 A、对二叉排序树进行中序遍历，必定得到节点关键字的有序序列
B、依据关键字无序的序列建立二叉排序树，也可能构造出单支树
C、若构造二叉排序树时进行平衡化处理，则根节点的左子树节点数与右子树节点数的差值一定不超过1
D、若构造二叉排序树时进行平衡化处理，则根节点的左子树高度与右子树高度的差值一定不超过1
答案C
解析 本题考查数据结构方面的基础知识。
   二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：
   ①若它的左子树非空，则其左子树上所有节点的关键字均小于根节点的关键字：
   ②若它的右子树非空，则其右子树上所有节点的关键字均大于根节点的关键字；
   ③左、右子树本身就是两棵二叉排序树。
   由上述定义可知，二叉排序树是一个有序表，对二叉排序树进行中序遍历，可得到一个关键字递增排序的序列。
   对于给定的关键字序列，可从空树开始，逐个将关键字插入树中，来构造一棵二叉排序树。其过程为：每读入一个关键字值，就建立一个新节点。若二叉排序树非空，则将新节点的关键字与根节点的关键字相比较，如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空树，则新节点作为二叉排序树的根节点。
   显然，若关键字初始序列已经有序，则构造出的二叉排序树一定是单枝树(每个节点只有一个孩子)。
   为了使在二叉排序树上进行的查找操作性能最优，构造二叉排序树时需进行平衡化处理，使每个节点左、右子树的高度差的绝对值不超过1。
转载请注明原文地址:https://www.kaotiyun.com/show/WnTZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

数据库系统工程师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)