有多少种不同的有根未标记二叉树恰好有 9 个节点并且是左重树？

Question

我知道使用第 n 个加泰罗尼亚语数可能有多少棵树，但不知道如何找到左重树。有什么技巧吗？

Answer 1

答案是：2357

我在这里提供了一种合理的方法（不涉及编程）和代码来产生相同的结果，但是通过更 brute-force 的方法。

一个。推理

从直觉上看，排除法似乎更容易计数。所以这导致了这种方法：

数出所有有9个节点的二叉树。正如您已经指出的，这对应于第 9^th 个加泰罗尼亚数字。这是 C₉ = 4862.
减去根平衡的树的数量，即根的两个子树高度相等（我们称这些子树为 L 和 R).这给了我们左树或 right-heavy.
因为有和 right-heavy 棵树一样多的树，所以将这个结果除以二得到最终结果。

所以现在我们可以专注于计算第二个要点中提到的数字：

计算在根部严格平衡的树

一棵高度为 2 的树最多有 7 个节点（满的时候），所以高度需要至少为 3。高度为 5 的树（在根部平衡）需要至少 5 A 中的节点（在一条路径上），and 5 in B（也是在单条路径上），所以高度不能超过 4。因此我们只有两种可能性：在根中平衡的 9 节点二叉树的高度是 3 或 4 .

让我们分别处理这两种情况：

1。当树的高度为3

在这种情况下，我们有一个 4 层的树。让我们来分析一下每个级别：

前两层有3个节点：根和它的两个children.

第三层是第一层，其中可能有一些变化：该层有 2 到 4 个节点。让我们一一处理这三种情况：

1.a第三层有2个节点

这里第三层在L中有一个节点，在R中有一个节点。每个都可以是其 parent 的左侧或右侧 child。所以两边都有两种可能性：2x2 = 4种可能性。

第四层没有变化：剩下的四个节点是第三层两个节点的children。

可能性：4

1.b第三层有3个节点

有 4 种方法可以从第三层的四个可用位置中 select 三个位置。 L 或 R 中只有一个节点。我们称这个节点为 x.

在第四层我们需要分配剩下的三个节点，这样L和R至少得到其中一个。这是在 x 得到一个或两个 children.

时实现的

当x得到两个children时，剩下的另一个节点有4个可能的位置。在这里你可以看到这 4 个浅灰色的位置：
当x得到一个child时，可以是左也可以是右child，另外两个剩余节点可以6种方式占据四个可用位置（见上图）：2x6=12.

所以在第三层给定一个选择，第四层有4+12=16种可能的配置。

结合第三层的可能性，我们得到 4x16:

可能性：64

1.c第三层有4个节点

第三层就这样满了。第四层剩余的两个节点需要在 L 和 R 之间进行拆分，因此每个节点都有 4 个可能的位置。这总共给出了 4x4 = 16 种可能性。

可能性：16

2。当树的高度为4

当高度为4时，结果L和R各只有一片叶子：它们是每个 4 个节点的链 。只有这样才能让根严格平衡和得到4.

的高度

L的根节点没有选择（就是根的左边child），但是从那以后，L的每个下一个后代=102=]L 可以是其 parent 的左或右 child。 L 的形状因此有 2³ 种可能性 = 8。考虑到 R 的形状相同，我们有总共 8x8 = 64 个形状。

可能性：64

总计

将以上所有因素加在一起，我们有 4+64+16 + 64 = 148 种可能的形状，使树具有平衡的根。

因此应用顶部列出的方法，具有 9 个未标记节点的 left-heavy 二叉树的总数为 (4862-148)/2 = 2357

乙。代码

为了让这成为一个编程挑战，这里是 JavaScript 中的一个实现，它定义了以下函数：

countTreesUpToHeight(n, height)：统计所有二叉树n 个节点，不高于给定高度。使用递归。
countTreesWithHeight(n, height)：计算所有具有 n 个节点的二叉树，其中正好给定的高度。使用前面的函数。
countLeftHeavy(n)：主要功能。使用其他两个函数计算根的左子树高于右子树的所有组合。

所以这个方法不像上面的排除方法。它实际上计算了感兴趣的组合。输出是一样的。

function countTreesUpToHeight(n, height) {
    if (n > 2**(height+1) - 1) return 0; // too many nodes to fit within height
    if (n < 2) return 1;
    let count = 0;
    for (let i = 0; i < n; i++) {
        count += countTreesUpToHeight(i, height-1) 
               * countTreesUpToHeight(n-1-i, height-1);
    }
    return count;
}

function countTreesWithHeight(n, height) {
    return countTreesUpToHeight(n, height) - countTreesUpToHeight(n, height-1);
}

function countLeftHeavy(n) {
    let count = 0;
    // make choices for the height of the left subtree
    for (let height = 0; height < n; height++) {
        // make choices for the number of nodes in the left subtree
        for (let i = 0; i < n; i++) {
            // multiply the number of combinations for the left subtree 
            //   with those for the right subtree 
            count += countTreesWithHeight(i, height-1)
                   * countTreesUpToHeight(n-1-i, height-2);
        }
    }
    return count;
}

let result = countLeftHeavy(9);
console.log(result);               // 2357

有多少种不同的有根未标记二叉树恰好有 9 个节点并且是左重树？

How many different rooted unlabelled binary trees have exacly 9 nodes and are left-heavy?

algorithm

binary-tree

data-structures