php - 在 PHP 中通过树结构递归的特定算法

Question

在 PHP 中，我有这样的结构:

Array
(
    [0] = Array
    (
        'id' => 1,
        'parent' => 0
    )

    [1] = Array
    (
        'id' => 2,
        'parent' => 1
    )

    [2] = Array
    (
        'id' => 3,
        'parent' => 1
    )

    [3] = Array
    (
        'id' => 4,
        'parent' => 2
    )
)

id 是一个唯一的整数，parent 是对另一个元素的 id 的引用。如果 parent 为 0，则它没有父级。树结构如下所示:

1 -> 2 -> 4
  -> 3

(我希望这是清楚的!)。我一直在尝试确定一种算法，该算法将生成一个嵌套数组或类似的输出来公开树层次结构，以便我可以使用它；例如，一个这样的输出是:tree = ['1' => ['2' => ['4'], '3']]]。该算法可以支持任意深度的数组；但我将其限制在一个 child 不能有超过一个 parent 的条件下。

对于非标准语法表示歉意，我希望它能有效地传达我想要实现的目标，我认为这是深度优先搜索 - 但是我遇到的实现太枯燥了，我无法理解，所以如果能提供一些帮助，我将不胜感激。

Answer 1

如果您使用 key 作为 id，您会发现它变得无限简单。

$tree = array( 
    1 => array( 'parent' => 0 ), 
    2 => array( 'parent' => 1 ),
    3 => array( 'parent' => 1 ), 
    4 => array( 'parent' => 2 ) );

现在您可以遍历所有元素，只需将它们附加到它们的父元素即可。

$newtree = array();
foreach($tree as $leaf) {
    if (!isset($newtree[$leaf['parent']])) $newtree[$leaf['parent']]=array();
    $newtree[$leaf['parent']][]=$leaf; }
print_r($newtree);

看看你得到了什么。