从 PHP 中的平面数组构建一棵树

Build a tree from a flat array in PHP

提问by DSkinner

I've looked around the internet and haven't quite found what I'm looking for. I have a flat array with each element containing an 'id' and a 'parent_id'. Each element will only have ONE parent, but may have multiple children. If the parent_id = 0, it is considered a root level item. I'm trying to get my flat array into a tree. The other samples I have found only only copy the element to the parent, but the original still exists.

我环顾了互联网，并没有完全找到我要找的东西。我有一个平面数组，每个元素都包含一个“id”和一个“parent_id”。每个元素只有一个父元素，但可能有多个子元素。如果 parent_id = 0，则将其视为根级别项目。我正在尝试将我的平面阵列放入一棵树中。我发现的其他示例仅将元素复制到父元素，但原始元素仍然存在。

EDIT

编辑

Each element of the starting array is read from a separate XML file. The file itself will have '0' as the value for parent_id if it doesn't have a parent. The keys are actually strings.

起始数组的每个元素都是从一个单独的 XML 文件中读取的。如果文件没有父级，则文件本身的 parent_id 值将为“0”。键实际上是字符串。

I'm sorry for the confusion earlier. Hopefully this is more clear:

我很抱歉之前的混乱。希望这更清楚：

/EDIT

/编辑

My starting array:

我的起始数组：

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

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

    [_321_] => Array
        (
            [id] => _321_
            [parent_id] => _320_
        )

    [_322_] => Array
        (
            [id] => _322_
            [parent_id] => _321_
        )

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

    [_324_] => Array
        (
            [id] => _324_
            [parent_id] => _323_
        )

    [_325_] => Array
        (
            [id] => _325_
            [parent_id] => _320_
        )
)

The resulting array after the tree is made:

生成树后的结果数组：

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

    [_320_] => Array
        (
            [id] => _320_
            [parent_id] => 0
            [children] => Array
                (
                    [_321_] => Array
                        (
                            [id] => _321_
                            [parent_id] => _320_
                            [children] => Array
                                (
                                    [_322_] => Array
                                        (
                                            [id] => _322_
                                            [parent_id] => _321_
                                        )
                                )
                        )
                    [_325_] => Array
                        (
                            [id] => _325_
                            [parent_id] => _320_
                        )
                )
    [_323_] => Array
        (
            [id] => _323_
            [parent_id] => 0
            [children] => Array
                (
                    [_324_] => Array
                        (
                            [id] => _324_
                            [parent_id] => _323_
                        )
                )
        )

Any help / guidance is greatly appreciated!

非常感谢任何帮助/指导！

Some code I have so far:

到目前为止我拥有的一些代码：

        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;
    }

回答by n0nag0n

You forgot the unset()in there bro.

你忘记了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;
}

回答by SteveEdson

The solution by ImmortalFirefly is working, however, as mrded points out, it doesn't save first parents without children. I've edited the function to fix this issue:

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;
}

回答by Eugen Rieck

This works for me:

这对我有用：

$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);

回答by Wrikken

I can see the logic, save for this in the result:

我可以看到逻辑，在结果中保存：

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

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

IMHO, is parent_id = o, shouldn't [1] be a child of [0] here?

恕我直言，parent_id = o，这里 [1] 不应该是 [0] 的孩子吗？

Anyway, references to the rescue:

无论如何，参考救援：

$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);

Because you have abused 0 as both a 'magic' number as root, and an existing id, we now have recursion in the id=0 branch. Adding if($item['parent_id']!=$item['id'])before $tree[$item['parent_id']]['children'][] = &$tree[$item['id']];could prevent that, but it isn't pretty.

因为您滥用 0 作为根的“魔术”数字和现有 id，我们现在在 id=0 分支中有递归。添加if($item['parent_id']!=$item['id'])before$tree[$item['parent_id']]['children'][] = &$tree[$item['id']];可以防止这种情况，但它并不漂亮。

回答by Gigamegs

It's possible to construct the source array slightly different you can use this function(parent_id,id,title):

您可以使用此函数（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. More efficient hierarchy system

1. 更高效的等级制度

回答by Inglis Baderson

Though this is an old question, I'm gonna post my answer here:

虽然这是一个老问题，但我会在这里发布我的答案：

/* 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_columnis PHP 5.5 but you can make your own easily.

array_column是 PHP 5.5，但您可以轻松制作自己的。

回答by Daniel West

You want to be looking at storing and loading hierarchical data in MySQL as I this should solve a few problems. I'm assuming that the first array represents data taken directly from the database?

您想在 MySQL 中存储和加载分层数据，因为这应该可以解决一些问题。我假设第一个数组代表直接从数据库中获取的数据？

It looks like you're trying to use the adjacency model to organize your data into the hierarchy structure. There are also other ways to achieve this using nesting. If you are not taking this data from a database then this may not be as useful.

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

This link should help you out: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

此链接应该可以帮助您：http: //mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

回答by Arne M

SteveEdson's code works fine, except in the case where the parent of an element does not exist in the original data structure. Here's my fix for that (however, it removes "parent_id" from elements, which may or may not be acceptable):

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;
}

回答by hoorider

I came up with a similar solution as @eugen-rieck and wanted to share it. I named $branchesmy array of indices, though.

我想出了一个与@eugen-rieck 类似的解决方案，并想分享它。不过，我命名了$branches我的索引数组。

$tree = [];
$branches = [];

while (!empty($input)) {
    $beforeCount = count($input);

    foreach ($input as $id => $item) {
        $pid = $item['parent_id'];

        if (isset($branches[$pid])) {
            $branches[$pid]['children'][$id] = $item;
            $branches[$id] = &$branches[$pid]['children'][$id];
            unset($input[$id]);
        }
    }

    if ($beforeCount === count($input)) {
        $firstItem = array_shift($input);
        $id = $firstItem['id'];
        $tree[$id] = $firstItem;
        $branches[$id] = &$tree[$id];
    }
}

回答by touzas

This is my solution, copy and optimize others solutions.

这是我的解决方案，复制并优化其他解决方案。

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;
}