如何调整PHP树形结构的显示顺序？非递归实现求助

当前PHP代码中，rebuildTree函数可生成正确的树形结构，但printTree函数输出的树顺序颠倒（根节点显示为level 3、level 2、level 1的逆序），需调整为正确顺序且不使用递归实现。

当前错误输出 #

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

完整原始代码 #

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

问题分析与解决方案 #

问题出在栈的后进先出（LIFO）特性：

• 原始代码中，根节点按level 1→level 2→level 3的顺序入栈，使用array_pop弹出时会从栈顶先取出level 3，导致根节点顺序颠倒。
• 子节点部分的array_reverse是正确的：子节点正序入栈会导致弹出顺序反转，因此反转后入栈才能保证子节点按原始顺序输出。

只需修改printTree函数中根节点的入栈顺序，将根节点列表反转后再入栈，即可保证弹出时按原始顺序输出。

修改后的printTree函数 #

function printTree($tree) {
    $stack = [];
    // 反转根节点列表后入栈，抵消栈后进先出的顺序影响
    foreach (array_reverse($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];
            }
        }
    }
}

修正后的输出 #

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

内容的提问来源于stack exchange，提问作者DimaFKort