Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 11 down vote favorite
5

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?

share|improve this question
didn't get it... your list is a PHP array? – acm Nov 16 '10 at 16:05
1  
@andre OP is looking for an adjacency list. There is a number of duplicates for this. – Gordon♦ Nov 16 '10 at 16:11
2  
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? – erisco Nov 16 '10 at 17:02
sry typo in array but it was indeed array of arrays edited it now – Thunderstriker Nov 16 '10 at 17:11

4 Answers

up vote 10 down vote accepted

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
1  
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 – Adam Apr 12 '11 at 21:26
up vote 8 down vote

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;
}
share|improve this answer
Any ideas how to get this one working with any parentId on the lowest level ? stackoverflow.com/questions/11942115/… – mike_hornbeck Aug 15 '12 at 6:36
up vote 1 down vote

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( $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 $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 );
share|improve this answer
up vote 0 down vote

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.

share|improve this answer
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. – erisco Nov 16 '10 at 16:50
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. – DampeS8N Nov 16 '10 at 16:55
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. – erisco Nov 16 '10 at 16:58
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 – Thunderstriker Nov 17 '10 at 6:37

protected by Community♦ Oct 26 '12 at 18:17

This question is protected to prevent "thanks!", "me too!", or spam answers by new users. To answer it, you must have earned at least 10 reputation on this site.

Not the answer you're looking for? Browse other questions tagged or ask your own question.