ツリー内の別のノードの子であるすべてのノードを取得します

StackOverflow https://stackoverflow.com/questions/79041

  •  09-06-2019
  •  | 
  •  

質問

私はデータベースに保存された古典的な親子メニューを持ったWebシステムを持っています。フィールドIDはPKであり、parent_idは所有するメニューを指します。(はい、これがあまりうまく拡張できないことはわかっていますが、それは別のトピックです)。

したがって、これらのレコード (id-parent_id ペア) については次のようになります。

0-7 0-4 4-9 4-14 4-16 9-6

私はこの木を持っています:

0
├ 7
└ 4
  ├ 9
  | └ 6     
  ├ 14
  └ 16

最上位ノードを非表示にする必要があるので、その特定のノードのすべての子のリストを作成する必要があります。4 の場合、(9、6、14、16) になります。順序は関係ありません。

私は混乱しています...これは古典的な木の問題に当てはまりますか?それともグラフ1ですか？

PHP を使用してこの構造を作成し、この問題を解決するにはどうすればよいでしょうか?

役に立ちましたか？

解決

これは再帰を使用する絶好のチャンスです。

疑似コード:

nodeList = {}
enumerateNodes(rootNode, nodeList);

function enumerateNodes(node, nodeList) {
   nodeList += node;
   foreach ( childnode in node.children ) {
       enumerateNodes(childnode, nodeList);
   }
}

編集：ツリーが隣接リスト形式であることに気づきませんでした。おそらく、作業を始める前に、それを実際のツリー データ構造に構築するだけでしょう。すべてのペアをループして (初めて見たときにノードを作成します)、それらをリンクするだけです。私 考える それは簡単なはずです...

他のヒント

隣接リスト モデルを扱うのは非常に困難です。私が今いる会社では階層構造にこれらを使用しているため、大きな頭痛の種となっています。私は以前の雇用主のために Celko のネストされたセット モデルを使用して成功しており、階層 (ツリー) の作成、維持、使用に非常にうまく機能しています。

それらについて説明しているこのリンクを見つけました。 http://www.intelligententerprise.com/001020/celko.jhtml

ただし、『SQL for Smarties:』という本もお勧めします。「Advanced SQL Programming」は Joe Celko 著で、ネストされたセットについて説明しています。

Joe Celko の Smarties のための SQL:高度な SQL プログラミング

Joe Celko の Smarties のための SQL のツリーと階層

これはグラフの問題です。チェックアウト BFS(幅優先検索) そして DFS(深さ優先検索)。. 。これらの用語を Google で検索すると、Web 上で何百もの実装を見つけることができます。

これは、ネストされたセットの実装では簡単です。詳細については、こちらを参照してください。

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

それ以外の場合は、次のように書きます。

def get_subtree(node)
  if children.size > 0
    return children.collect { |n| get_subtree(n) }
  else
    return node
  end
end
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top