How to display the tree in a different order? - PHP

DimaFKort
April 22, 2023
174 views
0 votes
2 Answers

In this case, the tree is displayed in this form

level 3
  level 3.1
    level 3.1.1
    level 3.1.2
      level 3.1.2.1
level 2
  level 2.1
  level 2.2
  level 2.3
level 1
  level 1.1
  level 1.2
  level 1.3
  level 1.4
    level 1.4.1

How can it be flipped so that it displays correctly?
I tried everything and nothing works

Here is the fully working code:

the rebuildTree function creates the correct structure, and the printTree function displays the result

<?php
$tree = [
   ['name' => 'level 1',     'id' => 1,  'pid' => 0],
    ['name' => 'level 1.1',   'id' => 2,  'pid' => 1],
    ['name' => 'level 1.2',   'id' => 3,  'pid' => 1],
    ['name' => 'level 1.3',   'id' => 4,  'pid' => 1],
    ['name' => 'level 2',     'id' => 5,  'pid' => 0],
    ['name' => 'level 2.1',   'id' => 6,  'pid' => 5],
    ['name' => 'level 2.2',   'id' => 7,  'pid' => 5],
    ['name' => 'level 3',     'id' => 8,  'pid' => 0],
    ['name' => 'level 3.1',   'id' => 9,  'pid' => 8],
    ['name' => 'level 3.1.1', 'id' => 10, 'pid' => 9],
    ['name' => 'level 3.1.2', 'id' => 11, 'pid' => 9],
    ['name' => 'level 1.4', 'id' => 12, 'pid' => 1],
    ['name' => 'level 2.3',   'id' => 13,  'pid' => 5],
    ['name' => 'level 3.1.2.1', 'id' => 14, 'pid' => 11],
    ['name' => 'level 1.4.1', 'id' => 15, 'pid' => 12],
];

function rebuildTree($tree){
    foreach ($tree as $key => $node) {
        $branches[$node['id']] = $node;
    }
    $rootNodes = [];
    foreach ($tree as $node) {
        if ($node['pid'] === 0) {
            $rootNodes[] = &$branches[$node['id']];
        } else {
            $branches[$node['pid']]['chld'][] = &$branches[$node['id']];
        }
    }
    return $rootNodes;
}

function printTree($tree) {
    $stack = [];
    foreach ($tree as $node) {
        if (empty($node['pid'])) {
            $stack[] = [$node, 0];
        }
    }
    
    while (!empty($stack)) {
    
        list($node, $depth) = array_pop($stack);
        
        echo str_repeat('  ', $depth) . $node['name'] . PHP_EOL;

        if (isset($node['chld'])) {
            foreach (array_reverse($node['chld']) as $child) {
                $stack[] = [$child, $depth + 1];
            }
        }
    }
}

$arr = rebuildTree($tree);
printTree($arr);

And I don’t want to use recursion, they say it’s very bad.

Tags: php tree

Answers

It can be proven they are equivalent, recursive and iterative solutions. So I’ll present to you a recursive one, first.

function printTreeRecursive($tree, $depth = 0)
{
    foreach ($tree as $node) {
        echo str_repeat('  ', $depth) . $node['name'] . PHP_EOL;
        if (isset($node['chld'])) {
            printTreeRecursive($node['chld'], $depth + 1);
        }
    }
}

Output:

level 1
  level 1.1
  level 1.2
  level 1.3
  level 1.4
    level 1.4.1
level 2
  level 2.1
  level 2.2
  level 2.3
level 3
  level 3.1
    level 3.1.1
    level 3.1.2
      level 3.1.2.1

As for non recursive, your method is perfect, except you would want to reverse the stack in the first place.

function printTree($tree)
{
    $stack = [];
    foreach ($tree as $node) {
        if (empty($node['pid'])) {
            $stack[] = [$node, 0];
        }
    }

    // add this line: 
    $stack = array_reverse($stack);

    while (!empty($stack)) {

        list($node, $depth) = array_pop($stack);

        echo str_repeat('  ', $depth) . $node['name'] . PHP_EOL;

        if (isset($node['chld'])) {
            foreach (array_reverse($node['chld']) as $child) {
                $stack[] = [$child, $depth + 1];
            }
        }
    }
}

Another possible solution without recursion, with stack and with a single loop. In the stack are saved the address of the active branch and the last processed position instead of the complete sub-branch(es).

function printTree($tree)
{
    $stack = [];
    $subTree = &$tree;  // the considered branch
    $ind = 0;

    // we test if we have more elements in the current branch or if we have an upper branch to process
    while (($into = ($ind < count($subTree)))  ||  count($stack))
    {
        if (!$into)  // if all elements of current branch are processed, we restore the upper branch
        {
            [$subTree, $ind] = array_pop($stack);
        }
        else
        {
            // let's print the string, the indentation is calculated by the stack level
            echo str_repeat(' ', (count($stack) + 1) * 2), $subTree[$ind]['name'],  PHP_EOL;

            // if there's a child branch we save the current processing branch and position
            // and we prepare to process the sub-branch
            if ($subTree[$ind]['chld'] ?? false)
            {
                $stack[] = [&$subTree, $ind];
                $subTree = &$subTree[$ind]['chld'];
                $ind = -1;  // will become 0 in the next instruction ~ if you don't like it use: $ind = 0; continue;
            }
        }

        $ind++;
    }
}

Please signup or login to give your own answer.

Click here to cancel reply.

How to display the tree in a different order? – PHP

Answers