このMPTT配列をPHPのツリー構造に変換するには？

Question

データベースに階層データがあり、Modified Preorder Tree Traversal形式で保存されています。私は "SELECT ID、Left、Right、名前、等からのテーブル注文からのLeft;"のような照会のデータを引っ張っています。私はこのデータをフラットな配列からDBにツリー構造に変換しようとしています。ツリー構造はPHPのjson_encode関数でJSONとして出力します。

ツリー構造コードが最初のレベルを超えて動作するのに問題があります。ここでは最小のテストケースです：

<pre><?php 

function projectListToTree($projects) { 
    $stack = Array(); 
    for($x =0; $x < count($projects); $x++) { 
     $project = $projects[$x]; 
     $project['Children'] = Array(); 

     while(count($stack) > 0 && $stack[count($stack) - 1]['Right'] < $project['Right']) { 
      array_pop($stack); 
     } 

     if(count($stack) > 0) { 
      $stack[count($stack) - 1]['Children'][] = $project; 
      echo "Adding " . $project['Name'] . " to " . $stack[count($stack) - 1]['Name'] . " for a total of " 
       . count($stack[count($stack) - 1]['Children']) . " kids\n"; 
     } else { 
      echo "No parent\n"; 
     } 

     echo "stack count: " . count($stack) . "\n"; 

     array_push($stack, $project); 
    } 

    echo "Left in stack: " . count($stack) . "\n"; 

    return $stack[0]; 
} 

/* 
This is basically what comes from the DB. 
Should be: 
    Parent 
    First Child 
    Second Child 
     Grand Child 
*/ 
$projects = Array(
    Array(
     "ID" => "2", 
     "Left" => "2", 
     "Right" => "9", 
     "ParentID" => "1", 
     "Name" => "Parent" 
    ), 
    Array(
     "ID" => "3", 
     "Left" => "3", 
     "Right" => "4", 
     "ParentID" => "2", 
     "Name" => "First Child" 
    ), 
    Array(
     "ID" => "4", 
     "Left" => "5", 
     "Right" => "8", 
     "ParentID" => "2", 
     "Name" => "Second Child" 
    ), 
    Array(
     "ID" => "5", 
     "Left" => "6", 
     "Right" => "7", 
     "ParentID" => "4", 
     "Name" => "Grand Child" 
    ) 
); 


$tree = projectListToTree($projects); 
echo "-----\n\n\n\n"; 
var_dump($tree); 

?></pre> 

そして、ここでは、私は、出力のためになってんだよ：

No parent 
stack count: 0 
Adding First Child to Parent for a total of 1 kids 
stack count: 1 
Adding Second Child to Parent for a total of 2 kids 
stack count: 1 
Adding Grand Child to Second Child for a total of 1 kids 
stack count: 2 
Left in stack: 3 
----- 



array(6) { 
    ["ID"]=> 
    string(1) "2" 
    ["Left"]=> 
    string(1) "2" 
    ["Right"]=> 
    string(1) "9" 
    ["ParentID"]=> 
    string(1) "1" 
    ["Name"]=> 
    string(6) "Parent" 
    ["Children"]=> 
    array(2) { 
    [0]=> 
    array(6) { 
     ["ID"]=> 
     string(1) "3" 
     ["Left"]=> 
     string(1) "3" 
     ["Right"]=> 
     string(1) "4" 
     ["ParentID"]=> 
     string(1) "2" 
     ["Name"]=> 
     string(11) "First Child" 
     ["Children"]=> 
     array(0) { 
     } 
    } 
    [1]=> 
    array(6) { 
     ["ID"]=> 
     string(1) "4" 
     ["Left"]=> 
     string(1) "5" 
     ["Right"]=> 
     string(1) "8" 
     ["ParentID"]=> 
     string(1) "2" 
     ["Name"]=> 
     string(12) "Second Child" 
     ["Children"]=> 
     array(0) { 
     } 
    } 
    } 
} 

あなたが見ることができるように、どこかで「孫が」でもprojectListToTreeで出力ものの、迷子にされますそれがそこにあるべきであることを示すようです。それは私がそれを投げる任意の木構造のように、2番目のレベルの下に何かを落とすようだ。何が起きているのかについての洞察？

ありがとうございます！

Answer 1

問題は、配列の割り当ては参照をコピーせず、配列のコピーを作成することです。これは、 "親"ノードの "子"にある "二次子"配列が、 "孫"を追加するのと同じ配列ではなく、そのコピーであることを意味します。アンパサンドが3箇所に追加されたことを

function projectListToTree($projects) { 
    $stack = Array(); 
    for($x =0; $x < count($projects); $x++) { 
     $project = &$projects[$x]; 
     $project['Children'] = array(); 

     while(count($stack) > 0 && $stack[count($stack) - 1]['Right'] < $project['Right']) { 
       array_pop($stack); 
     } 

     if(count($stack) > 0) { 
       $stack[count($stack) - 1]['Children'][] = &$project; 

       echo "Adding " . $project['Name'] . " to " . $stack[count($stack) - 1]['Name'] . " for a total of " 
         . count($stack[count($stack) - 1]['Children']) . " kids\n"; 

       echo "\n"; 
     } else { 
       echo "No parent\n"; 
     } 

     echo "stack count: " . count($stack) . "\n"; 

     $stack[] = &$project; 
    } 

    echo "Left in stack: " . count($stack) . "\n"; 

    return $stack[0]; 
} 

注：

問題を解決するには、明示的に代わりにコピーの参照の割り当てを使用する必要があります。

この問題のため、PHPではネストされた配列と代入演算子を使用する際には非常に注意が必要です。

これは、ネストされた配列で大量のデータを使用すると、プロセッサ使用率とメモリフットプリントが集中することを意味します。例えば、上の例では、projectListToTree（）が返ってくると、完全な配列ツリーがローカル変数$ treeにコピーされます（PHPガベージコレクタが吸うので）。

Answer 2

array_pop（）を呼び出すときにechoステートメントを入れましたか？テストせずにこれを読んで、私はあなたがスタックからレコードをポップして、それを投げ捨てていると思います。