Clever Geek Handbook

隣接リストツリー全体の非再帰的フェッチ

一般に、 隣接リストについて嫌いなのは再帰です。特に、制限なしでツリーを選択する必要がある場合は、次のようになります。 もちろん、ポインタを使用してツリー配列を形成するために提案されたソリューションでは、データベースへの不要なクエリを取り除くことができますが、残念ながら、配列を介してではありますが、再帰は除外されません。 そして私たちと...



挑戦する

データベースに対して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（逆順）でのみ必要です。 それ以外の場合、サイクルの終了後に、最後のリストを「接着」する必要があります。また、 隣接リストアルゴリズムには定義によりこのフィールドがないため、アルゴリズムにノードレベルの計算を実装しました。添付されていません。

オリジナル


More articles:


All Articles