在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1

题目

在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1

相似考题

1.在AVL树中,任一结点的()。A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左、右子树的结点数均相同D.左、右子树结点数差的绝对值不超过1

2.若一棵二叉树中只有叶结点和左右子树皆非空的结点，设叶结点的个数为k，则左右子树皆非空的结点个数是( )。A．2kB．k-1C．2k-1D．2k-1

3.在平衡二叉树中，(55)。A．任意结点的左、右子树结点数目相同B．任意结点的左、右子树高度相同C．任意结点的左、右子树高度之差的绝对值不大于1D．不存在度为1的结点

4.如果根结点的左子树和右子树高度差不超过1,则该二叉树是平衡二叉树。()此题为判断题(对，错)。

参考答案和解析
正确答案:正确
更多“在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1”相关问题

  • 第1题：

    若一颗二叉树中只有叶结点和左右子树皆非空的结点，设叶结点的个数为n，则左右子树皆非空的结点个数为__________。


    正确答案：
    n-1
    【解析】对任意二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。所谓度为2的结点，在二叉树里面即是左、右子树皆非空，因此，本题答案为n-1。

  • 第2题：

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

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

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

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

    D．仍然是平衡二叉树


    正确答案：C
    解析：本题考查平衡查找树。由于平衡二叉树中任一结点的左右子树高度之差不超过1，因此，若在CR中插入一个结点并使得CR的高度增加1，则结点C的左右子树高度之差为-1，同时以C为根的子树高度增加了1，所以结点B的左右子树高度之差变为-1。如此一来，A的左子树的高度为h+2、右子树的高度为h，根据定义，以A为根的子二叉树变为不平衡。

  • 第3题：

    ●在 (59) 中，任意一个结点的左、右子树的高度之差的绝对值不超过 1。

    (59)

    A．完全二叉树

    B．二叉排序树

    C．线索二叉树

    D．最优二叉树


    正确答案：A

  • 第4题：

    ● 满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为 h(h>1)的满二叉树，其结点总数为 （36） 。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从 1、2、3、…依次编号，则对于树中编号为 i 的非叶子结点，其右子树的编号为 （37） （高度为 3 的满二叉树如下图所示） 。


    正确答案：C,C

  • 第5题：

    以下关于平衡二叉树叙述中，说法错误的是(65)。

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

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

    C．所有节点的平衡因子只可能是-1、0和1

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


    正确答案：A
    解析：平衡二叉树又称为AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子(Balance Factor，BF)定义为该节点的左子树的深度减去其右子树的深度，则平衡二叉树上所有节点的平衡因子只可能是-1、0和1。只要树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。选项A——“任意节点的左、右子树节点数目相同”的说法不正确。

  • 第6题：

    满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为h(h＞1)的满二叉树，其结点总数为(1)。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从1、2、3、…依次编号，则对于树中编号为i的非叶子结点，其右子树的编号为(2)(高度为3的满二叉树如图8-17所示)。

    A．2h

    B．2h-1

    C．2h-1

    D．2h-1+1


    正确答案：C

  • 第7题：

    在平衡二叉树中，()。

    A.任意结点的左右子树结点数目相同
    B.任意结点的左右子树高度相同
    C.任意结点的左右子树高度之差的绝对值不大于1
    D.不存在度为1的结点

    答案：C
    解析：
    该题考查考生对平衡二叉树的理解，形态匀称的二叉树称为平衡二叉树，其严格定义是：一棵空树是平衡二叉树；T是一棵非空二叉树，其左、右子树为TL和TR，令h1和hr分别为左、右子树的深度，当且仅当TL、TR都是平衡=叉树且丨h1-hr丨≤1时，T是平衡二叉树

  • 第8题：

    在（ ）中，任意一个结点的左、右子树的高度之差的绝对值不超过1。

    A.完全二叉树
    B.二叉排序树
    C.线索二叉树
    D.最优二叉树

    答案：A
    解析：
    本题考查二叉树的基本概念。在平衡二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。虽然在结构上都符合二叉树的定义，但完全二叉树、线索二叉树、二叉排序树与最优二叉树的应用场合和概念都不同。线索二叉树与二叉树的遍历运算相关，是一种存储结构。二叉排序树的结构与给定的初始关键码序列相关。最优二叉树（即哈夫曼树）是一类带权路径长度最短的二叉树，由给定的一个权值序列构造。线索二叉树、二叉排序树和最优二叉树在结构上都不要求是平衡二叉树。在完全二叉树中，去掉最后一层后就是满二叉树，而且最后一层上的叶子结点必须从该层的最左边开始排列，满足任意一个结点的左、右子树的高度之差的绝对值不超过1的条件，因此在形态上是一个平衡的二叉树。

  • 第9题：

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


    正确答案:1

  • 第10题：

    在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该（）

    • A、只有左子树上的所有结点
    • B、只有左子树上的部分结点
    • C、只有右子树上的所有结点
    • D、只有右子树上的部分结点

    正确答案:A

  • 第11题：

    填空题
    一般树的每一个结点可以有（）个子树，在二叉树中每个结点的子树数不能超过（）个，而二叉树中的子树有左右之分，其次序不能颠倒。

    正确答案： 任意多,2
    解析： 暂无解析

  • 第12题：

    判断题
    在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第13题：

    二叉树中每个结点的两棵子树的高度差等于1。（）


    正确答案：错

  • 第14题：

    在非空二叉树的中序遍历序列中，二叉树的根结点的左边(40)。

    A．只有左子树上的所有结点

    B．只有左子树上的部分结点

    C．只有右子树上的所有结点

    D．只有右子树上的部分结点


    正确答案：A
    解析：在非空二叉树中序遍历序列中，二叉树的根结点的左边的那些结点为根结点的左子树上的所有结点。答案为A。

  • 第15题：

    前序遍历序列与中序遍历序列相同的二叉树为(1)，前序遍历序列与后序遍历序列相同的二叉树为(2)。

    A．根结点无左子树的二叉树

    B．根结点无右子树的二叉树

    C．只有根结点的二叉树或非叶子结点只有左子树的二叉树

    D．只有根结点的二叉树或非叶子结点只有右子树的二叉树


    正确答案：D

  • 第16题：

    满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为h(h＞1)的满二叉树，其结点总数为(36)。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从1、2、3、…依次编号，则对于树中编号为i的非叶子结点，其右子树的编号为(37)(高度为3的满二叉树如下图所示)。

    A．2h

    B．2h-1

    C．2h-1

    D．2h-1+1


    正确答案：C

  • 第17题：

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

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

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

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

    D．不存在度为1的节点


    正确答案：C
    解析：平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树。①左子树和右子树都是平衡二叉树；②左子树和右子树的深度之差的绝对值不超过1；③二叉树上节点的平衡因子定义为该节点的左子树的深度减去它的右子树的深度。由此可见，平衡二叉树上所有节点的平衡因子只可能是-1，0，1。只要二叉树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

  • 第18题：

    在下述结论中，不正确的是【】

    A．二叉树的度为2

    B．只有一个结点的二叉树的度为1

    C．二叉树的左右子树可任意交换

    D．深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树的结点个数


    正确答案：ABC
    [解析]二叉树的度可以是0、1或2；空二叉树和只有一个结点的二叉树的度均为0；二叉树的左右子树不能任意交换，否则不再是同一棵二叉树．

  • 第19题：

    在平衡二叉树中()。

    A.不存在度为1的节点
    B.任意节点的左、右子树节点数目相同
    C.任意节点的左、右子树高度相同
    D.任意节点的左右子树高度之差的绝对值不大于1

    答案：D
    解析：
    平衡二叉树又称AVL树，它或者是一棵空树，或具有下列性质的二叉树：(1)左子树和右子树都是平衡二叉树：(2)左子树和右子树的高度之差的绝对值不超过1。二叉树上节点的平衡因子定义为该节点的右子树的高度减去它的左子树的高度。可见，平衡二叉树上所有节点的平衡因子只可能是-1，0，1。只要二叉树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

  • 第20题：

    二叉排序树或者是一棵空树，或者是具有下列性质的一棵二叉树：（1）若左子数不空，则左子树所有结点的值（）；（2）若右子数不空，则右子树所有结点的值（）； （3）左右子树又分别是（）。
    均小于根结点的值；均大于根结点的值；二叉排序树
    略

  • 第21题：

    在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1


    正确答案:正确

  • 第22题：

    一般树的每一个结点可以有（）个子树，在二叉树中每个结点的子树数不能超过（）个，而二叉树中的子树有左右之分，其次序不能颠倒。


    正确答案:任意多；2

  • 第23题：

    判断题
    二叉树中每个结点的两棵子树的高度差等于1。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第24题：

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

    正确答案： 1
    解析： 暂无解析

相关内容