在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过（）

在平衡二叉树中，(55)。

A．任意结点的左、右子树结点数目相同

B．任意结点的左、右子树高度相同

C．任意结点的左、右子树高度之差的绝对值不大于1

D．不存在度为1的结点

由关键字序列(12，7，36，25，18，2)构造一棵二叉排序树(初始为空，第一个关键字作为根结点插入，此后对于任意关键字，若小于根结点的关键字，则插入左子树中，若大于根结点的关键字，则插入右子树中，且左、右子树均为二叉排序树) ，该二叉排序树的高度(层数)为 ( ) 。

A. 6

B. 5

C. 4

D. 3

请帮忙给出正确答案和分析，谢谢!

● 关于二叉排序树的说法，错误的是 （27） 。

（27）

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

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

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

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

●在一棵非空二叉排序树中，关键字最小的结点的( )。

A．左子树一定为空、右子树不一定为空

B．左子树不一定为空、右子树一定为空

C．左子树和右子树一定都为空

D．左子树和右子树一定都不为空

从供选择的答案中选出应填入下列叙述中()内的正确答案：

在二叉排序树中，每个结点的关键码值(A)，(B)一棵二叉排序树，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称做最佳二叉排序树，最佳二叉排序树在结构上的特点是(C)。

供选择的答案

A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小

②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大

③比左右子树的所有结点的关键码值大

④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系

B：①前序遍历 ②中序(对称)遍历

③后序遍历 ④层次遍历

C：①除最下二层可以不满外，其余都是充满的

②除最下一层可以不满外，其余都是充满的

③每个结点的左右子树的高度之差的绝对值不大于1

④最下层的叶子必须在左边

●二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行 （42)遍历，可得到一个结点元素的递增序列

（42）

A. 先序（根、左、右）

B. 中序（左、根、右）

C. 后序（左、右、根）

D. 层序（从树根开始，按层次）

对一棵二叉树的中序遍历序列中，根结点右边的结点属于( )。

A．左子树上的叶子结点

B．右子树上的所有结点

C．左子树上的所有结点

D．右子树上的叶子结点

A.左、右子树的高度均相同

B.左、右子树高度差的绝对值不超过1

C.左、右子树的结点数均相同

D.左、右子树结点数差的绝对值不超过1

下图所示平衡二叉树(树中任一结点的左右子树高度之差不超过1)中，结点A的右子树AR高度为h，结点B的左子树BL高度为h，结点C的左子树CL、右子树CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加1，则该二叉树(61)。

A．以B为根的子二叉树变为不平衡

B．以C为根的子二叉树变为不平衡

C．以A为根的子二叉树变为不平衡

D．仍然是平衡二叉树

在平衡二叉树中，(6)。

A．任意节点的左、右子树节点数目相同

B．任意节点的左、右子树高度相同

C．任意节点的左、右子树高度之差的绝对值不大于1

D．不存在度为1的节点