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

Question

有一个未知深度的不平衡二叉树。具有两个子节点的节点数用 表示T2。只有一个孩子的节点用 表示T1，叶节点用 表示L。如果给出了T1 = m和节点，那么你能定义一个给出叶节点数量 LT2 = n的数学函数吗？f(m, n)

例如，在下面的树中，总T2节点是m = 3，总T1节点是n = 2。叶节点的数量L = f(m,n) = 4。你能找到一个数学函数f(m,n)来给出所有树的叶节点数量吗？

Answer 1

这很容易。在内部节点的完全二叉树（即每个非叶子都有 2 个子节点）中m，正好有m+1叶子节点。每个只有一个孩子的节点都可以被删除，你仍然有一个二叉树。所以，叶子节点的数量L就是m+1。或回答问题：f(m, n) = m + 1。

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

如果我们对9（把4直接放在 下2）做同样的事情，我们有一个完整的二叉树，也就是说，所有非叶子都有 2 个孩子。

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

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

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

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

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

---

替代证明

该性质也可以直接证明，而无需删除T1节点的挥手论证。再次，通过归纳，用归纳假设|L| = |T2| + 1。

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

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