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

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

admin2022-06-07  37
问题 下列关于二叉排序树的说法正确的是(    )。
    Ⅰ．向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度
    Ⅱ．二叉排序树一定是平衡二叉树
    Ⅲ．删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树
    Ⅳ．平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树
选项 A、Ⅰ、Ⅱ、IV
B、Ⅱ、Ⅲ、Ⅳ
C、Ⅰ、Ⅳ
D、全错
答案D
解析 Ⅰ：根据二叉排序树插入操作的步骤可知，比较次数最坏情况下等于树的高度，所以I错误。
    lI：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的二叉树，此时明显不是平衡二叉树，所以Ⅱ错误。
    Ⅲ：不一定可以得到以前的排序二叉树。例如，给出一个二叉排序树，如图3-7所示。此时删除结点3，二叉排序树变为图3．7b，再插入结点3，变为图3-7c。显然图3-7a和图3—7c不是同一个二叉排序树，所以Ⅲ错误。

    Ⅳ：根据平衡二叉树的概念可知，该说法是错误的，应该改为：平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉排序树(出此选项的目的是让大家记住平衡二叉树默认是二叉排序树)，所以Ⅳ错误。
    可能疑问点：为什么有些教材定义平衡二叉树还是二叉树，而不是二叉排序树?
   提示：首先不管教材是怎么定义的，因为考研大纲没有指定教材，所以考生只能依靠大纲解析为准，如果以前认为平衡二叉树不一定是二叉排序树就把这种思想改变过来吧。
    补充知识点：关于二叉排序树、完全二叉树、平衡二叉树、堆之间的关系。
    (1)首先堆的建立永远都是从最后开始插，所以堆一定是完全二叉树。
    (2)完全二叉树不一定是平衡二叉树，平衡二叉树也不一定是完全二叉树。因为平衡二叉树是有序的，而完全二叉树不一定有序，所以完全二叉树不一定是平衡二叉树。平衡二叉树不一定是完全二叉树比较好理解。
转载请注明原文地址:https://kaotiyun.com/show/Jj3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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