问题 单项选择题

将二叉树的有关概念推广到三叉树,则一棵有244个结点的完全三叉树的高度为 (8)

A.4

B.5

C.6

D.7

答案

参考答案:C

解析:易知,在三叉树的第i层上至多有3i-1个结点(i≥1)。那么深度为k的三叉树的最多结点数为:[*]。假设具有n个结点的完全三叉树的高度为k,那么根据上式和完全三叉树的定义可知:1+(3k-1-1)/2≤n<1+(3k-1)/2。
这个不等式来源于这样的事实:高度为k的完全三叉树最后一层最少有1个结点,最多有(3k-1)/2个结点,即1+(3k-1-1)/2≤n≤(3k-1)/2,注意到n是整数,所以不等式可变为:1+(3k-1)/2≤n<1+(3k-1)/2,于是取以3为底的对数得k-1≤log3(2n-1)<k,即log3(2n-1)<k≤1+log3(2n-1),又因为k为整数,所以:k=「log3(2n-1)」+1。此题中,代入数值244便得k=6。

问答题
单项选择题