data-structures - 一棵二叉树在第 n 层可以有多少个节点？用归纳法证明答案

Question

这是一个家庭作业，我没有太多时间花在上面，但我知道一些答案，需要一点帮助。

我在想这样假设我们有：

1个节点---->1级

2,3个节点---->2级

3,4,5,6,7节点---->3级

4,5,6,.....,15 个节点 ----> 4 级

5,6,7,8,9,.....,31个节点---->5级

从 [ min=X node(s) TO max = 2^X - 1 node(s) ] 的节点间隔，其中 X 表示级别

从现在开始我很困惑如何完成

Answer 1

我记得要使用归纳法，您必须证明第 N 个案例和第 N + 1 个案例。我们看到，对于任何 N，N + 1 级的数量正好是其两倍。因此显示为 2^(N + 1) / 2^N = 2

可以通过从 n = 0 到 N - 1 of 2^n 的总和来找到节点的总数

您可能想要一个更确凿和详细的答案，但这就是要点。

Answer 2

听起来你说得对。二叉树可以拥有的最小节点数量为n，最大节点数量为2^n-1

Answer 3

二叉树中第 n 层的节点将有 n 个祖先。归纳证明：显示 P(0)：级别 0 的节点没有祖先。（这是真的，因为它是根。） 显示 P(1)：级别 1 的节点有一个祖先。（这是真的；祖先是位于第 0 层的根，它的父亲。）假设 P(K)：第 K 层的节点有 K 个祖先。它的父亲在 K - 1 层。证明 P(K+1)：在 K+1 层的节点将比 K 层的节点多一个祖先。第 K+1 个元素将在 (K+) 层有一个父节点1)-1，或K级。