3

いくつかの異なるタイプのツリー ノードがあり、それぞれが 0 から 5 の子を持つ可能性があります。深さ <= N の考えられるすべてのツリーを生成するアルゴリズムを見つけようとしています。ノードに変更を加えるたびに新しいサブツリーが公開される（または古いサブツリーが削除される）可能性があるため、ツリーを再帰的にたどる方法を理解するのに苦労しています。

4

4 に答える 4

4

これは私が書いたPythonプログラムで、あなたが求めていることを実行すると思います。開始ノードを指定すると、可能なすべてのツリーが返されます。基本的に、これはビット操作によるトリックに要約されます。ノードに 5 つの子がある場合、各子が個別にサブツリーに存在する場合と存在しない場合があるため、2 5 = 32 の異なるサブツリーが存在する可能性があります。

コード：

#!/usr/bin/env python

def all_combos(choices):
    """
    Given a list of items (a,b,c,...), generates all possible combinations of
    items where one item is taken from a, one from b, one from c, and so on.

    For example, all_combos([[1, 2], ["a", "b", "c"]]) yields:

        [1, "a"]
        [1, "b"]
        [1, "c"]
        [2, "a"]
        [2, "b"]
        [2, "c"]
    """
    if not choices:
        yield []
        return

    for left_choice in choices[0]:
        for right_choices in all_combos(choices[1:]):
            yield [left_choice] + right_choices

class Node:
    def __init__(self, value, children=[]):
        self.value    = value
        self.children = children

    def all_subtrees(self, max_depth):
        yield Node(self.value)

        if max_depth > 0:
            # For each child, get all of its possible sub-trees.
            child_subtrees = [list(self.children[i].all_subtrees(max_depth - 1)) for i in range(len(self.children))]

            # Now for the n children iterate through the 2^n possibilities where
            # each child's subtree is independently present or not present. The
            # i-th child is present if the i-th bit in "bits" is a 1.
            for bits in xrange(1, 2 ** len(self.children)):
                for combos in all_combos([child_subtrees[i] for i in range(len(self.children)) if bits & (1 << i) != 0]):
                    yield Node(self.value, combos)

    def __str__(self):
        """
        Display the node's value, and then its children in brackets if it has any.
        """
        if self.children:
            return "%s %s" % (self.value, self.children)
        else:
            return str(self.value)

    def __repr__(self):
        return str(self)

tree = Node(1,
[
    Node(2),
    Node(3,
    [
        Node(4),
        Node(5),
        Node(6)
    ])
])

for subtree in tree.all_subtrees(2):
    print subtree

テスト ツリーのグラフィカルな表現を次に示します。

  1
 / \
2 3
   /|\
  4 5 6

そして、プログラムを実行した結果は次のとおりです。

1
1 [2]
1 [3]
1 [3 [4]]
1 [3 [5]]
1 [3 [4, 5]]
1 [3 [6]]
1 [3 [4, 6]]
1 [3 [5, 6]]
1 [3 [4, 5, 6]]
1 [2, 3]
1 [2, 3 [4]]
1 [2, 3 [5]]
1 [2, 3 [4, 5]]
1 [2, 3 [6]]
1 [2, 3 [4, 6]]
1 [2, 3 [5, 6]]
1 [2, 3 [4, 5, 6]]

もしよろしければ、これを別の言語に翻訳できます。指定しなかったので、Python を使用しました。Python のリスト内包表記を大いに活用したので、コードは Java や C++ などでもう少し冗長になります。

于 2009-07-21T19:51:16.497 に答える
1

要素を多次元配列に追加し、ツリーが完成するまでその関数を再度呼び出す for ループを含む関数を作成できます。あなたがどの言語を好むかわからないため、例を提供することはできません。

于 2009-07-21T16:08:20.830 に答える
0

ノード タイプ間の唯一の違いが子の数である場合、最大数の子を持つノード タイプのみを使用してすべての可能なツリーを生成すると、等しいか少ない子を持つノードの任意の組み合わせに対してもすべての可能なツリーが生成されます。

それはちょっと一口です...

別の言い方をすれば、5 つの子が最大の場合、5 つの子ノードのみで構成される可能なツリーの一部には、たとえば 2 つの実際の子と 3 つの null ポインターを持つノードがあります。これは、子ノードが 2 つしかないノードを持つことと実質的に同じです。

于 2009-07-22T02:58:45.273 に答える