3

我有一个相当愚蠢的问题，我发誓这不是家庭作业。对于我的一生，我不记得我是否曾经研究过一种算法来做到这一点，而且我的头脑/创造力让我失望了。

我有一个唯一节点列表。我需要生成包含这些节点的二叉树的所有唯一排列。如果您想知道，手性很重要；在其轴（左/右）上翻转的二叉树是不一样的。

一些背景信息，如果您想知道：它是用于进化程序的种子创建算法，所以大量的小种子是可以的。

编辑：澄清唯一性

Examples:

This:
  1
 / \
2   3

Is not the same as this:
  1
 / \
3   2

Nor is it the same as this:

    1
   /
  3
 /
2   

Nor this:

1
 \
  2
   \
    3
4

1 回答 1

6

Eric Lippert 在这里有一篇相关的帖子（实际上是一系列帖子的开始）。关键位是这种递归 LINQ 方法：

static IEnumerable<Node> AllBinaryTrees(int size)
{
    if (size == 0)
        return new Node[] { null };
    return from i in Enumerable.Range(0, size)
           from left in AllBinaryTrees(i)
           from right in AllBinaryTrees(size - 1 - i)
           select new Node(left, right);
}

这将获得给定大小的所有可能的二叉树结构。

我认为，如果您采用（a）节点列表的所有排列，以及（b）Eric 的所有树结构列表，并执行两者的“叉积”（您将排列的节点分配给 a以某种一致的顺序从左到右构建结构）你应该得到你想要的所有树。

例如 3 个项目

Permutations                        Tree structures
123  132                                 .   .    .    .    .        
213  231                               ./  ./   ./ \.   \.   \.
312  321                             ./     \.         ./      \.

Result
:      1   1    1    1    1             1   1    1    1    1      
:    2/  2/   2/ \3   \2   \2         3/  3/   3/ \2   \3   \3
:  3/     \3         3/      \3     2/     \2         2/      \2

:      2   2    2    2    2             2   2    2    2    2      
:    1/  1/   1/ \3   \1   \1         3/  3/   3/ \1   \3   \3
:  3/     \3         3/      \3     1/     \1         1/      \1

:      3   3    3    3    3             3   3    3    3    3      
:    1/  1/   1/ \2   \1   \1         2/  2/   2/ \1   \2   \2
:  2/     \2         2/      \2     1/     \1         1/      \1

如果您不关心手性，这将更加困难。

（生成输入节点的排列，并将排列分配给 Eric 的结构之一，应该是相当简单的......对吗？）

于 2012-07-12T10:41:08.167 回答