插件窝 干货文章 PHP树形结构:如何高效遍历并按层次输出所有节点?

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

节点 遍历 TreeNode 树形 41    来源:    2025-03-14

在PHP中,处理树形结构并高效遍历并按层次输出所有节点,可以使用广度优先搜索(BFS)算法。BFS算法非常适合按层次遍历树形结构,因为它会先访问当前层的所有节点,然后再访问下一层的节点。

下面是一个示例代码,展示如何使用BFS遍历树形结构并按层次输出所有节点:

<?php

class TreeNode {
    public $value;
    public $children = [];

    public function __construct($value) {
        $this->value = $value;
    }

    public function addChild(TreeNode $child) {
        $this->children[] = $child;
    }
}

function bfsTraversal(TreeNode $root) {
    $queue = new SplQueue();
    $queue->enqueue($root);

    $level = 0;

    while (!$queue->isEmpty()) {
        $levelSize = $queue->count();
        echo "Level $level: ";

        for ($i = 0; $i < $levelSize; $i++) {
            $currentNode = $queue->dequeue();
            echo $currentNode->value . " ";

            foreach ($currentNode->children as $child) {
                $queue->enqueue($child);
            }
        }

        echo "\n";
        $level++;
    }
}

// 示例树结构
$root = new TreeNode('A');
$nodeB = new TreeNode('B');
$nodeC = new TreeNode('C');
$nodeD = new TreeNode('D');
$nodeE = new TreeNode('E');
$nodeF = new TreeNode('F');
$nodeG = new TreeNode('G');

$root->addChild($nodeB);
$root->addChild($nodeC);
$nodeB->addChild($nodeD);
$nodeB->addChild($nodeE);
$nodeC->addChild($nodeF);
$nodeF->addChild($nodeG);

// 执行BFS遍历
bfsTraversal($root);

?>

代码解释:

  1. TreeNode类:表示树中的一个节点,包含节点的值和子节点列表。
  2. bfsTraversal函数:使用BFS算法遍历树,并按层次输出节点。
    • 使用SplQueue来实现队列,用于存储待访问的节点。
    • 外层循环处理每一层的节点,内层循环处理当前层的所有节点。
    • 对于每个节点,输出其值,并将其子节点加入队列中。
    • 每处理完一层,输出换行符并增加层次计数。

输出结果:

Level 0: A 
Level 1: B C 
Level 2: D E F 
Level 3: G 

总结:

  • BFS算法:适合按层次遍历树形结构,能够高效地输出每一层的节点。
  • 队列的使用:通过队列来管理待访问的节点,确保按层次顺序访问。
  • 时间复杂度:O(n),其中n是树中节点的数量,因为每个节点都会被访问一次。

这种方法适用于大多数树形结构的遍历需求,并且能够高效地按层次输出节点。