How to Efficiently Convert a Flat Array List into a Hierarchical Tree Structure?

Converting an Array List to a Tree Structure

In this problem, we are tasked with transforming a flat array of elements into a hierarchical tree-like structure. The input array consists of objects with three properties: id, parentid, and name. The output should be a tree structure where each node represents an element in the input array and has a list of child nodes that belong to it.

To solve this problem, we cannot rely on methods like nested sets due to database constraints. Instead, we utilize a recursive algorithm to build the tree.

$arr = array(
    array('id' => 100, 'parentid' => 0, 'name' => 'a'),
    array('id' => 101, 'parentid' => 100, 'name' => 'a'),
    array('id' => 102, 'parentid' => 101, 'name' => 'a'),
    array('id' => 103, 'parentid' => 101, 'name' => 'a'),
);

$new = array();
foreach ($arr as $a) {
    $new[$a['parentid']][] = $a;
}
$tree = createTree($new, array($arr[0]));

In the first step, we loop through the input array and group elements by their parentid to create a new array where each key represents a parent's id, and the value is an array of its children. Subsequently, we invoke a helper function createTree to construct the tree recursively.

function createTree(&$list, $parent) {
    $tree = array();
    foreach ($parent as $k => $l) {
        if (isset($list[$l['id']])) {
            $l['children'] = createTree($list, $list[$l['id']]);
        }
        $tree[] = $l;
    }
    return $tree;
}

The createTree function takes two parameters: the reorganized array $list and an array $parent representing the current level in the tree. Within the function, we iterate through the $parent array and inspect if the $list contains any children for the current element. If children are found, we recursively invoke createTree to build the subtree for that element and add it as the children property of the current element. Finally, we append the current element to the $tree array and return the tree.

By following this algorithm, we can efficiently construct a tree structure from the provided array list, generating a nested representation of the hierarchical relationships between the elements.

The above is the detailed content of How to Efficiently Convert a Flat Array List into a Hierarchical Tree Structure?. For more information, please follow other related articles on the PHP Chinese website!