下列关于二叉排序树的说法正确的是( )。 Ⅰ．向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度 Ⅱ．二叉排序树一定是平衡二叉树 Ⅲ．删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树 Ⅳ．平衡二叉树是指左、右子树

admin2019-12-10 39

问题下列关于二叉排序树的说法正确的是( )。
Ⅰ．向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度
Ⅱ．二叉排序树一定是平衡二叉树
Ⅲ．删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树
Ⅳ．平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树

选项 A、Ⅰ、Ⅱ、Ⅳ
B、Ⅱ、Ⅲ、Ⅳ
C、Ⅰ、Ⅳ
D、全错

答案D

解析 Ⅰ:根据二叉排序树插入操作的步骤可知，比较次数最坏情况下等于树的高度，所以I错误。
Ⅱ：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的二叉树，此时明显不是平衡二叉树，所以Ⅱ错误。
Ⅲ：不一定可以得到以前的排序二叉树。例如，给出一个二叉排序树，如图3—8所示。此时删除结点3，二叉排序树变为图3—8b，再插入结点3，变为图3—8c。显然图3—8a和图3—8c不是同一个二叉排序树，所以Ⅲ错误。