create array tree from array list
PhpArraysRecursionTreePhp Problem Overview
i have a list like this:
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'),
)
but way bigger so i need a efficient way to make this into a tree like structure like this:
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',
)
)
)
i cannot use things like nested set or things like that becoas i can add left and right values in my database. any ideas?
Php Solutions
Solution 1 - Php
oke this is how i solved it:
$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;
}
Solution 2 - Php
small fix if you need more than 1 parentid[0] element :)
$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;
}
Solution 3 - Php
One more rework of Thunderstriker's variant - all the logic in one function:
/**
* @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);
Playground: https://www.tehplayground.com/Ap4uUuwHWl9eiJIx
Solution 4 - Php
Here is my adaptation from arthur's rework:
/* 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]);
}
Use:
$tree = createTree($flat);
Solution 5 - Php
I created an unusual ('while-based' instead of recursive) but multidimensional sorting function that walk the array until there aren't any orphans. Here the function:
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] );
}
}
}
}
Recommendation: the key of each element of the array has to be the id fo the element itself. Example:
$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' ),
);
Usage: the function need $a (the array), $parent_key (the name of the column where the id of the father is saved), $children_key (the name of the column where the children will be move). It returns nothing (the array is changed by reference). Example:
treeze( $ARRAY, 'father', 'children' );
echo "<pre>"; print_r( $ARRAY );
Solution 6 - Php
//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>";
Solution 7 - Php
One way to do this is with a recursive function that first finds all the bottom values of the list, adding them to a new array. Then for each new id, you use the same function on that id, taking the returned array and stuffing it in that item's new children array. Finally, you return your new array.
I won't do all the work for you, but the function's parameters will look something like:
function recursiveChildren($items_array, $parent_id = 0)
Essentially, it'll find all the ones with parent of 0, then for each of those it'll find all the ones with that id as the parent, and for each of those.. so on.
The end result should be what you are looking for.
Solution 8 - Php
Is there any reason this three pass method wouldn't work? I didn't do any tests to compare speed to some of the recursive solutions, but it seemed more straight forward. If your initial array is already associative with the IDs being the key, then you can skip the first 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;
}
Solution 9 - Php
A simpler version:
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);