使用唯一排列创建所有二叉树

Question

我有一个相当愚蠢的问题,我发誓不是家庭作业.对于我的生活,我不记得我是否研究过这样做的算法,而我的思维/创造力让我失望.

我有一个唯一节点列表.我需要生成包含这些节点的二叉树的所有唯一排列.如果你想知道,手性问题很重要; 在其轴(左/右)上翻转的二叉树是不一样的.

一些背景信息,如果你想知道:它是一个进化程序的种子创建算法,所以大量的小种子是好的.

编辑:澄清唯一性

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

Answer 1

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的所有树结构列表,并执行两者的"交叉产品"(您将置换节点分配给节点中的节点)按照一致的顺序从左到右结构)你应该得到你想要的所有树木.

例如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的结构之一分配排列,应该相当简单......对吗？)