若三叉树 T 中有244个结点(叶结点的高度为1),则 T 的高度至少是()。

A.8

B.7

C.6

D.5

[tag_link]

正确答案：C

高度为 n 的二叉树最多有 1 + 2 + ⋯ + 2 n − 1 = 2 n − 1 个结点，高度为 n 的三叉树最多有 f ( n ) = 1 + 3 + ⋯ + 3 n − 1 = 3 − 1 3 n − 1 − 2 3 n − 1 。f ( 5 ) = 121 f ( 6 ) = 364 因为 121 < 244 < 364 ，所以高度至少为 6。