列表

详情


下面关于二叉树的叙述,正确的是(  )。

 

A. 完全二叉树的高度h与其结点数n之间存在确定的关系

B. 在二叉树的顺序存储和链式存储结构中,完全二叉树更适合采用链式存储结构

C. 完全二叉树中一定不存在度为1的结点

D. 完全二叉树中必定有偶数个叶子结点

参考答案: A

详细解析:

    本题考查数据结构方面的基础知识。
    根据其定义,一棵完全二叉树除了最后一层外,其余层的节点数都是满的,最后一层的节点也必须自左至右排列,例如图(a)是高度为3的满二叉树,图(b)是完全二叉树,图(c)不是完全二叉树。

    二叉树采用顺序存储结构时,对于编号为i的节点,则有:
    ·若i= 1时,该节点为根节点,无双亲;
    ·若i>1时,该节点的双亲节点为[i/2」;
    ·若2i≤n,则该节点的左孩子编号为2i,否则无左孩子;
    ·若2i+1≤n,则该节点的右孩子编号为2i+1,否则无右孩子。
    图(d)为具有10个节点的完全二叉树及其顺序存储结构,图(e)为某非完全二叉树的顺序存储结构,从中可以看出,完全二叉树适合采用顺序存储结构。

    可以推导出具有n个节点的完全二叉树的深度为[log 2n]+1。

上一题