algorithm - 二叉树中深度 d 的节点数

Question

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

标签： algorithmdata-structurestreebinomial-heap

Answer 1

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

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

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

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