create array tree from array list [duplicate]

Question 1

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?

Question 2

didn't get it... your list is a PHP array?

Question 3

@andre OP is looking for an adjacency list. There is a number of duplicates for this.

Question 4

The arrays you have demoed do not make sense because you have duplicate keys. Did you mean to have an array of arrays or are you showing the implied meaning based on the index value?

Question 5

sry typo in array but it was indeed array of arrays edited it now

Question 6

This flat array list is one of kinds of tree store in relational database and is named Adjacency list. There are another ways to store tree in RDBMS which are described in articles like this: bitworks.software/en/2017-10-20-storing-trees-in-rdbms.html

Question 7

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

Question 8

This works well, just make sure that, if you have more than one item with parentid=0, to loop through all the items and check for parentid == 0. If that's true, then run createTree on that item and append it to your tree array. Otherwise, this routine only works for the first item where parentid=0

Question 9

Found this solusion, helped a lot!

Question 10

Question: Is the &$list required or can it also work with $list? I believe that's what PHP uses to pass by ref. Also, is recursion discouraged in PHP?

Question 11

@JinIzzraeel If you want to pass non-objects by ref, you need the ampersand. Recursion is not discouraged in PHP.

Question 12

man you saved me from pulling out my hair today. thanks a lot.

Question 13

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

Question 14

Any ideas how to get this one working with any parentId on the lowest level ? stackoverflow.com/questions/11942115/…

Question 15

what if we will have a loop here?

Question 16

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

Question 17

I liked this example so I wrapped it in a class and made it available on github here; github.com/srayner/NavTree

Question 18

How to add an element to this tree as a child of a particular parent?

Question 19

@HappyCoder just add an element to the $flat, for example ['id'=>103, 'parentID'=>101, 'name'=>'a'] - it's a child of a ['id'=>101, 'parentID'=>100, 'name'=>'a'] element

Question 20

Based on @Vasily 's answer, I made an "array of instances" tree builder: gist.github.com/seniorpreacher/64adfcf4844974b568bc84bf3056c05e

Question 21

What is idKey? My ide keeps complaining about it

Question 22

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

Question 23

It works perfectly with multiple root parents with id 0.

Question 24

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

Question 25

Good way, faster than recurrence! Needs a little fix, "Notice: Undefined index: father"

Question 26

@PeterKrauss I've fixed the notice (and also improve a little bit the formatting)

Question 27

//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>";

Question 28

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.

Question 29

The problem with this algorithm is that it is likely O(n^2). Consider an array where every element is the parent of the next. This algorithm would scan the array n times, resulting in n(n+1)/2 operations.

Question 30

So remove the items from the old array as you find them before passing it along. My intention here was just to get a sketch of a function that will do the job. Not do the job fast. That's for optimization later on. This is the web. Caching is a better place to expend these kinds of mental energies.

Question 31

My calculation of n(n+1)/2 operations accounted for the fact that the array is shrinking after every scan. The OP stated that his data structure was "way bigger"; I feel it is implied that O(n^2) is too expensive.

Question 32

i was doing it like this until my tree where becomming to big that is way i asked for an efficient way it to mo about 1 second to create the tree and had to load several of them so this solution is to slow. i posted my solution this ony will do it in 5ms

Question 33

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

Question 34

personally, I'd make $array immutable and just add parentless items to a new array then return that array.

Question 35

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

Thunderstriker 1,3091 gold badge11 silver badges11 bronze badges · Accepted Answer · 2010-11-16 17:10:31Z

67

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

Share

Improve this answer

answered Nov 16, 2010 at 17:10

Thunderstriker's user avatar

Thunderstriker

1,3091 gold badge11 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Adam

Adam Over a year ago

This works well, just make sure that, if you have more than one item with parentid=0, to loop through all the items and check for parentid == 0. If that's true, then run createTree on that item and append it to your tree array. Otherwise, this routine only works for the first item where parentid=0

2011年04月12日T21:26:26.98Z+00:00

Altenrion

Altenrion Over a year ago

Found this solusion, helped a lot!

2016年06月29日T21:19:26.797Z+00:00

Jin

Jin Over a year ago

Question: Is the &$list required or can it also work with $list? I believe that's what PHP uses to pass by ref. Also, is recursion discouraged in PHP?

2016年11月22日T15:08:34.23Z+00:00

472084

472084 Over a year ago

@JinIzzraeel If you want to pass non-objects by ref, you need the ampersand. Recursion is not discouraged in PHP.

2017年04月12日T09:17:37.273Z+00:00

Disorder

Disorder Over a year ago

man you saved me from pulling out my hair today. thanks a lot.

2018年03月27日T10:08:01.323Z+00:00

CollectivesTM on Stack Overflow

create array tree from array list [duplicate]

9 Answers 9

5 Comments

2 Comments

6 Comments

1 Comment

2 Comments

Comments

4 Comments

1 Comment

Comments

Linked

Hot Network Questions

CollectivesTM on Stack Overflow

9 Answers 9

5 Comments

2 Comments

6 Comments

1 Comment

2 Comments

Comments

4 Comments

1 Comment

Comments

Linked

Related