algorithm - 查找二叉树中叶节点数的数学函数

Question

<分区>

Answer 1

这很简单。在 m 个内部节点的完全二叉树(即每个非叶子节点都有 2 个子节点)中，恰好有 m+1 个叶子节点。每个只有一个 child 的节点都可以删除，你仍然有一个二叉树。因此，L 中的叶节点数就是m+1。或者回答问题:f(m, n) = m + 1。

举例说明“删除 T1 节点”的含义可能会有用。考虑你的例子。右边的 5 只有一个 child 。如果我们去掉5，把9直接放在2下面，叶子的数量不会改变。

如果我们对 9 做同样的事情(将 4 直接放在 2 下)，我们就有了一个完整的二叉树，即是，所有非叶子节点都有 2 个 child 。

有关如何删除所有 T1 类型的节点而不更改叶节点数的图形说明，请参见图片。

剩下的就是证明在一棵 m 内部节点的树中，每个非叶节点恰好有 2 个子节点，叶节点的数量是 m+1:

归纳法证明。归纳假设:|L| = |T2|+1

基础:树由单个节点组成。显然，|L|=1 和|T2|=0，所以它成立。

步骤:考虑一棵树，其根不是叶子。根据假设，它有两个 child ，左和右。通过归纳假设: |Lleft|=|T2left| + 1 和 |Lright| = |T2右| + 1。对于总树，我们有 |T2| = |T2左| + |T2右| + 1 和 |L| = |左左| + |右|。因此，|L| = |T2左| + 1 + |T2右| + 1 = |T2| + 1。

---

替代证明

该属性也可以直接证明，无需删除 T1 节点的手动参数。同样，通过归纳，归纳假设 |L| = |T2| + 1。

• Base:树是单节点，所以|L| = 1 和 |T2| = 0。
• 步骤案例 1:树的根只有 1 个 child ，X，然后是 |L| = |LX| 和 |T2| = |T2X|，所以 |L| = |T2| + 1 通过归纳假设。
• 步骤案例 2:这棵树有一个根，它有左右两个 child 。通过归纳假设: |Lleft|=|T2left| + 1 和 |Lright| = |T2右| + 1。对于总树，我们有 |T2| = |T2左| + |T2右| + 1 和 |L| = |左左| + |右|。因此，|L| = |T2左| + 1 + |T2右| + 1 = |T2| + 1。

因此，|L| = |T2| + 1 或换句话说 f(m, n) = m + 1。