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）すべてのツリー構造のエリックのリストを取得し、2つの「交差積」を実行すると（順列したノードを一定の順序で左から右に構造化する必要があります)、必要なすべてのツリーを取得する必要があります。

例: 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 の構造の 1 つに順列を割り当てることは、かなり簡単なはずです...そうですか?)

于 2012-07-12T10:41:08.167 に答える