2. 考研
  3. 已知一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有结点总数为( )。

已知一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有结点总数为( )。

admin2019-12-10  58
问题 已知一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有结点总数为(    )。
选项 A、2k-1-1
B、2k-1+1
C、2k—1
D、2k+1
答案C
解析 每个非叶子结点的平衡因子均为0，说明了该平衡二叉树为满二叉树，所以结点总数为2k一1。
    总结：(1)设Nh表示深度为h的平衡二叉树中含有的最少结点数，则 N0=0，N1=1，N2=2，…，Nh=Nh-1+Nh-2+1
    例如，深度为5的平衡二叉树中含有最少的结点数为N5=12。
    (2)二叉排序树的查找效率取决于其深度。对于结点个数相同的二叉排序树，平衡二叉树的深度最小，因此效率最高。
转载请注明原文地址:https://kaotiyun.com/show/CB3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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