PHP树形数组遍历：如何找出所有根节点及其子孙节点？

php树形结构遍历：寻找根节点及后续节点

本文将解答一个关于php树形结构遍历的算法问题。题目要求从一个类似树结构的数组中找出所有根节点及其子孙节点。 该树结构并非标准的树结构，而是使用一个数组，其中每个元素包含一个节点值('node')和其子节点数组('children')。

问题描述：给定一个如下所示的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]]
];

解决方法：

算法的核心思想是先找到所有根节点，然后递归遍历其子节点。 具体步骤如下：

Vondy

下一代AI应用平台，汇集了一流的工具/应用程序

下载

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

1. 找到第一层节点（根节点）： 通过遍历整个数组，判断每个节点的'node'值是否出现在任何其他节点的'children'数组中。 如果一个节点的'node'值不在任何'children'数组中，则该节点为根节点。
2. 递归查找： 利用递归函数，遍历每个根节点的子节点。 在递归过程中，将已访问的节点从数组中移除，避免重复访问。 递归函数使用静态变量$result来存储所有已访问的节点。

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

// 找出第一层
$loop = [];
foreach ($tree as $item) {
    if (!in_array($item['node'], $children)) {
        $loop[] = $item['node'];
    }
}

// 递归找结果
function recursion(&$tree, $loop)
{
    static $result = [];
    $result = array_merge($result, $loop);

    if ($tree) {
        $next_children = [];
        foreach ($tree as $k => $item) {
            if (in_array($item['node'], $loop)) {
                $next_children = array_merge($next_children, $item['children']);
                unset($tree[$k]);
            }
        }
        return recursion($tree, $next_children);
    } else {
        return $result;
    }
}

$result = recursion($tree, $loop);

print_r($result);

// 结果
// Array ( [0] => 7 [1] => 10 [2] => 2 [3] => 11 [4] => 3 [5] => 9 [6] => 4 [7] => 6 [8] => 5 [9] => 8 )
?>

这段代码实现了题目要求的功能，通过先找到根节点，然后递归遍历所有子节点，最终输出所有节点。 需要注意的是，递归函数中使用了静态变量$result来存储结果，以及unset操作来避免重复访问节点。