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