如何将此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（）？从没有测试的阅读中，我认为你会将记录从堆叠中弹出并扔掉。