Asked  7 Months ago    Answers:  5   Viewed   37 times

So, my problem is, that I want to build a tree of these 2 tables:

Parent table:
+-------+---------------+
| pr_id |  parent_name  |
+-------+---------------+
|   1   |       p       |
|   2   |      p_0      | 
|   3   |     p_0_1     | 
|   4   |       q       | 
+-------+---------------+

Child table:
+-------+---------------+---------------------------+
| ch_id |     pr_id     |        child_name         |
+-------+---------------+---------------------------+
|   1   |       1       |            p_0            |
|   2   |       1       |            p_1            |
|   3   |       2       |           p_0_0           |
|   4   |       2       |           p_0_1           |
|   5   |       3       |          p_0_1_0          |
|   6   |       3       |          p_0_1_1          |
|   7   |       4       |            q_0            |
|   8   |       4       |            q_1            |
+-------+---------------+---------------------------+

And the Tree should look like:

  • p
    • p_0
      • p_0_0
      • p_0_1
        • p_0_1_0
        • p_0_1_1
  • q

Can anybody help me out with a recursive solution??

 Answers

57

You do not need to create 2 tables in the database for this you can maintain it like below from one table only

+-------+---------------+---------------------------+
|   id  |   parent_id   |           title           |
+-------+---------------+---------------------------+
|   1   |       0       |   Parent Page             |
|   2   |       1       |   Sub Page                |
|   3   |       2       |   Sub Sub Page            |
|   4   |       0       |   Another Parent Page     |
+-------+---------------+---------------------------+

The array generated will be like

Array
(
    [0] => Array
        (
            [id] => 1
            [parent_id] => 0
            [title] => Parent Page
            [children] => Array
                        (
                            [0] => Array
                                (
                                    [id] => 2
                                    [parent_id] => 1
                                    [title] => Sub Page
                                    [children] => Array
                                                (
                                                    [0] => Array
                                                        (
                                                            [id] => 3
                                                            [parent_id] => 1
                                                            [title] => Sub Sub Page
                                                        )
                                                )
                                )
                        )
        )
    [1] => Array
        (
            [id] => 4
            [parent_id] => 0
            [title] => Another Parent Page
        )
)

You need to use the below recursive function to achieve it

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

The algorithm is pretty simple:

  1. Take the array of all elements and the id of the current parent (initially 0/nothing/null/whatever).
  2. Loop through all elements.
  3. If the parent_id of an element matches the current parent id you got in 1., the element is a child of the parent. Put it in your list of current children (here: $branch).
  4. Call the function recursively with the id of the element you have just identified in 3., i.e. find all children of that element, and add them as children element.
  5. Return your list of found children.
Wednesday, March 31, 2021
 
Crontab
answered 7 Months ago
61

I think you have to add the id as parameter in your function call.

$this->categoriesTree($row['menuid']) 

Otherwise you call the function exactly the same every time.

Saturday, May 29, 2021
 
MGP
answered 5 Months ago
MGP
41

I have no idea why you want your BuildTree method return List<Group> - tree needs to have root node, so you should expect it to return single Group element, not a list.

I would create an extension method on IEnumerable<Group>:

public static class GroupEnumerable
{
    public static IList<Group> BuildTree(this IEnumerable<Group> source)
    {
        var groups = source.GroupBy(i => i.ParentID);

        var roots = groups.FirstOrDefault(g => g.Key.HasValue == false).ToList();

        if (roots.Count > 0)
        {
            var dict = groups.Where(g => g.Key.HasValue).ToDictionary(g => g.Key.Value, g => g.ToList());
            for (int i = 0; i < roots.Count; i++)
                AddChildren(roots[i], dict);
        }

        return roots;
    }

    private static void AddChildren(Group node, IDictionary<int, List<Group>> source)
    {
        if (source.ContainsKey(node.ID))
        {
            node.Children = source[node.ID];
            for (int i = 0; i < node.Children.Count; i++)
                AddChildren(node.Children[i], source);
        }
        else
        {
            node.Children = new List<Group>();
        }
    }
}

Usage

var flatList = new List<Group>() {
    new Group() { ID = 1, ParentID = null },    // root node
    new Group() { ID = 2, ParentID = 1 },
    new Group() { ID = 3, ParentID = 1 },
    new Group() { ID = 4, ParentID = 3 },
    new Group() { ID = 5, ParentID = 4 },
    new Group() { ID = 6, ParentID = 4 }
};


var tree = flatList.BuildTree();
Saturday, July 10, 2021
 
Hexaholic
answered 4 Months ago
29
def nested(flat, level=0):
    for k, it in itertools.groupby(flat, lambda x: x.split("-")[level]):
        yield next(it)
        remainder = list(nested(it, level + 1))
        if remainder:
            yield remainder

Example:

>>> list(nested(flat, 0))
['1', ['1-1', ['1-1-1'], '1-2'], '2', ['2-1', '2-2'], '3']
Sunday, August 22, 2021
 
David542
answered 2 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 :