私は、データベースに保存された古典的な親子メニューを持つ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) になります。順序は関係ありません。
私は混乱しています...これは古典的なツリーの問題に当てはまりますか? それともグラフですか？
この構造を構成し、php を使用してこの問題を解決するにはどうすればよいですか?
隣接リスト モデルは扱いが非常に困難です。私が現在所属している会社では、それらを階層に使用しており、それが大きな頭痛の種になっています。私はCelkoのネストされたセットモデルを以前の雇用者にうまく使用しており、階層（ツリー）の作成、維持、および使用に最適です。
それらを説明するこのリンクを見つけました：http://www.intelligententerprise.com/001020/celko.jhtml
しかし、Joe Celko 著の「SQL for Smarties: Advanced SQL Programming」という本もお勧めします。ネストされたセットについて説明しています。
これは、再帰を使用する絶好のチャンスです。
擬似コード:
nodeList = {}
enumerateNodes(rootNode, nodeList);
function enumerateNodes(node, nodeList) {
nodeList += node;
foreach ( childnode in node.children ) {
enumerateNodes(childnode, nodeList);
}
}
編集:ツリーが隣接するリスト形式であることに気づきませんでした。作業を開始する前に、おそらくそれを実際のツリーデータ構造に組み込むだけでした。すべてのペアをループして (最初にノードが表示されたときにノードを作成します)、それらをリンクするだけです。私はそれが簡単であるべきだと思う...
これはグラフの問題です。BFS（幅優先検索）とDFS（深さ優先検索）をチェックしてください。. これらの用語をググると、ウェブ上で何百もの実装を見つけることができます。
これは、ネストされたセットの実装では簡単です。詳細については、こちらを参照してください。
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