题1

题1

题目

对于二叉排序树, 下面的说法中, ( ) 是正确的.
A. 二叉排序树是动态树表, 查找失败时插入新结点, 会引起树的重新分裂和组合
B. 对二叉排序树进行层序遍历可得到有序序列
C. 用逐点插入法构造二叉排序树, 若先后插入的关键字有序, 二叉排序树的深度最大
D. 在二叉排序树中进行查找，关键字的比较次数不超过结点数的

分析

二叉排序树的查找效率一般是，但是如果是挂成了一个链，也就是说二叉排序树退化成了一个链表，那么查找效率就是。所以选项C是正确的
那么显然D就是错的，C是对的

解

C
二叉排序树插入新结点时不会引起树的分裂组合。对二叉排序树进行中序遍历可得到有序序列。当插入的关键字有序时, 二叉排序树会形成一个长链, 此时深度最大。在此种情况下进行查找, 有可能需要比较每个结点的关键字, 超过总结点数的 。