algorithm - 树中内部节点数的证明

Question

我正在阅读有关压缩尝试的内容并阅读以下内容:

压缩的特里树是一棵有 L 个叶子的树，特里里的每个内部节点至少有 2 个子节点。

然后作者写道，一棵有 L 个叶子的树使得每个内部节点至少有 2 个子节点，最多有 L-1 个内部节点。我真的很困惑为什么这是真的。

有人可以提供归纳证明吗？

Answer 1

归纳证明:
我们将通过对 L 的归纳来证明它 - 树中的叶子数。
基础:一棵由一片叶子组成的树实际上是一棵只 Root过的树。它有 0 个内部节点，声明为真。
假设对于具有 L 个叶子的压缩树，该声明是正确的。
步骤:设T是一棵有L+1片叶子的树。选择任意一片叶子，将其设为 l，然后对其进行修剪。
为了再次压缩树——你需要让我的父亲成为一片叶子[如果我的父亲有超过2个儿子，包括我，跳过这一步]。我们通过赋予它与我的兄弟相同的值(value)，并修剪兄弟来做到这一点。
现在你有一棵有L片叶子的树T'。
归纳:T'至多有L-1个内部节点。
所以，T有L-1+1=L个内部节点，最多有L+1个叶子节点。
Q.E.D.

替代证明:
一棵有L片叶子的二叉树有L-1个内部节点(1 + 2 + 4 + ... + L/2 = L-1)
因为在“最坏情况”下你有一个二叉树[每个内部节点至少有 2 个儿子!]，那么你不能有超过 L-1 个内部节点!