含有n 个结点的三叉树的最小高度是多少？

[tag_link]

参考答案

设三叉树高度为 h（根为第 1 层）。高度为 h 的三叉树至多有 (3^h-1)/2 个结点，因此最小高度为 h=ceil(log_3(2n+1))。

推导过程

先令前 h-1 层全满，有 (3^(h-1)-1)/2 < n；再要求前 h 层容量覆盖 n，有 n <= (3^h-1)/2。合并得到 3^(h-1) < 2n+1 <= 3^h，所以 h=ceil(log_3(2n+1))。

评分要点

• 1. 写出 h 层最大容量
• 2. 建立严格的上下界
• 3. 给出向上取整结果并说明根为第 1 层