logo标签列表

有三个节点的有序树的总数

algorithmdata-structurestreebinary-treeordered-tree
4
2
有点不太清楚；也许不同的答案指的是“有序树”的不同定义；例如，必须考虑边缘是否有方向。 - Codor
2
是的，这是一棵树，所以我也会回答12。 - user189
1
我正在考虑的（带方向）显然是指http://en.wikipedia.org/wiki/Arborescence_(graph_theory)。 - user189
@user189 它也是二进制的吗？ - user1765876
@user189 加一分，因为你严谨地介绍了这些数据结构的正确术语。当计算机科学家轻率地使用数学术语和符号时，我感到很烦恼。 - Jonathan E. Landrum
是的，它将是二进制的，但不是“完整”的。请参阅http://en.wikipedia.org/wiki/Binary_tree了解详细信息。 - user189
2个回答
2

请参考下方链接：链接地址，这是一篇非常好的有关计算有序树数量的论文。

请在评论中发布链接，或提供更多有关算法的细节，以便回答有用，即使链接可能离线。 - Fabien
1
首先，是的，根据任何合理的定义，您的示例都是一棵树，除非您要求树是“完整的”，但这在任何地方都没有提到。因此，我怀疑这两个页面上的答案（并不意外地）是错误的。
其次，我不喜欢第二个链接中的问题措辞方式，因为它没有清楚地说明等式的含义。我们只是在寻找拓扑相同的树吗（即结构相同，节点位置相同），还是我们正在寻找包含三个特定节点集的树的相等性，就像在第一个链接中所述。因此，我将坚持第一个链接中的问题。
我使用以下有序树的定义。由于对于这个问题来说并不重要，我将忽略空树的边缘情况，尽管如果需要，可以编写一个定义来将空树作为候选项。有序树由根节点和可能为空的子节点列表（有序序列）组成，每个子节点也是有序树。
这个定义明显包括您的示例。根是A，它有一个子节点B，B有一个子节点C，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。因此，这两棵树是相同的。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接