1

所以我已经读到，在深度 d 的顺序 k 二项式树中的节点数是 k 选择 d。但是，我不知道该结果来自何处。有人对此有简单的证明/直觉吗？

4

2 回答 2

1

@templatetypedef 给出了一个正式的（ish :) 证明。这是一个非正式的证明：

在帕斯卡三角形中，第 N 层的节点是第 N-1 层的总和，加上右移的第 N-1 层。

在二叉树中，N 阶树包含 N-1 阶树，加上 N-1 阶树向下移动。

如果我们将二叉树的每一层替换为该层的节点数，二叉树的构造就完全变成了帕斯卡三角构造。

于 2020-09-11T03:01:10.457 回答
1

这是一个使用归纳的简单证明，尽管我认为必须有一个更优雅、更直观的论证，不需要归纳。

我们将通过对 n 的归纳来证明这个陈述：

深度为 d 的 n 阶二叉树中的节点数为 n 选择 d。

n = 0 的基本情况要求我们证明在深度 d = 0 处是（0 选择 0），即 1。这是真的。耶！

对于归纳步​​骤，假设这对于 n = k 是正确的；我们将在 n = k + 1 的情况下证明这一点。回想一下，可以通过取两棵 k 阶二叉树并将其中一棵树作为另一棵树的子树来形成一棵 k+1 阶二叉树。因此，如果您选择任何深度 d，则树中深度 d 处的节点数由下式给出

  • 来自一棵 k 阶树的深度 d 处的节点数，以及
  • 来自另一棵 k 阶树的深度 d-1 处的节点数，因为该树向下移动了一个位置。

我们的归纳假设告诉我们，这里的节点数是 (k 选择 d) + (k 选择 d-1)。现在，关于二项式系数的有趣事实！如果添加 (k 选择 d) + (k 选择 d-1)，你会得到什么？这适用于（k+1 选择 d）。（想想帕斯卡的三角形以获得一个很好的简单证明，或者计算出数学）。

我们已经得到了 k+1 的声明，这完成了我们很好的归纳证明。

现在剩下要做的就是锻炼直觉。:-)

于 2020-09-11T01:45:01.037 回答