9

更新:
私がやろうとしていることの例をさらに見つけました: Managing Hierarchical Data in MySQL。私はそれをやりたいのですが、JavaScript で、より具体的には reddit.com である階層構造のコメントを取り込むアプリを構築しているためです。Chrome Web ブラウザーに Pretty JSON 拡張機能がある場合は、reddit に移動してスレッドのコメントをクリックし、URL に .json を追加して、解析しているものを確認します。
コメントを解析し、適切な HTML を追加してネストされていることを示すだけで、JSON データを問題なく取得できます。
解決策のアイデアはありますか?

古い質問:
私はプログラムに取り組んでいて、コードを書く前にロジックを理解する必要がある部分に来ました。ツリー形式のデータを取り込んでいますが、親ノードごとに複数の子が存在する可能性があり、データを見つけることができる唯一のツリーは、重みのあるツリーまたは各ノードが最大で 2 つの子ノードを持つツリーです。だから私は、次のようにツリーの各ノードを評価するアルゴリズムを理解しようとしています:

startingParent[15] // [# of children]
    child1[0]
    child2[5]
       child2ch1[4]
       ...
       child2ch5[7]
    child3[32]
    ...
    child15[4]

今、アルゴリズムがどのように機能するかを書き出そうとすると、ネストされた for/while ループを書くことになりますが、ツリーの高さのレベルごとにループを書くことになります。ノードごとの子これは機能しません。ある時点で、このような木をトラバースする方法を学んだことは知っていますが、今は完全に逃げています。ループに関してこれがどのように行われるか知っている人はいますか?

4

4 に答える 4

17

再帰を使用しない場合は、補助データ構造が必要です。キューは幅優先のトラバーサルを提供しますが、スタックは深さ優先のトラバーサルを提供します。いずれにせよ、大まかに次のようになります。

structure <- new stack (or queue)
push root onto structure
while structure is not empty
  node <- pop top off of structure
  visit(node)
  for each child of node
     push child onto structure
loop

ウィキペディアの参考文献

于 2011-01-27T17:33:51.980 に答える
8

ループではなく、再帰を使用します。
幅優先検索
深さ優先検索
これらは、達成しようとしていることを始めるのに役立つはずです

于 2011-01-27T17:31:25.413 に答える
1

通常、ほとんどのツリー トラバーサルの最も単純なコードは再帰的です。あなたのような多方向ツリーの場合、通常、子への各ポインターを調べ、すべての子ノードに対して、そのノードを引数として自分自身を呼び出すループを作成するのが最も簡単です。

于 2011-01-27T17:33:27.530 に答える
1

のような再帰を使用するだけです

def travel(node):
    for child in node.childs:
        # Do something
        travel(child)
于 2011-01-27T17:31:30.767 に答える