Reputation: 24798
I use PHP and mySQL with Idiorm. That might not be relevant.
My PHP array
This array structure can be changed if needed for solving the problem.
array (
33 =>
array (
0 => '27',
1 => '41',
),
27 =>
array (
0 => '64',
1 => '71',
),
0 =>
array (
0 => '28',
1 => '29',
2 => '33',
),
)
My hierarchical result
Something like this, but as an array...
0 =>
28
29
33
27 =>
64
71
41
Information
My own thoughts
I tried both of the above, just got a mess. It's a brainer.
Upvotes: 27
Views: 62834
Reputation: 71
I had a different problem and could not find a solution that worked for me on this page. I needed to create a tree but without knowing the root id. This means I have to go through my flat array and build branches with the most parently items at the top of the tree.
If anyone else needs to build a tree without a root parent item id, here's how I did it.
<?php
$rows = [
(object) [
'id' => 1001,
'parentid' => 1000,
'name' => 'test1.1'
],
(object) [
'id' => 1000,
'parentid' => 100,
'name' => 'test1'
],
(object) [
'id' => 1002,
'parentid' => 1000,
'name' => 'test1.2'
],
(object) [
'id' => 1004,
'parentid' => 1001,
'name' => 'test1.1.1'
],
(object) [
'id' => 1005,
'parentid' => 1004,
'name' => 'test1.1.1.1'
],
(object) [
'id' => 100,
'parentid' => 10,
'name' => 'test 0'
],
(object) [
'id' => 1006,
'parentid' => 1002,
'name' => 'test1.2.1'
],
(object) [
'id' => 1007,
'parentid' => 1002,
'name' => 'test1.2.2'
],
];
function add_child(stdClass $parent, stdClass $child) {
if ($child->parentid != $parent->id) {
throw new Exception('Attempting to add child to wrong parent');
}
if (empty($parent->children)) {
$parent->children = [];
} else {
// Deal where already in branch.
foreach ($parent->children as $idx => $chd) {
if ($chd->id === $child->id) {
if (empty($chd->children)) {
// Go with $child, since $chd has no children.
$parent->children[$idx] = $child;
return;
} else {
if (empty($child->children)) {
// Already has this child with children.
// Nothing to do.
return;
} else {
// Both childs have children - merge them.
$chd->children += $child->children;
$parent->children[$idx] = $child;
return;
}
}
}
}
}
$parent->children[] = $child;
}
function build_branch(&$branch, &$rows, &$parent = null) {
$hitbottom = false;
while (!$hitbottom) {
$foundsomething = false;
// Pass 1 - find children.
$removals = []; // Indexes of rows to remove after this loop.
foreach ($rows as $idx => $row) {
if ($row->parentid === $branch->id) {
// Found a child.
$foundsomething = true;
// Recurse - find children of this child.
build_branch($row, $rows, $branch);
add_child($branch, $row);
$removals[] = $idx;
}
}
foreach ($removals as $idx) {
unset($rows[$idx]);
}
// Pass 2 - find parents.
if ($parent === null) {
$foundparent = false;
foreach ($rows as $idx => $row) {
if ($row->id === $branch->parentid) {
// Found parent
$foundsomething = true;
$foundparent = true;
add_child($row, $branch);
unset ($rows[$idx]);
// Now the branch needs to become the parent since parent contains branch.
$branch = $row;
// No need to search for other parents of this branch.
break;
}
}
}
$hitbottom = !$foundsomething;
}
}
function build_tree(array $rows) {
$tree = [];
while (!empty($rows)) {
$row = array_shift($rows);
build_branch($row, $rows);
$tree[] = $row;
}
return $tree;
}
$tree = build_tree($rows);
print_r($tree);
Upvotes: 0
Reputation: 78
public function createTree (&$list, $parentId = null) {
$tree = array();
foreach ($list as $key => $eachNode) {
if ($eachNode['parentId'] == $parentId) {
$eachNode['children'] = $this->createTree ($list,$eachNode['id']);
$tree[] = $eachNode;
unset($list[$key]);
}
}
return $tree;
}
In that function pass the associative array and if the most parent is not null then just pass the most parent id as second argument.
Upvotes: 0
Reputation: 1497
great answer from @Jens Törnell, just wanted to add a little improvement that if your parent_id and id is actually string instead of number then above method will fail and after creating children array, it will create those childrens arrays again as separate individual array. In order to fix that you should do triple equal check and by telling data type of variable i.e (string) in comparison.
For string based Id and Parent_id in array
function buildTree(array $elements, $parentId = 0) {
$branch = array();
foreach ($elements as $element) {
if ((string)$element['parent_id'] === (string)$parentId) {
$children = buildTree($elements, $element['id']);
if ($children) {
$element['children'] = $children;
}
$branch[] = $element;
}
}
return $branch;
}
additionally if someone desire, he can add a third parameter to function as well to specify data type of variables dynamically i.e function buildTree(array $elements, $parentId = 0, $datatype='string')
but then you will have to take of any other error occur.
hope it will help someone!
Upvotes: 4
Reputation: 914
I added to @Jens Törnell's answers to enable defining the options for the column name of parent_id, the children array key name, and also the column name for id.
/**
* function buildTree
* @param array $elements
* @param array $options['parent_id_column_name', 'children_key_name', 'id_column_name']
* @param int $parentId
* @return array
*/
function buildTree(array $elements, $options = [
'parent_id_column_name' => 'parent_id',
'children_key_name' => 'children',
'id_column_name' => 'id'], $parentId = 0)
{
$branch = array();
foreach ($elements as $element) {
if ($element[$options['parent_id_column_name']] == $parentId) {
$children = buildTree($elements, $options, $element[$options['id_column_name']]);
if ($children) {
$element[$options['children_key_name']] = $children;
}
$branch[] = $element;
}
}
return $branch;
}
Since the functionality is quite universal, I managed to use the above function in most of my projects.
Upvotes: 9
Reputation: 24798
The suggestion by @deceze worked. However the input array needs to change a litte, like this...
$rows = array(
array(
'id' => 33,
'parent_id' => 0,
),
array(
'id' => 34,
'parent_id' => 0,
),
array(
'id' => 27,
'parent_id' => 33,
),
array(
'id' => 17,
'parent_id' => 27,
),
);
From https://stackoverflow.com/a/8587437/476:
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;
}
}
return $branch;
}
$tree = buildTree($rows);
print_r( $tree );
Upvotes: 69