在PHP中从一个平面数组构建树形结构

55
我在互联网上找了一圈,仍然没有找到我要的内容。我有一个平面数组,每个元素都包含一个“id”和一个“parent_id”。每个元素只会有一个父级,但可能有多个子级。如果parent_id = 0,则视为根级项。我正在尝试将我的平面数组转换成树形结构。我发现的其他示例只是将元素复制到父级,但原始元素仍然存在。
编辑
起始数组的每个元素都从单独的XML文件中读取。如果没有父级,则parent_id的值为“0”。键实际上是字符串。
对之前的混淆表示抱歉。希望这样更清楚:
/编辑
我的起始数组:
结果数组(树形结构):
        function buildTree(array &$elements, $parentId = 0) {
        $branch = array();
foreach ($elements as $element) { if ($element['parent_id'] == $parentId) { $children = $this->buildTree($elements, $element['id']); if ($children) { $element['children'] = $children; } $branch[] = $element; } }
return $branch; }

这段代码用于构建一个树形结构,输入一个多维数组 $elements 和父级 ID $parentId。

首先,定义了一个名为 $branch 的空数组,用于保存构建好的树形结构。

然后,使用 foreach 循环遍历 $elements 数组中的每个元素。如果该元素的 parent_id 等于当前传入的 parentId,则说明这个元素是当前节点的子节点,需要将其加入到 $branch 数组中,并递归调用 buildTree 函数,查找该元素是否还有子节点。

最后,返回 $branch 数组,即为构建好的树形结构。


1
我有点困惑。你是在要求我们编写代码,将第一个数组的内容输出为第二个数组吗? - MetalFrog
是的...这里的问题是什么? - Wes Crow
简而言之,我猜是这样的。我看了很多其他的例子,包括stackoverflow上和其他博客/论坛上的例子。但是当我尝试它们时,它们并不起作用。 - DSkinner
如果您一开始就创建了该数组,为什么不通过搜索数组的parent_id自动将其排序为树形结构呢? - Daniel West
邻接模型相对于嵌套集模型具有许多优点(在更改位置时,嵌套集模型非常昂贵)。Bill的幻灯片展示了不同模型成本的便捷概述:http://www.slideshare.net/billkarwin/models-for-hierarchical-data。请注意,在PosgresSQL、Oracle、DB2和MSSQL中,邻接列表比在MySQL中更可行(期待它们实现它)。 - Wrikken
显示剩余3条评论
14个回答

68

你忘记了在其中加上 unset() 哥们。

function buildTree(array &$elements, $parentId = 0) {
    $branch = array();

    foreach ($elements as $element) {
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($elements[$element['id']]);
        }
    }
    return $branch;
}

3
在某些情况下(即$arr = array( array('id'=>1, 'parentid'=>0), array('id'=>10, 'parentid'=>2), array('id'=>2, 'parentid'=>0), array('id'=>3, 'parentid'=>10), array('id'=>4, 'parentid'=>0), array('id'=>11, 'parentid'=>1), array('id'=>5, 'parentid'=>0), array('id'=>6, 'parentid'=>1), array('id'=>8, 'parentid'=>11), array('id'=>9, 'parentid'=>0), array('id'=>7, 'parentid'=>0), );)该解决方案可能无法正确构建树形结构。我建议查看以下网址:https://dev59.com/d2855IYBdhLWcg3wsWlq (Arthur的修改版解决方案)。 - danicotra
1
它不会保存没有子节点的第一个父节点。 - mrded
2
您可以通过添加以下代码行来提高搜索性能:“array_splice($elements, $key, 1);” 在这行代码之后:“if ($elmParent == $parentId) {”。保持如下形式:“... foreach ($elements as $key => $element) { if ($elmParent == $parentId) { array_splice($elements, $key, 1); ...” - Pyetro
这个的时间复杂度是 O(n^2) 或者 O(n log n),根据 @Pyetro 的建议。看一下我的答案,有一个线性解决方案。 - Leo
修复@danicotra指出的以下问题:foreach ($elements as $i => $element)unset($elements[$i]); - farinspace

40

ImmortalFirefly的解决方案有效,但是正如mrded指出的那样,它不能保存没有子项的第一个父项。我已编辑该函数以修复此问题:

function buildTree(array &$elements, $parentId = 0) {

    $branch = array();

    foreach ($elements as &$element) {

        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($element);
        }
    }
    return $branch;
}

不错的解决方案,与 wp_get_nav_menu_items 配合使用效果非常好,这为在 WordPress 上创建自定义菜单提供了很大的灵活性。哇! - klewis
如果您想要一个没有键的树(只有索引0、1、2等),请将行$branch[$element['id']] = $element;更改为$branch[] = $element; - Petr Pánek

6
这个对我有效:
$index=array();
$tree=array();
foreach ($ori as $key=>$var) {
  $var=array_shift($ori);
  if ($var['id']==0) $var['id']=$key;
  if ((string)$var['parent_id']==='0') {
    $tree[$key]=$var;
    $index[$key]=&$tree[$key];
  } else if (isset($index[$var['parent_id']])) {
    if (!isset($index[$var['parent_id']]['children'])) $index[$var['parent_id']]['children']=array();
    $index[$var['parent_id']]['children'][$key]=$var;
    $index[$key]=&$index[$var['parent_id']]['children'][$key];
  } else {
    array_push($ori,$var);
  }
}
unset($index);
print_r($tree);

4
我可以理解,除了结果中的这个部分:
Array
(
    [0] => Array
        (
            [id] => 0
            [parent_id] => 0
        )

    [1] => Array
        (
            [id] => 1
            [parent_id] => 0
        )

在我看来,如果parent_id = o,那么[1]不应该是[0]的子级吗?

无论如何,引用可以拯救问题:

$tree = array();
foreach($inputarray as $item){
     if(!isset($tree[$item['id']])) $tree[$item['id']] = array();
     $tree[$item['id']] = array_merge($tree[$item['id']],$item);
     if(!isset($tree[$item['parent_id']])) $tree[$item['parent_id']] = array();
     if(!isset($tree[$item['parent_id']]['children'])) $tree[$item['parent_id']]['children'] = array();
     $tree[$item['parent_id']]['children'][] = &$tree[$item['id']];
}
$result = $tree[0]['children'];
unset($tree);
print_r($result);

因为你在使用0作为'魔数'和现有id时滥用了它,所以现在我们在id=0分支中出现了递归。在$tree[$item['parent_id']]['children'][] = &$tree[$item['id']];之前添加if($item['parent_id']!=$item['id'])可以防止这种情况发生,但并不美观。


由于递归在我的情况下导致内存耗尽,因此加上 +1。在我的情况下,有54个对象,这已足以满足我的内存需求。 - bumerang

3

您可以使用这个函数(parent_id,id,title)来稍微不同地构建源数组:

$q = mysql_query("SELECT id, parent_id, name FROM categories");
while ($r = mysql_fetch_row($q)) {
  $names[$r[0]] = $r[2];
  $children[$r[0]][] = $r[1];
 }

function render_select($root=0, $level=-1) {
  global $names, $children;
  if ($root != 0)
    echo '<option>' . strrep(' ', $level) . $names[$root] . '</option>';
  foreach ($children[$root] as $child)
    render_select($child, $level+1);
}

echo '<select>';
render_select();
echo '</select>';
  1. 更高效的层次结构系统

(注:此链接为问题讨论页面,无法直接翻译其内容)

3
尽管这是一个老问题,我还是要在此发布我的答案:
/* assuming top level pid = 0 */
$rows = array (
    array ( 'id' => 1, 'pid' => 0 ),
    /* ... */
);

/* make id become array key */
$rows = array_column ( $rows, null, 'id' ); 

foreach ( $rows as $key => $val ) {
    if ( $val ['pid'] ) {
        if ( isset ( $rows [$val ['pid']] )) {
            $rows [$val ['pid']]['children'][] = &$rows [$key];
        }
    }
}

foreach ( $rows as $key => $val ) {
    if ( $val ['pid'] ) unset ( $rows [$key] );
}

array_column是PHP 5.5中新增的函数,但您可以轻松地自己创建。


3
这是我的解决方案,复制并优化其他人的解决方案。
function buildTree(array &$elements, $parentId = 0) {
    $branch = array();
    foreach ($elements as $key => $element) {
        if ($element['parent_id'] == $parentId) {
            $children = $this->buildTree($elements, $key);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$key] = $element;
            unset($elements[$key]);
        }
    }
    return $branch;
}

请注意,此答案使用索引数组作为键(0、1、2..)。这可能与从数据库解析的大多数结果最匹配。如果您将元素ID作为元素数组的键,则@SteveEdson的解决方案可能更好。 - Sjaak Wish

1
这是我的解决方案,首先按照parent_id对项目进行分组,然后从根节点开始递归地使用分组列表填充所有子分支。
public function get_nested_tree() {
    $parent_node = null;
    $nodes_by_parent = array();
    
    if(is_null($flat_list) || count($flat_list) <= 0){
        return null;
    }

    foreach ($flat_list as $node) {
        if($node['parent_id'] != null){
            $nodes_by_parent[$node['parent_id']][] = $node;
        }
        else{
            // NB. In my implementation if multiple roots exist,
            // I want to always return the first...
            if(is_null($parent_node)){
                $parent_node = $node;
            }
        }
    }

    return $this->populate_branch($parent_node, $nodes_by_parent);
}

public function populate_branch($node, $nodes_by_parent){
    $children = $nodes_by_parent[$node['id']] ?? [];

    foreach ($children as &$child){
        $child = $this->populate_branch($child, $nodes_by_parent);
    }

    $node['children'] = $children;

    return $node;
}

我认为这个时间复杂度是线性的(O(n))——假设PHP关联数组等同于其他语言中的HashMapDictionary

1

你需要考虑在MySQL中存储和加载分层数据,这应该可以解决一些问题。我假设第一个数组表示直接从数据库中获取的数据?

看起来你正在尝试使用邻接模型将数据组织成分层结构。还有其他方法可以使用嵌套来实现这一点。如果您不是从数据库中获取此数据,则可能没有那么有用。

这个链接应该会对你有所帮助:http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/


尽管它正确地说明了邻接模型和嵌套集模型的使用,但在实践中(至少在我的经验中),嵌套集模型对于任何实际数据来说都太昂贵了(平均需要更新表格的一半!)。如果数据相对稳定(即:很少更改),则它是可行的,但通常情况并非如此。 - Wrikken
@Wrikken 是的,这取决于数据的使用/更新方式。对于类别而言,它是可以的,但对于有大量修改的数据来说,这根本不可行。忘了提到这一点,谢谢 :) - Daniel West

1

SteveEdson的代码很好,但是当元素的父级在原始数据结构中不存在时,就会出现问题。这是我对此进行的修复(但它会从元素中删除“parent_id”,这可能是可以接受的,也可能不是):

function buildTree(array &$elements, $parentId = 0)
{
    $branch = array();
    foreach ($elements as &$element) {
        if ($element["parent_id"] != null && $elements[$element["parent_id"]] == null)
            unset($element["parent_id"]);        
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
            unset($element);
        }
    }
    return $branch;
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接