如何以不同的顺序显示树？

Question

在这种情况下，树以这种形式显示

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

如何翻转才能正确显示？ 我尝试了一切，但没有任何效果

这是完整的工作代码：

rebuildTree 函数创建正确的结构，printTree 函数显示结果

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

而且我不想使用递归，他们说这很糟糕。

Answer 1

可以证明它们是等价的递归迭代解。所以我先给你一个递归的。

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

输出：

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

至于非递归，你的方法是完美的，除了你首先想要反转堆栈。

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];
            }
        }
    }
}

Answer 2

另一种没有递归的可能解决方案，使用堆栈和单个循环。在堆栈中保存的是活动分支的地址和最后处理的位置，而不是完整的子分支。

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++;
    }
}