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 的结构之一,应该是相当简单的......对吗?)