create array tree from array list

Solution 1:

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:

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:

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:

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:

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