将扁平结构转换为树形结构，只知道父级信息。

Question

考虑以下数组结构：

array(
   55 => array(
       'ident' => 'test 1',
       'depth' => 1,
   ),
   77 => array(
       'parent_id' => 55,
       'ident' => 'test 2',
       'depth' => 2,
   )
);

有没有通用的算法可以将它转换为嵌套树形结构？

即：

array(
   55 => array(
       'ident' => 'test 1',
       'depth' => 1,
       'children' => array(
            77 => array(
                'parent_id' => 55,
                'ident' => 'test 2',
                'depth' => 2,
           )
       )
   )
);

我提供的示例很简化，实际情况包括数百个节点+最多达到15个深度。

- Marty Wallace

---

你尝试了什么？我会将这个链接作为起点：https://dev59.com/1G865IYBdhLWcg3wHK3u - Sergiu Paraschiv

网站上有很多这样的问题，尝试搜索“php构建分层结构”或类似的内容，例如：https://dev59.com/JkjSa4cB1Zd3GeqPDTfk#1060993 - Orbling

@SergiuParaschiv 只是要注意一下，你链接的内容非常复杂（至少在O(n)的情况下也是可行的=>请看下面我的回答）。 - bwoebi

我认为你首先必须尝试一下才能知道这个问题的存在，不是吗？对于“数百个节点”，递归解决方案是完全可接受的。 - Sergiu Paraschiv

@SergiuParaschiv 递归实际上是 O(n^2)。想象一下有700个节点...递归“仅仅”需要大约250k次迭代（平均值），再加上函数调用通常也相对较慢，或者只需使用引用进行foreach循环的总共700次迭代...我认为在这一点上它开始产生显著差异。 - bwoebi

Answer 1

使用引用可以帮助很多。这样，即使孩子已经被插入，你仍然可以追加孩子。

foreach ($array as $key => &$sub) {
    if (isset($sub['parent_id'])) {
        $array[$sub['parent_id']]['children'][$key] = &$sub;
    }
}
unset($sub); // unset the reference to make sure to not overwrite it later...

// now remove the entries with parents
foreach ($array as $key => $sub) {
    if (isset($sub['parent_id'])) { 
        unset($array[$key]);
    }
}

以下是一些相关示例：http://3v4l.org/D6l6U#v500

- bwoebi

---

我可能是唯一一个宁愿避免像瘟疫一样引用PHP的人...尽管如此，这是一个有趣的回答。 - MackieeE

@MackieeE 你好，引用很棒。没有它们，一半的递归代码都无法实现。 - sybear

@MackieeE 是的，我也会尽量避免使用它们，但这实际上是一个非常有效的用例。因为我无法想象其他解决方案可以在O(n)时间内运行且不使用引用... - bwoebi

@MackieeE：我认为大多数人都讨厌PHP中的引用 - 可能会造成一团糟。但是bwoebi关于性能的观点是正确的，如果没有它们，内存或处理时间将飞升，必须存储路径等。 - Orbling

有趣，今晚我会试试它们 =] 谢谢，很有见地！我想这是因为我觉得在 PHP 中大多数引用都感觉很“幕后”，一开始阅读时似乎不太容易理解 - 除此之外，对答案和演示的赞同！ - MackieeE