具有 n 个叶节点的二叉树的 min/max 深度是多少？

Question

我知道具有 n 个节点 的二叉树的最大深度是 n-1

我知道具有 n 个节点 的二叉树的最大深度是 floor(log2n)

但是，如果只给出 叶节点的数量 怎么办？

Answer 1

二叉树中有两个理想。

理想的"deepest"树。

 *
  *
   *
    *
     a

这棵树显然包含一个叶节点，并且可以有无限多个中间节点。这意味着一个叶节点的最大深度是无限的（除非你的问题需要有多个子节点的内部节点）

理想"shallowest"树

          *
      *       *
    *   *   *   *
   a a a a a a a a

这棵树显然包含 2^(depth-1) 个叶子（对于深度为 1 或更大的树），并且通过数学的魔法将具有 log(base2)(leaves) = depth-1 或 1+log(base2)(leaves) 的深度。由于我们不能有分数深度，因此必须对齐 ceil(1+log(base2)(leaves))

为了测试这个，让我们构建一个 table

leaves formula                        depth
  1    ceil(1+log(base2)(1)) => ceil(1+0) => ceil(1) => 1
  2    ceil(1+log(base2)(2)) => ceil(1+1) => ceil(2) => 2
  3    ceil(1+log(base2)(3)) => ceil(1+1.58) => ceil(2.58) => 3
  4    ceil(1+log(base2)(4)) => ceil(1+2) => ceil(3) => 3
  5    ceil(1+log(base2)(5)) => ceil(1+2.32) => ceil(3.32) => 4

等等。

因此具有 n 个节点（其中 n > 0）的树的深度范围是

[ceil(1+log(base2)(n)), infinity)

除非对最深的树有更强的约束，比如"each internal node must have two siblings (or something like that)"

具有 n 个叶节点的二叉树的 min/max 深度是多少？

What is min/max depth of a binary tree with n leaf nodes?

binary-tree

data-structures