单选题
含有n个结点的三叉树的最小高度是______。
A
B
C
D
【正确答案】
D
【答案解析】
[解析] 设含有n个结点的三叉树的最小高度为h(为完全三叉树时高度最小),第h层至少有一个结点,至多有3
h-1
个结点,则有:
1+3
1
+3
2
+…+3
h-2
<n≤1+3
1
+3
2
+…+3
h-2
+3
h-1
即:
(3
h-1
-1)/2<n≤(3
h
-1)/2
得:
3
h-1
<2n+1≤3
h
也就是:
h<log
3
(2n+1)+1,h≥log
3
(2n+1)
而h只能是正整数,则
,所以,含有n个结点的三叉树的最小高度是
提交答案
关闭