问题是：
具有 n 节点的4-ary树的最小深度是多少？
n
我找不到正确的日志就是答案，我知道对于 n = 1 ，深度是 0 ，如果 2 <= n <= 5 则是 1 ，如果 6 <= n <= 21 则是 2
n = 1
0
2 <= n <= 5
1
6 <= n <= 21
2
提前致谢！
这是一个数学问题 .
让我们在高度 h 和 full 树中的节点数 n 之间找到关系 f . 我会用递归来做它 .
h
f
n = f(h) . 正如你所说，基础很简单： f(0)=1 .
n = f(h)
f(0)=1
我们可以看到每个级别都包含 4^i 个节点，其中 i 是距离根的距离 . 因此，在总结了我们的所有级别之后：
4^i
i
f(h) = 4^h + f(h-1) = 4^h + 4^(h-1) + ... 4^1 + 4^0 = (4^(h+1)-1)/3 =n [sum of geometric series]
隔离 h ：
h = log_4(3n+1) - 1 并且您应该使用 ceil() ，因为您希望它也适用于非完整树 .
h = log_4(3n+1) - 1
ceil()
现在很容易推广k-ary，如：
f_k(h) = (k^(h+1)-1)/(k-1) ，所以 h = ceil(log_k((k-1)n + 1) - 1)
f_k(h) = (k^(h+1)-1)/(k-1)
h = ceil(log_k((k-1)n + 1) - 1)
1 回答
这是一个数学问题 .
让我们在高度
h和 full 树中的节点数n之间找到关系f. 我会用递归来做它 .n = f(h). 正如你所说，基础很简单：f(0)=1.我们可以看到每个级别都包含
4^i个节点，其中i是距离根的距离 . 因此，在总结了我们的所有级别之后：f(h) = 4^h + f(h-1) = 4^h + 4^(h-1) + ... 4^1 + 4^0 = (4^(h+1)-1)/3 =n [sum of geometric series]隔离
h：h = log_4(3n+1) - 1并且您应该使用ceil()，因为您希望它也适用于非完整树 .现在很容易推广k-ary，如：
f_k(h) = (k^(h+1)-1)/(k-1)，所以h = ceil(log_k((k-1)n + 1) - 1)