单选题 5.有n个叶结点的非满的完全二叉树的高度为( )。
【正确答案】 A
【答案解析】设j、k分别为度为1、2的结点数目,则结点总数m=n+j+k;由于是非满的,所以必有j=1,且n=k+1,因此有m=2n。设树的高度为h,具有n个结点的完全二叉树的深度为log2n+1。本题中,树的结点个数为2n,有h=log2(2n)+1。所以,有n个叶结点的非满的完全二叉树的高度为log2(2n)+1。