将二叉树的有关概念推广到三叉树,则一棵有244个结点的完全三叉树的高度为(8)。A.4B.5C.6D.7

Question

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

A．4

B．5

C．6

D．7

Answer 1

正确答案：C
解析：易知，在三叉树的第i层上至多有3i-1个结点(i1)。那么深度为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≤n1+(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。