logo标签列表

从数组列表创建数组树

phparraysrecursiontree
54

我有一个如下所示的列表:

array(
  array(id=>100, parentid=>0, name=>'a'),
  array(id=>101, parentid=>100, name=>'a'),
  array(id=>102, parentid=>101, name=>'a'),
  array(id=>103, parentid=>101, name=>'a'),
)

但是因为我需要更大的，所以我需要一种高效的方式将此转换为树形结构，如下所示：

array(
  id=>100, parentid=>0, name=>'a', children=>array(
    id=>101, parentid=>100, name=>'a', children=>array(
      id=>102, parentid=>101, name=>'a',
      id=>103, parentid=>101, name=>'a',
    )
  )
)

我无法使用像嵌套集这样的东西，因为我可以在我的数据库中添加左和右值。你有什么想法吗？

没明白...你的列表是一个 PHP 数组？ - acm
@andre OP正在寻找邻接表。这方面有很多重复的内容。 - Gordon
2
你展示的数组没有意义，因为它们有重复的键。你是想展示一个数组的数组还是根据索引值显示隐含的意义？ - erisco
抱歉，数组中有一个打字错误，但它确实是一个数组的数组。我已经进行了编辑。 - Thunderstriker
这个扁平的数组列表是关系型数据库中一种树存储的形式，被称为邻接表。还有其他存储树的方式在文章中有描述，比如：https://bitworks.software/en/2017-10-20-storing-trees-in-rdbms.html - Ilya Kolesnikov
9个回答
65

好的，这就是我是如何解决它的：

$arr = array(
  array('id'=>100, 'parentid'=>0, 'name'=>'a'),
  array('id'=>101, 'parentid'=>100, 'name'=>'a'),
  array('id'=>102, 'parentid'=>101, 'name'=>'a'),
  array('id'=>103, 'parentid'=>101, 'name'=>'a'),
);

$new = array();
foreach ($arr as $a){
    $new[$a['parentid']][] = $a;
}
$tree = createTree($new, array($arr[0]));
print_r($tree);

function createTree(&$list, $parent){
    $tree = array();
    foreach ($parent as $k=>$l){
        if(isset($list[$l['id']])){
            $l['children'] = createTree($list, $list[$l['id']]);
        }
        $tree[] = $l;
    } 
    return $tree;
}
2
这个方法很好用，只需要确保如果你有多个parentid=0的项目，要遍历所有项目并检查parentid == 0。如果是这样，那么在该项目上运行createTree并将其附加到您的树数组中。否则，此例程仅适用于parentid = 0的第一个项目。 - Adam
找到了这个解决方案，帮了很大的忙！ - Altenrion
问题：&$list 是否必须，或者 $list 也可以工作？我认为这是 PHP 中用于传递引用的方式。此外，在 PHP 中是否不建议使用递归？ - Jin
2
如果你想传递非对象引用，你需要使用&符号。在PHP中，递归并不被反对。 - 472084
兄弟，你今天真是救了我一命啊。非常感谢你！ - Disorder
47

如果你需要超过一个parentid[0]元素，则可以进行小修复 :)

$arr = array(
  array('id'=>100, 'parentid'=>0, 'name'=>'a'),
  array('id'=>101, 'parentid'=>100, 'name'=>'a'),
  array('id'=>102, 'parentid'=>101, 'name'=>'a'),
  array('id'=>103, 'parentid'=>101, 'name'=>'a'),
);

$new = array();
foreach ($arr as $a){
    $new[$a['parentid']][] = $a;
}
$tree = createTree($new, $new[0]); // changed
print_r($tree);

function createTree(&$list, $parent){
    $tree = array();
    foreach ($parent as $k=>$l){
        if(isset($list[$l['id']])){
            $l['children'] = createTree($list, $list[$l['id']]);
        }
        $tree[] = $l;
    } 
    return $tree;
}
有没有办法让这个代码在最低层级上使用任何parentId？http://stackoverflow.com/questions/11942115/convert-flat-array-to-nested-parent-child-structure#comment15908756_11942115 - mike_hornbeck
1
如果我们在这里有一个循环会怎样？ - Oleg Abrazhaev
23

对Thunderstriker版本进行了一次重构 - 所有逻辑都在一个函数中：

/**
 * @param array $flatList - a flat list of tree nodes; a node is an array with keys: id, parentID, name.
 */
function buildTree(array $flatList)
{
    $grouped = [];
    foreach ($flatList as $node){
        $grouped[$node['parentID']][] = $node;
    }

    $fnBuilder = function($siblings) use (&$fnBuilder, $grouped) {
        foreach ($siblings as $k => $sibling) {
            $id = $sibling['id'];
            if(isset($grouped[$id])) {
                $sibling['children'] = $fnBuilder($grouped[$id]);
            }
            $siblings[$k] = $sibling;
        }
        return $siblings;
    };

    return $fnBuilder($grouped[0]);
}

// Example:
$flat = [
    ['id' => 100, 'parentID' => 0, 'name' => 'root'],
    ['id' => 101, 'parentID' => 100, 'name' => 'ch-1'],
    ['id' => 102, 'parentID' => 101, 'name' => 'ch-1-1'],
    ['id' => 103, 'parentID' => 101, 'name' => 'ch-1-2'],
];

$tree = buildTree($flat, 'parentID', 'id');
echo json_encode($tree, JSON_PRETTY_PRINT);

实验场： https://www.tehplayground.com/Ap4uUuwHWl9eiJIx

3
我很喜欢这个例子，所以我将其封装在一个类中，并在这里提供了GitHub链接；https://github.com/srayner/NavTree。 - srayner
如何将一个元素作为特定父节点的子节点添加到这棵树中？ - Happy Coder
@HappyCoder 只需向 $flat 添加一个元素，例如 ['id'=>103, 'parentID'=>101, 'name'=>'a'] - 它是 ['id'=>101, 'parentID'=>100, 'name'=>'a'] 元素的子元素。 - Vasily
根据@Vasily的回答，我制作了一个“实例数组”树生成器：https://gist.github.com/seniorpreacher/64adfcf4844974b568bc84bf3056c05e - seniorpreacher
什么是idKey？我的IDE一直在抱怨它。 - Sithell
@Sithell，那是一个多余的未使用变量，已删除，谢谢！ - Vasily
14

这是我对arthur改良版的适应：

/* Recursive branch extrusion */
function createBranch(&$parents, $children) {
    $tree = array();
    foreach ($children as $child) {
        if (isset($parents[$child['id']])) {
            $child['children'] =
                $this->createBranch($parents, $parents[$child['id']]);
        }
        $tree[] = $child;
    } 
    return $tree;
}

/* Initialization */
function createTree($flat, $root = 0) {
    $parents = array();
    foreach ($flat as $a) {
        $parents[$a['parent']][] = $a;
    }
    return $this->createBranch($parents, $parents[$root]);
}

使用：

$tree = createTree($flat);
1
它可以完美地处理具有ID 0的多个根父级。 - Alan Delval
8

我创建了一个不同寻常的（使用'while循环'而不是递归）多维排序函数，它遍历数组直到没有孤儿。以下是函数：

function treeze( &$a, $parent_key, $children_key )
{
    $orphans = true; $i;
    while( $orphans )
    {
        $orphans = false;
        foreach( $a as $k=>$v )
        {
            // is there $a[$k] sons?
            $sons = false;
            foreach( $a as $x=>$y )
            if( isset($y[$parent_key]) and $y[$parent_key]!=false and $y[$parent_key]==$k )  
            { 
                $sons=true; 
                $orphans=true; 
                break;
            }

            // $a[$k] is a son, without children, so i can move it
            if( !$sons and isset($v[$parent_key]) and $v[$parent_key]!=false )
            {
                $a[$v[$parent_key]][$children_key][$k] = $v;
                unset( $a[$k] );
            }
        }
    }
}

建议：数组中每个元素的关键字必须是元素本身的id。例如：

$ARRAY = array(
    1 => array( 'label' => "A" ),
    2 => array( 'label' => "B" ),
    3 => array( 'label' => "C" ),
    4 => array( 'label' => "D" ),
    5 => array( 'label' => "one", 'father' => '1' ),
    6 => array( 'label' => "two", 'father' => '1' ),
    7 => array( 'label' => "three", 'father' => '1' ),
    8 => array( 'label' => "node 1", 'father' => '2' ),
    9 => array( 'label' => "node 2", 'father' => '2' ),
    10 => array( 'label' => "node 3", 'father' => '2' ),
    11 => array( 'label' => "I", 'father' => '9' ),
    12 => array( 'label' => "II", 'father' => '9' ),
    13 => array( 'label' => "III", 'father' => '9' ),
    14 => array( 'label' => "IV", 'father' => '9' ),
    15 => array( 'label' => "V", 'father' => '9' ),
);

使用方法：这个函数需要$a（数组）、$parent_key（保存父级id的列名）和$children_key（子项将被移动的列名）。它什么都不返回（数组通过引用进行更改）。示例：

treeze( $ARRAY, 'father', 'children' );
echo "<pre>"; print_r( $ARRAY );
1
好方法，比递归更快！需要进行一些修复，“注意：未定义索引：father”。 - Peter Krauss
@PeterKrauss 我已经修复了通知（并且还稍微改善了一下格式）。 - Marco Panichi
3

//if order by parentid, id
$arr = array(
    array('id'=>100, 'parentid'=>0, 'name'=>'a'),
    array('id'=>101, 'parentid'=>100, 'name'=>'a'),
    array('id'=>102, 'parentid'=>101, 'name'=>'a'),
    array('id'=>103, 'parentid'=>101, 'name'=>'a'),
);

$arr_tree = array();
$arr_tmp = array();

foreach ($arr as $item) {
    $parentid = $item['parentid'];
    $id = $item['id'];

    if ($parentid  == 0)
    {
        $arr_tree[$id] = $item;
        $arr_tmp[$id] = &$arr_tree[$id];
    }
    else 
    {
        if (!empty($arr_tmp[$parentid])) 
        {
            $arr_tmp[$parentid]['children'][$id] = $item;
            $arr_tmp[$id] = &$arr_tmp[$parentid]['children'][$id];
        }
    }
}

unset($arr_tmp);
echo '<pre>'; print_r($arr_tree); echo "</pre>";
1

一种方法是使用递归函数，首先找到列表的所有底部值，并将它们添加到一个新数组中。然后对于每个新的id，您可以在该id上使用相同的函数，在返回的数组中填充该项的新子数组。最后，返回您的新数组。

我不会为您完成所有工作，但函数的参数看起来应该是这样的：

function recursiveChildren($items_array, $parent_id = 0)

基本上，它会找到所有父级为0的项，然后对于每个父级为0的项，它会找到所有父级为该id的项，以此类推。

最终结果应该是您要寻找的内容。

这个算法的问题在于它很可能是O(n^2)。考虑一个数组，其中每个元素都是下一个元素的父元素。该算法将扫描该数组n次，导致n(n+1)/2次操作。 - erisco
在传递旧数组之前，找到要删除的项并将其移除。我的意图只是得到一个能够完成工作的函数草图，而不是快速完成工作。优化留待以后。这是网络世界。缓存是更好的地方来消耗这些精力。 - DampeS8N
我的n(n+1)/2次计算考虑了每次扫描后数组缩小的事实。OP表示他的数据结构“要大得多”；我觉得这意味着O(n^2)太昂贵了。 - erisco
我一直这样做，直到我的树变得太大了，所以我寻求一种更有效的方法。创建树需要约1秒钟的时间，并且必须加载多个树，因此这种解决方案太慢了。我发布了我的解决方案，这个新的解决方案只需要5毫秒就能完成。 - Thunderstriker
1
一种更简单的版本：
function build_tree(&$items, $parentId = null) {
    $treeItems = [];
    foreach ($items as $idx => $item) {
        if((empty($parentId) && empty($item['parent_id'])) || (!empty($item['parent_id']) && !empty($parentId) && $item['parent_id'] == $parentId)) {
            $items[$idx]['children'] = build_tree($items, $items[$idx]['id']);
            $treeItems []= $items[$idx];
        }
    }

    return $treeItems;
}
build_tree($array);
1
这个三遍方法有没有不可行的理由？我没有进行任何测试来比较递归解决方案的速度，但它似乎更加直接。如果你的初始数组已经是带有ID作为键的关联数组，则可以跳过第一个 foreach()。
function array_tree(&$array) {
    $tree = array();

    // Create an associative array with each key being the ID of the item
    foreach($array as $k => &$v) {
      $tree[$v['id']] = &$v;
    }

    // Loop over the array and add each child to their parent
    foreach($tree as $k => &$v) {
        if(!$v['parent']) {
          continue;
        }
        $tree[$v['parent']]['children'][] = &$v;
    }

    // Loop over the array again and remove any items that don't have a parent of 0;
    foreach($tree as $k => &$v) {
      if(!$v['parent']) {
        continue;
      }
      unset($tree[$k]);
    }

    return $tree;
}
个人而言，我会将$array设为不可变，并将无父级的项目添加到一个新数组中，然后返回该数组。 - user719662
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接