如何將此MPTT數組轉換爲PHP中的樹結構？

Question

我有數據庫中的分層數據，存儲在Modified Preorder Tree Traversal格式。我在查詢中查詢的數據類似於「SELECT ID，Left，Right，Name等等FROM TABLE ORDER BY Left;」。我試圖從一個平面數組中將這些數據轉換成一個樹形結構，然後我將以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輸出功能似乎表明它應該在那裏。看起來像我投擲它的任何樹結構都會降低第二級以下的任何東西。任何對可能發生的事情的洞察力？

謝謝！

Answer 1

問題是分配一個數組不會複製引用，而是複製數組。這意味着你在「Parent」節點的「children」中的「Second Child」數組與您添加「Grandchild」的數組不是同一個數組，而是它的副本。

要解決此問題，你必須明確地使用引用賦值而不是複製的：

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（）？從沒有測試的閱讀中，我認爲你會將記錄從堆疊中彈出並扔掉。