一般に、
隣接リストについて嫌いなのは再帰です。特に、制限なしでツリーを選択する必要がある場合は、次のようになります。
- コメントツリー全体。
- サイトマップ;
- ナビゲーションメニュー。
- など。
もちろん、ポインタを使用してツリー配列を形成するために提案されたソリューションでは、データベースへの不要なクエリを取り除くことができますが、残念ながら、配列を介してではありますが、再帰は除外されません。 そして私たちと...
挑戦する
データベースに対して1つの要求を行い、1回のパスで単一レベルのリストを目的の順序で収集します。
解決策
データベースレベルでこのような問題を解決する方法はまだわかりませんが、アプリケーションレベルでは簡単です。主な問題は、特定のノードでは親と子を取得できない可能性があることです。 したがって、一時リストを使用し、必要に応じてそれらをまとめます。 Perlのアルゴリズムをお勧めします。
Perlコード（1）
＃！/ usr / bin / perl
警告を使用します。 厳格な使用;
＃データはORDER BY pid DESC、[ORDER] ASCとしてサンプリングされます
＃ここではデータベースを使用しませんが、選択したリストを使用します
私の@select =（
＃ID PIDその他のデータの注文...
{id => 14、pid => 1、ord => 1、data => 'その他のデータ'}、
{id => 15、pid => 4、ord => 1、data => 'その他のデータ'}、
{id => 24、pid => 4、ord => 2、data => 'その他のデータ'}、
{id => 23、pid => 7、ord => 1、data => 'その他のデータ'}、
{id => 27、pid => 7、ord => 2、data => 'その他のデータ'}、
{id => 25、pid => 7、ord => 3、データ=> 'その他のデータ'}、
{id => 17、pid => 7、ord => 4、データ=> 'その他のデータ'}、
{id => 28、pid => 11、ord => 1、data => 'その他のデータ'}、
{id => 21、pid => 11、ord => 2、データ=> 'その他のデータ'}、
{id => 5、pid => 12、ord => 1、data => 'その他のデータ'}、
{id => 11、pid => 12、ord => 2、data => 'その他のデータ'}、
{id => 13、pid => 12、ord => 3、データ=> 'その他のデータ'}、
{id => 10、pid => 12、ord => 4、データ=> 'その他のデータ'}、
{id => 22、pid => 12、ord => 5、データ=> 'その他のデータ'}、
{id => 2、pid => 13、ord => 1、data => 'その他のデータ'}、
{id => 6、pid => 15、ord => 1、data => 'その他のデータ'}、
{id => 20、pid => 15、ord => 2、data => 'その他のデータ'}、
{id => 9、pid => 15、ord => 3、data => 'その他のデータ'}、
{id => 7、pid => 16、ord => 1、data => 'その他のデータ'}、
{id => 1、pid => 20、ord => 1、data => 'その他のデータ'}、
{id => 26、pid => 20、ord => 2、データ=> 'その他のデータ'}、
{id => 8、pid => 25、ord => 1、data => 'その他のデータ'}、
＃最も重要なことは、ルートノードが最後にあることです。
{id => 12、pid => 0、ord => 1、data => 'その他のデータ'}、
{id => 4、pid => 0、ord => 2、data => 'その他のデータ'}、
{id => 3、pid => 0、ord => 3、data => 'その他のデータ'}、
{id => 18、pid => 0、ord => 4、data => 'その他のデータ'}、
{id => 16、pid => 0、ord => 5、data => 'その他のデータ'}、
{id => 19、pid => 0、ord => 6、data => 'その他のデータ'}、
）;
my％インデックス=（）; ＃このハッシュでは、ノードの座標（リストのキーとリスト内の順序）を保存します
my％リスト=（）; ＃PIDによる最初のノードのリスト
私の$ tpid = undef; ＃現在のリストPID
foreach my $ row（@select）{
＃ルートノードがどのpidの定義を解除するか、またはおそらく0
$ row-> {pid} || = 'root';
＃親ノードの現在のIDが定義されていない場合は、それを置き換えます
$ tpid || = $ row-> {pid};
＃最初にノードレベルを設定します1
$行-> {レベル} = 1;
＃ノードをPIDリストに挿入します
プッシュ@ {$リスト{$行-> {pid}}}、$行。
＃ノードの座標を置く
$インデックス{$行-> {id}} = [$行-> {pid}、$＃{$リスト{$行-> {pid}}}];
＃現在のノードのIDに対して既に生成されたリストがある場合
if（$リスト{$行-> {id}}）{
＃このリストには、現在のリストに参加する新しい座標を配置し、
＃新しいリストで注文し、レベルを1上げる
地図{
$インデックス{$ _-> {id}}-> [0] = $ row-> {pid};
$インデックス{$ _-> {id}}-> [1] + =スカラー@ {$リスト{$行-> {pid}}};
$ _-> {レベル} ++
} @ {$リスト{$行-> {id}}};
＃下位リストを現在のリストに添付
@ {$リスト{$行-> {pid}}}、@ {$リスト{$行-> {id}}};
＃不要なものとして削除
$リストの削除{$ row-> {id}};
}
＃現在のPIDがノードのPIDと一致しない場合、現在のPIDのリストは最後まで形成されます
if（$ tpid ne $ row-> {pid}）{
＃この時点までに親ノードがありましたか？そうでない場合、彼はこのリストを取得します
＃彼に関しては
if（$インデックス{$ tpid}）{
＃親リスト内のノードの順序を、親ノードから最後まで番号だけ増やします
＃挿入されたリストノード
地図{
$インデックス{$ _}-> [1] + =スカラー@ {$リスト{$ tpid}}
} @ {$リスト{$インデックス{$ tpid}-> [0]}} [$インデックス{$ tpid}-> [1] + 1 .. $＃{$リスト{$インデックス{$ tpid}-> [ 0]}}];
＃実装されたリストのノードの新しい座標を配置し、
＃および親ノードに相対的なレベル
地図{
$インデックス{$ _-> {id}}-> [0] = $インデックス{$ tpid}-> [0];
$インデックス{$ _-> {id}}-> [1] + = $インデックス{$ tpid}-> [1] + 1;
$ _-> {レベル} + = $リスト{$インデックス{$ tpid}-> [0]}-> [$インデックス{$ tpid}-> [1]]-> {レベル};
} @ {$リスト{$ tpid}};
＃親ノードの座標に相対的なリストを実装する
splice @ {$リスト{$インデックス{$ tpid}-> [0]}}、$インデックス{$ tpid}-> [1] + 1、0、@ {$リスト{$ tpid}};
＃不要なリストを削除する
$リストの削除{$ tpid};
}
＃新しいPIDを置く
$ tpid = $ row-> {pid};
}
}
＃ルートノードに指定したキーの下に既製のリストがあります。
私の@result = @ {$リスト{root}};
＃確認してみましょう
foreach my row（@result）{
print $ row-> {id}、 "\ t"、$ row-> {pid}、 "\ t"、$ row-> {ord}、 "\ t"、$ row-> {level}、 "\ t "、$ row-> {data}、" \ n "
}
1;
説明
ルートノードのリストをどこにでも固定する必要がないため、最初の並べ替えはPID（逆順）でのみ必要です。 それ以外の場合、サイクルの終了後に、最後のリストを「接着」する必要があります。また、
隣接リストアルゴリズムに
は定義によりこのフィールド
がないため、アルゴリズムにノードレベルの計算を実装しました。添付されていません。
オリジナル