具有 n 个节点的 4 叉树的最小深度是多少？
What is the minimal depth of a 4-ary tree with n nodes?
问题是：
具有 n 个节点的 4 叉树的最小深度是多少？
我找不到作为答案的正确日志，我知道 n = 1 的深度是 0，如果 2 <= n <= 5 是 1，如果 6 <= n <= 21 是 2
提前致谢！
这是一道数学题。
让我们在 完整 树中找出高度 h 和节点数 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 元的泛化现在很容易，因为：
f_k(h) = (k^(h+1)-1)/(k-1)，所以h = ceil(log_k((k-1)n + 1) - 1)
问题是：
具有 n 个节点的 4 叉树的最小深度是多少？
我找不到作为答案的正确日志，我知道 n = 1 的深度是 0，如果 2 <= n <= 5 是 1，如果 6 <= n <= 21 是 2
提前致谢！
这是一道数学题。
让我们在 完整 树中找出高度 h 和节点数 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 元的泛化现在很容易，因为：
f_k(h) = (k^(h+1)-1)/(k-1)，所以h = ceil(log_k((k-1)n + 1) - 1)