algorithm - 具有 3 个节点的有序树的总数

Question

我在互联网上得到了不同的答案

我也在SO看到了一个问题，但对我没有多大帮助

答案应该是什么？

这也是树吗？
```
    a
   /
  b
 /
c
```

score 2 · Accepted Answer

2

请参阅以下链接，这是一篇关于计算有序树数量的非常好的论文。

于 2017-07-15T07:01:19.437 回答

score 1 · Accepted Answer

首先，是的，您的示例是任何合理定义下的树，除非您要求树是“完整的”，这在任何地方都没有提到。因此，我怀疑这两页上的答案（不足为奇）都是错误的。

其次，我不喜欢第二个链接中问题的措辞方式，因为它没有明确平等的含义。我们只是在寻找拓扑相同的树（相同的结构，即节点的位置）还是在寻找包含一组三个特定节点的树的相等性，就像在第一个链接中一样。所以，我会坚持第一个链接中的问题。

我正在使用以下有序树的定义。因为这个问题无关紧要，我将忽略空树的边缘情况，尽管如果需要，可以编写一个定义以将空树包含为候选者。有序树由一个根节点和一个可能为空的子节点列表（有序序列）组成，每个子节点也是有序树。

这个定义清楚地包括你的例子。根是 A，它有一个子节点 B，它有一个子节点 C，它没有子节点（一个空的子节点列表）。

让我们递归地处理要放入树中的节点数 N。我们将让 T(N) 是可以从一组固定的 N（标记）节点构建的不同有序树的数量。

基本情况：N = 1。如果我们只有一个节点，我们只能构建一棵以该节点为根的树。所以 T(1) = 1。

第二种情况：N = 2。根节点有两种选择。剩下的节点必然是根的第一个也是唯一的孩子。所以 T(2) = 2。

第三种情况：N = 3。根节点现在有三个选择。一旦我们选择了一个根节点，我们又有两种情况：

案例A：根节点有两个孩子，每个孩子都是一个有两个元素的有序树。我们可以通过两种方式对剩余的两个节点进行排序。因此，鉴于根节点有两个子节点，因此有 3*2 = 6 个可能的具有三个节点的有序树。
案例B：根节点有一个孩子，它必然是一棵有两个元素的有序树。有 T(2) = 2 种不同的方式我们可以从剩余的两个元素构造一棵有序树，因此鉴于根节点只有一个子节点，总共有 3*2 = 6 个可能的具有三个节点的有序树。

这两个子案例涵盖了所有可能性并且它们不重叠（它们用三个节点划分可能的有序树），所以我们可以将它们相加：T(3) = 6 + 6 = 12。

如果您对更一般的问题感兴趣，那就有点棘手了，我不知道答案，也不知道答案是否已知。我会采取的方法是这样的：

一般情况：N。有一个根。剩余的 N - 1 个节点必须位于根的子树中。因此，您将查看 N - 1 的分区数（将 N - 1 分成组的方式数）。然后将不得不查看选择进入每个组的项目的方法的数量。然后您将查看可以根据每个组中的节点数生成的有序树的数量。

无论如何，还有其他方法。但这可能超出了这个问题的范围。

注意： 可能出现的一个问题是我是否忘记计算类似

    A                      A
   /                        \
  B           and            B
 /                            \
C                              C

但作为有序树，这些是相同的。它们在这里被显示为好像它们是二叉树（其中每个节点有两个可能是空子树的子节点）。但是对于有序树，我们只关心根是否相同以及相应的子节点是否相等。所以在上面的两种情况下，根都是 A。在这两种情况下，根都有一个孩子 B。在这两种情况下，那个孩子都有一个孩子 C。所以树是相同的。

algorithm - 具有 3 个节点的有序树的总数

2 回答 2

Related

Reference