PHP树形结构遍历：精准定位所有根节点及其子节点
在PHP开发中，处理树形结构数据是常见任务。本文提供一种高效的PHP算法，用于遍历树形结构并找出所有根节点及其所有子节点。
我们使用数组表示树形结构，每个节点包含node值和children数组（包含其子节点的node值）。目标是识别所有根节点（无父节点的节点）及其所有后代节点。
算法的核心在于：首先识别根节点，然后递归遍历找到所有子节点。
立即学习“PHP免费学习笔记（深入）”；
以下代码及注释详细解释了实现过程：
代码首先定义一个示例树形结构数组$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); // 输出所有根节点及其子节点
?>
这段代码清晰地展示了如何使用递归算法高效解决问题，注释也详细解释了每一步逻辑。 通过这种方法，可以有效地遍历树形结构并提取所需信息。
