logo标签列表

创建具有唯一排列的所有二叉树

c#binary-tree
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
“唯一排列”是否也包括结构？例如，根节点为1，左子节点为2，另一个左子节点为3的树与根节点为1，左子节点为2，右子节点为3的树是否被视为相同？如果我表达得有些别扭，请见谅。 - Daniel
它不会被视为相同的。 - user978122
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)全排列，并使用Eric提供的所有树形结构列表(b)，并对两者执行“交叉乘积”(在某个一致的顺序中将排列好的节点分配给结构中的节点从左到右)，那么您应该得到所有想要的树。
例如，对于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结构之一，应该是相当简单的... 对吧？）
有趣。我会研究一下。 - user978122
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接