PHP树形结构：如何高效遍历并按层次输出所有节点？

高效遍历PHP树形结构并按层次输出所有节点

本文探讨一种高效的PHP算法，用于遍历树形结构数据并按层次顺序输出所有节点。给定一个树形数组，目标是找到所有根节点，并以层次遍历的方式输出所有节点的值。

问题描述：

假设我们有一个类似以下结构的树形数组：

立即学习“PHP免费学习笔记（深入）”；

$tree = [
    ['node' => 2, 'children' => [3, 9, 4]],
    ['node' => 7, 'children' => [2]],
    ['node' => 3, 'children' => [6]],
    ['node' => 4, 'children' => [5]],
    ['node' => 5, 'children' => [8]],
    ['node' => 10, 'children' => [11]]
];

我们需要编写PHP代码，遍历此树形结构，并按层次遍历的顺序输出所有节点的值。

算法思路与代码实现：

PathFinder

AI驱动的销售漏斗分析工具

下载

该算法的核心在于识别根节点并递归遍历其子节点。步骤如下：

1. 根节点识别： 确定哪些节点是根节点。一个节点是根节点的条件是：它的node值不在任何其他节点的children数组中。

2. 递归遍历： 使用递归函数遍历树。该函数接收当前节点集合和已访问节点集合作为参数，依次处理每个节点。如果节点是根节点或已被访问，则将其添加到结果数组中，并递归处理其子节点。

以下为完整的PHP代码实现：

<?php
$tree = [
    ['node' => 2, 'children' => [3, 9, 4]],
    ['node' => 7, 'children' => [2]],
    ['node' => 3, 'children' => [6]],
    ['node' => 4, 'children' => [5]],
    ['node' => 5, 'children' => [8]],
    ['node' => 10, 'children' => [11]]
];

// 收集所有子节点
$children = [];
foreach ($tree as $item) {
    $children = array_merge($children, $item['children']);
}

// 查找根节点
$roots = [];
foreach ($tree as $item) {
    if (!in_array($item['node'], $children)) {
        $roots[] = $item['node'];
    }
}

// 递归函数进行层次遍历
function traverse($tree, $roots, &$result) {
    if (empty($roots)) return;

    foreach ($roots as $root) {
        $result[] = $root;
        foreach ($tree as $item) {
            if ($item['node'] === $root) {
                traverse($tree, $item['children'], $result);
                break; // 避免重复遍历
            }
        }
    }
}

$result = [];
traverse($tree, $roots, $result);

print_r($result); // 输出层次遍历结果
?>

此代码首先收集所有子节点，然后找到根节点。traverse 函数递归地遍历树，将节点按层次顺序添加到$result数组中。 使用 break; 避免了不必要的重复遍历，提高了效率。

最终输出结果将是层次遍历的节点顺序。 此方法清晰、高效，避免了不必要的数组操作，更易于理解和维护。