How to convert a flat array to hierarchical tree array?

Question

I want to know how I can write a method to convert a flat array of any size to a hierarchical tree (look at examples). Can anyone suggest a way to do this? Also, can this be done without using a large amount of resources?

Here is my example:

Flat Array:

$categories = array(
    array(
        'id' => 1,
        'sub' => 0
    ),
    array(
        'id' => 2,
        'sub' => 1
    ),
    array(
        'id' => 3,
        'sub' => 1
    ),
    array(
        'id' => 4,
        'sub' => 2
    ),
    array(
        'id' => 5,
        'sub' => 2
    ),
    array(
        'id' => 6,
        'sub' => 4
    ),
    array(
        'id' => 7,
        'sub' => 0
    )
);

Hierarchical Tree:

$categories = array(
    array(
        'id' => 1,
        'sub' => 0,
        'children' => array(
            array(
                'id' => 2,
                'sub' => 1,
                'children' => array(
                    array(
                        'id' => 4,
                        'sub' => 2,
                        'children' => array(
                            array(
                                'id' => 6,
                                'sub' => 4,
                                'children' => array()
                            )
                        )
                    ),
                    array(
                        'id' => 5,
                        'sub' => 2,
                        'children' => array()
                    )
                )
            ),
            array(
                'id' => 3,
                'sub' => 1,
                'children' => array()
            ),
        )
    ),
    array(
        'id' => 7,
        'sub' => 0,
                'children' => array()
    )
);

possible duplicate of [Flat PHP Array to Hierarchy Tree](http://stackoverflow.com/questions/14740429/flat-php-array-to-hierarchy-tree) — Michal Brašna, Feb 19 '14 at 14:24

score 1 · Answer 1 · answered Feb 19 '14 at 15:18

i propose object-oriented approach

a. simple class representing node, with methods to addChild and transform self to array:

class TreeNode {
        public $id;
        public $parent;
        private $children;

        public function __construct($dataArray) {
                $this->id = $dataArray['id'];
                $this->parent = $dataArray['sub'];
                $this->children = array();
        }

        public function addChild(TreeNode $node) {
                $this->children[$node->id] = $node;
        }

        public function toArray() {
                return array(
                        'id'  => $this->id,
                        'sub' => $this->parent,
                        'children' => array_map(
                           function(TreeNode $element) { 
                             return $element->toArray();
                           }, $this->children
                         )
                );
        }
}

b. create flat array of TreeNodes from flat $categories array , and determinate roots of trees

$nodes = array();
$rootNodes = array();
foreach($categories as $category) {
        $nodes[$category['id']] = new TreeNode($category);
        if ($category['sub'] == 0) {
                $rootNodes[] = $nodes[$category['id']];
        }
}

c. add childs to TreeNodes

array_map(
  function(TreeNode $element) use($nodes){ 
    if(isset($nodes[$element->parent])) 
      $nodes[$element->parent]->addChild($element);
  }, $nodes
);

d. convert trees to array starting from roots

print_r(array_map(
  function(TreeNode $element) { 
    return $element->toArray();
  }, $rootNodes)
);

Thanks man. But, can you have idea how do it with categories, which created like this: foreach ($categories as $c) { $cats[] = array( 'name' => $c->name, 'count' => $c->count, 'id' => $c->id, 'description' => $c->description, 'sub' => $c->sub, 'products' => $c->products, 'status' => $c->status, 'level' => $level ); } Because that this was an example. — user3324208, Feb 19 '14 at 15:42
You can wrap $c in TreeNode instead of example array, and produce final array in toArray method from $this->c object — ziollek, Feb 19 '14 at 15:44
And remove __construct, toArray() and point D? And my solution is at point C? Need in a form in which the data come. — user3324208, Feb 19 '14 at 15:47
in point a. function __construct($c) { $this->id = $c->id; $this->parent = $c->sub; $this->c = $c; $this->children = array();}/// function toArray() { $c = $this->c; return array( 'name' => $c->name, 'count' => $c->count, 'id' => $c->id, 'description' => $c->description, 'sub' => $c->sub, 'products' => $c->products, 'status' => $c->status, 'level' => $level, 'children' => ...[without changes] ); } point b. instead array $category you use $c object point c. without changes point d. without changes — ziollek, Feb 19 '14 at 15:52

How to convert a flat array to hierarchical tree array?

1 Answers1