Build a Nested Set Tree

Question

From flat array:

$tmp = array( array('id' => 0, 'level' => 0, 'name' => 'root', 'left' => 1, 'right' => 13), array('id' => 1, 'level' => 1, 'name' => 'Техотдел', 'left' => 2, 'right' => 8), array('id' => 2, 'level' => 1, 'name' => 'Отдел кадров', 'left' => 9, 'right' => 10), array('id' => 3, 'level' => 1, 'name' => 'Экономический отдел', 'left' => 11, 'right' => 12), array('id' => 4, 'level' => 2, 'name' => 'Подотдел техотдела 1', 'left' => 3, 'right' => 6), array('id' => 5, 'level' => 2, 'name' => 'Подотдел техотдела 2', 'left' => 7, 'right' => 8), array('id' => 6, 'level' => 3, 'name' => 'Подподотдел техотдела 1', 'left' => 4, 'right' => 5), );

You need to build a tree view:

 $tree = array( array( 'id' => 0, 'level' => 0, 'name' => 'root', 'children' => array( array( 'id' => 1, 'level' => 1, 'name' => 'Техотдел', 'children' => array( array( 'id' => 4, 'level' => 2, 'name' => 'Подотдел техотдела 1', 'children' => array( array( 'id' => 6, 'level' => 3, 'name' => 'Подподотдел техотдела 1' ), ), ), array( 'id' => 5, 'level' => 2, 'name' => 'Подотдел техотдела 2' ), ), ), array( 'id' => 2, 'level' => 1, 'name' => 'Отдел кадров' ), array( 'id' => 3, 'level' => 1, 'name' => 'Экономический отдел' ), ) ), );

Breaking my head, I can not figure out how to do it.

and generally the principle of constructing such a tree on the available data.
An example because the source data and the result tree correspond to each other?
where information about the parent node is stored, or about descendants?
@teran these keys organize storage of hierarchical data structures in a relational database - getinfo.ru/article610.html

Accepted Answer · 2018-09-27T11:21:02

Probably, the solution algorithm does not exist alone, so a simple variant of construction:

First, we define the maximum depth and decompose the array into levels:

 $lmax = max(array_column($tmp, 'level')); $levels = array_fill(0, $lmax, []); foreach($tmp as $node){ $levels[$node['level']][] = $node + ['children' => []]; }

Now we define the construction function itself. At the entrance you need a parent node. We will sort through the elements that lie on the level below. If the bottom element fits under the boundary conditions, then add it to the children . Next, run the recursion.

 $build = function(&$root) use (&$build, $levels){ $l = $root['level'] + 1; if(!isset($levels[$l])) return; foreach($levels[$l] as &$n){ if(($n['id'] >= $root['left']) && ($n['id'] <= $root['right'])){ $root['children'][] = &$n; $build($n); } } };

Attention should be paid to the use of references & both in the looping cycle and when added to children

It remains to run this thing.

 $root = $levels[0][0]; $build($root); print_r($root);

The output is the desired structure.

In principle, you can simultaneously remove items from the $levels that we bring in children so that they will not be sorted out the next time (in recursion).

I deal with php 5.3.13 (:, freaked out globals and it all worked. Thank you very much!

Build a Nested Set Tree

1 answer 1

More articles: