PHP树形结构遍历：如何高效查找所有根节点及其子节点？-php教程-PHP中文网

PHP树形结构遍历：如何高效查找所有根节点及其子节点？

聖光之護

发布： 2025-03-16 10:14:17

原创

641人浏览过

php树形结构遍历：如何高效查找所有根节点及其子节点？

PHP树形结构遍历：精准定位所有根节点及其子节点

在PHP开发中，处理树形结构数据是常见任务。本文提供一种高效的PHP算法，用于遍历树形结构并找出所有根节点及其所有子节点。

我们使用数组表示树形结构，每个节点包含node值和children数组（包含其子节点的node值）。目标是识别所有根节点（无父节点的节点）及其所有后代节点。

算法的核心在于：首先识别根节点，然后递归遍历找到所有子节点。

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

以下代码及注释详细解释了实现过程：

造点AI

夸克 · 造点AI

325

查看详情

代码首先定义一个示例树形结构数组$tree。然后，它遍历$tree，收集所有子节点到$children数组中。通过比较$tree中每个节点的node值是否在$children数组中，即可判断该节点是否为根节点。所有根节点的node值被收集到$roots数组中。

接下来，递归函数findSubtree用于遍历树形结构。它接收两个参数：$tree（当前遍历的树）和$roots（当前遍历的节点）。函数使用静态变量$result存储最终结果，避免重复初始化。

每次递归调用中，函数先将$roots中的节点添加到$result。然后，它遍历$tree，找到$roots中存在的节点，并将它们的子节点添加到$nextRoots数组中。这些子节点将在下一次递归调用中被遍历。已访问的节点从$tree中移除，避免重复访问。

递归过程持续进行，直到$tree为空，此时$result包含所有根节点及其所有子节点。最后，$result被打印。

<?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 $v) {
    $children = array_merge($children, $v['children']);
}

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

// 递归查找子树
function findSubtree(&$tree, $roots) {
    static $result = [];
    $result = array_merge($result, $roots);

    if ($tree) {
        $nextRoots = [];
        foreach ($tree as $k => $item) {
            if (in_array($item['node'], $roots)) {
                $nextRoots = array_merge($nextRoots, $item['children']);
                unset($tree[$k]); //移除已访问节点
            }
        }
        return findSubtree($tree, $nextRoots);
    } else {
        return $result;
    }
}

$result = findSubtree($tree, $roots);
print_r($result); // 输出所有根节点及其子节点
?>

登录后复制

这段代码清晰地展示了如何使用递归算法高效解决问题，注释也详细解释了每一步逻辑。通过这种方法，可以有效地遍历树形结构并提取所需信息。

以上就是PHP树形结构遍历：如何高效查找所有根节点及其子节点？的详细内容，更多请关注php中文网其它相关文章！