Asked  7 Months ago    Answers:  4   Viewed   37 times

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.

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.

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

 Answers

96

You forgot the unset() in there bro.

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;
}
Wednesday, March 31, 2021
 
JohnnyW
answered 7 Months ago
60

You should use recursion.

Here an exemple of code:

$datas = array(
    array('id' => 1, 'parent' => 0, 'name' => 'Page 1'),
    array('id' => 2, 'parent' => 1, 'name' => 'Page 1.1'),
    array('id' => 3, 'parent' => 2, 'name' => 'Page 1.1.1'),
    array('id' => 4, 'parent' => 3, 'name' => 'Page 1.1.1.1'),
    array('id' => 5, 'parent' => 3, 'name' => 'Page 1.1.1.2'),
    array('id' => 6, 'parent' => 1, 'name' => 'Page 1.2'),
    array('id' => 7, 'parent' => 6, 'name' => 'Page 1.2.1'),
    array('id' => 8, 'parent' => 0, 'name' => 'Page 2'),
    array('id' => 9, 'parent' => 0, 'name' => 'Page 3'),
    array('id' => 10, 'parent' => 9, 'name' => 'Page 3.1'),
    array('id' => 11, 'parent' => 9, 'name' => 'Page 3.2'),
    array('id' => 12, 'parent' => 11, 'name' => 'Page 3.2.1'),
    );

function generatePageTree($datas, $parent = 0, $depth=0){
    $ni=count($datas);
    if($ni === 0 || $depth > 1000) return ''; // Make sure not to have an endless recursion
    $tree = '<ul>';
    for($i=0; $i < $ni; $i++){
        if($datas[$i]['parent'] == $parent){
            $tree .= '<li>';
            $tree .= $datas[$i]['name'];
            $tree .= generatePageTree($datas, $datas[$i]['id'], $depth+1);
            $tree .= '</li>';
        }
    }
    $tree .= '</ul>';
    return $tree;
}

echo(generatePageTree($datas));

You can test it at: http://phpfiddle.org/main/code/1qy-5fj

Or if you want the exact format:

function generatePageTree($datas, $parent = 0, $depth = 0){
    $ni=count($datas);
    if($ni === 0 || $depth > 1000) return ''; // Make sure not to have an endless recursion
    $tree = '';
    for($i=0; $i < $ni; $i++){
        if($datas[$i]['parent'] == $parent){
            $tree .= str_repeat('-', $depth);
            $tree .= $datas[$i]['name'] . '<br/>';
            $tree .= generatePageTree($datas, $datas[$i]['id'], $depth+1);
        }
    }
    return $tree;
}

The test: http://phpfiddle.org/main/code/jw3-s1j

Wednesday, March 31, 2021
 
muncherelli
answered 7 Months ago
98

Explanations can be found as inline comments. This function provides your exact desired output. Also pay attention to the query that I've rewritten to set up $resultset.

Code: (Demo)

function findParent(&$array,$parentid=0,$childarray=[]){  // make $array modifiable
    foreach($array as $i=>&$row){                         // make $row modifiable
        if($parentid){                                    // if not zero
            if($row['id']==$parentid){                    // found parent
                $row['nodes'][]=$childarray;              // append child to parent's nodes subarray
            }elseif(isset($row['nodes'])){                // go down rabbit hole looking for parent
                findParent($row['nodes'],$parentid,$childarray);  // look deeper for parent while preserving the initial parent_id and row
            }                                             // else continue;
        }elseif($row['parent_id']){                       // child requires adoption
            unset($array[$i]);                            // remove child from level because it will be store elsewhere and won't be its own parent (reduce iterations in next loop & avoid infinite recursion)
            findParent($array,$row['parent_id'],$row);    // look for parent using parent_id while carrying the entire row as the childarray
        }                                                 // else continue;
    }
    return $array;                                        // return the modified array
}


// $db->query('SELECT id,name_a AS name,parent_id FROM accounts_tree ORDER BY id');
// for($resultset=[]; $row=$res->fetch_assoc(); $resultset[]=$row);  // inspired by: http://php.net/manual/en/mysqli-result.fetch-assoc.php#112924

$resultset=[
    ['id'=>1,'name'=>'folder 1','parent_id'=>0],
    ['id'=>2,'name'=>'folder 2','parent_id'=>0],
    ['id'=>3,'name'=>'sub 1-1','parent_id'=>1],
    ['id'=>4,'name'=>'sub 2-1','parent_id'=>2],
    ['id'=>5,'name'=>'Sub 1-1-1','parent_id'=>3],
    ['id'=>6,'name'=>'folder 3','parent_id'=>0],
    ['id'=>7,'name'=>'sub 1-1-1-1','parent_id'=>5]
];

print_r(findParent($resultset));

Output:

Array
(
    [0] => Array
        (
            [id] => 1
            [name] => folder 1
            [parent_id] => 0
            [nodes] => Array
                (
                    [0] => Array
                        (
                            [id] => 3
                            [name] => sub 1-1
                            [parent_id] => 1
                            [nodes] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 5
                                            [name] => Sub 1-1-1
                                            [parent_id] => 3
                                            [nodes] => Array
                                                (
                                                    [0] => Array
                                                        (
                                                            [id] => 7
                                                            [name] => sub 1-1-1-1
                                                            [parent_id] => 5
                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

    [1] => Array
        (
            [id] => 2
            [name] => folder 2
            [parent_id] => 0
            [nodes] => Array
                (
                    [0] => Array
                        (
                            [id] => 4
                            [name] => sub 2-1
                            [parent_id] => 2
                        )

                )

        )

    [5] => Array
        (
            [id] => 6
            [name] => folder 3
            [parent_id] => 0
        )

)
Saturday, May 29, 2021
 
PeanutsMcgee
answered 5 Months ago
75

One way to solve this to make use of variable aliases. If you take care to manage a lookup-table (array) for the IDs you can make use of it to insert into the right place of the hierarchical menu array as different variables (here array entries in the lookup table) can reference the same value.

In the following example this is demonstrated. It also solves the second problem (implicit in your question) that the flat array is not sorted (the order is undefined in a database result table), therefore a submenu entry can be in the resultset before the menu entry the submenu entry belongs to.

For the example I created a simple flat array:

# some example rows as the flat array
$rows = [
    ['id' => 3, 'parent_id' => 2, 'name' => 'Subcategory A'],
    ['id' => 1, 'parent_id' => null, 'name' => 'Home'],
    ['id' => 2, 'parent_id' => null, 'name' => 'Categories'],
    ['id' => 4, 'parent_id' => 2, 'name' => 'Subcategory B'],
];

Then for the work to do there are tow main variables: First the $menu which is the hierarchical array to create and second $byId which is the lookup table:

# initialize the menu structure
$menu = []; # the menu structure
$byId = []; # menu ID-table (temporary) 

The lookup table is only necessary as long as the menu is built, it will be thrown away afterwards.

The next big step is to create the $menu by traversing over the flat array. This is a bigger foreach loop:

# build the menu (hierarchy) from flat $rows traversable
foreach ($rows as $row) {
    # map row to local ID variables
    $id = $row['id'];
    $parentId = $row['parent_id'];

    # build the entry
    $entry = $row;
    # init submenus for the entry
    $entry['submenus'] = &$byId[$id]['submenus']; # [1]

    # register the entry in the menu structure
    if (null === $parentId) {
        # special case that an entry has no parent
        $menu[] = &$entry;
    } else {
        # second special case that an entry has a parent
        $byId[$parentId]['submenus'][] = &$entry;
    }

    # register the entry as well in the menu ID-table
    $byId[$id] = &$entry;

    # unset foreach (loop) entry alias
    unset($entry);
}

This is where the entries are mapped from the flat array ($rows) into the hierarchical $menu array. No recursion is required thanks to the stack and lookup-table $byId.

The key point here is to use variable aliases (references) when adding new entries to the $menu structure as well as when adding them to $byId. This allows to access the same value in memory with two different variable names:

        # special case that an entry has no parent
        $menu[] = &$entry;
         ...

    # register the entry as well in the menu ID-table
    $byId[$id] = &$entry;

It is done with the = & assignment and it means that $byId[$id] gives access to $menu[<< new key >>].

The same is done in case it is added to a submenu:

    # second special case that an entry has a parent
    $byId[$parentId]['submenus'][] = &$entry;
...

# register the entry as well in the menu ID-table
$byId[$id] = &$entry;

Here $byId[$id] points to $menu...[ << parent id entry in the array >>]['submenus'][ << new key >> ].

This is solves the problem to always find the right place where to insert a new entry into the hierarchical structure.

To deal with the cases that a submenu comes in the flat array before the menu entry it belongs to, the submenu when initialized for new entries needs to be taken out of the lookup table (at [1]):

# init submenus for the entry
$entry['submenus'] = &$byId[$id]['submenus']; # [1]

This is a bit of a special case. In case that $byId[$id]['submenus'] is not yet set (e.g. in the first loop), it is implicitly set to null because of the reference (the & in front of &$byId[$id]['submenus']). In case it is set, the existing submenu from a not yet existing entry will be used to initialize the submenu of the entry.

Doing so is enough to not depend on any specific order in $rows.

This is what the loop does.

The rest is cleanup work:

# unset ID aliases
unset($byId); 

It unsets the look ID table as it is not needed any longer. That is, all aliases are unset.

To complete the example:

# visualize the menu structure
print_r($menu);

Which then gives the following output:

Array
(
    [0] => Array
        (
            [id] => 1
            [parent_id] => 
            [name] => Home
            [submenus] => 
        )

    [1] => Array
        (
            [id] => 2
            [parent_id] => 
            [name] => Categories
            [submenus] => Array
                (
                    [0] => Array
                        (
                            [id] => 3
                            [parent_id] => 2
                            [name] => Subcategory A
                            [submenus] => 
                        )

                    [1] => Array
                        (
                            [id] => 4
                            [parent_id] => 2
                            [name] => Subcategory B
                            [submenus] => 
                        )

                )

        )

)

I hope this is understandable and you're able to apply this on your concrete scenario. You can wrap this in a function of it's own (which I would suggest), I only kept it verbose for the example to better demonstrate the parts.

Related Q&A material:

  • Php: Converting a flat array into a tree like structure
  • Convert a series of parent-child relationships into a hierarchical tree?
  • Build a tree from a flat array in PHP
Thursday, September 23, 2021
 
daniel__
answered 4 Weeks ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :