7

私は木の横断に苦労しているので、疫病のようにそれを避けてください...通常。

私は次のような種類のクラスを持っています（ここでは少し簡略化されたバージョンですが、機能的には同じです）。

class Branch(object):
    def __init__(self, title, parent=None):
        self.title = title
        self.parent = parent

たくさんのBranchインスタンスの辞書があり、それぞれのタイトルがキーになっています。

tree = {'Foo Branch': foo, 'Sub-Foo Branch': sub_foo, 'Bar Branch': bar}

今では、トラバーサルを効率的にするための複雑なアルゴリズム（MPTTなど）があることを知っています。特に、効率が最も重要なデータベース駆動型プロジェクトで使用する場合はそうです。私はデータベースをまったく使用しておらず、単純なメモリ内オブジェクトのみを使用しています。

のを考えると、titleそのブランチのすべての子孫（子、子の子など）をBranchから取得する必要があります。listtree

  1. 私の場合、効率を上げるためにMPTTのような複雑な（私のアルゴリズムのない脳:)アルゴリズムを使用することをお勧めしますか、それとも単一の関数でこれを実現する簡単な方法がありますか？
  2. もしそうなら、私がデータベースを使用していないことを知っているので、どれをお勧めしますか？
  3. 例を挙げていただけますか、それとも私が思っているよりもはるかに大きいですか？

注：これは宿題ではありません。私は学校にいません。私は本当にアルゴリズムが苦手です。DBに保存されたツリーを必要とするプロジェクトにDjangoMPTTを使用しましたが、それでもよく理解できていません。

4

1 に答える 1

6

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Tree_traversal

次のように2つのパスでトラバースします。

  • 最初のパス：適切なキーを使用してクエリノードを検索します。（ツリー全体のすべてのノードのハッシュマップがある場合、この手順は不要です。これは（適切な）ので、この手順は必要ありません。）

  • 2番目のパス：クエリノードでアルゴリズムの変更バージョンを呼び出しますが、今回は、ノードにアクセスするたびに、それを生成します（または非ローカルアキュムレータ変数に追加します）。

ただし、通常、ツリーには子へのポインタもあるため、状況は少し奇妙です。これは、二重リンクリストのようなものです。残念ながら、その情報はありません...しかし、幸いなことに、その情報を追加するのは簡単です。

nodes = tree.values()
for node in nodes:
    if node.parent:
        if not hasattr(node.parent, 'children'):
            node.parent.children = []
        node.parent.children +=[ node ]

これで、例を進めることができます。

def traverse(root, callback):
    """
        Peform callback on all nodes in depth-first order
        e.g. traverse(root, lambda x:print(x))
    """
    yield root, callback(root)
    for child in root.children:
        traverse(child)

def getAllDescendents(title):
    queryNode = titlesToNodes[title]  #what you call 'tree'
    for node,blah in traverse(queryNode, lambda x:None):
        yield node
于 2011-06-06T04:46:19.583 に答える