当前位置：首页 > PHP

php实现树

2026-01-13 12:32:49PHP

PHP实现树结构的方法

在PHP中实现树结构通常可以通过递归或迭代的方式完成。以下是几种常见的实现方法：

递归实现树结构

递归是处理树结构的自然方式，尤其适用于具有未知深度的树。

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

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

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

function buildTree($data, $parentId = 0) {
    $tree = [];
    foreach ($data as $item) {
        if ($item['parent_id'] == $parentId) {
            $node = new TreeNode($item['id']);
            $children = buildTree($data, $item['id']);
            if ($children) {
                $node->children = $children;
            }
            $tree[] = $node;
        }
    }
    return $tree;
}

使用数组实现树结构

对于简单的树结构，可以直接使用PHP数组来表示。

function buildArrayTree($items, $parentId = 0) {
    $branch = [];
    foreach ($items as $item) {
        if ($item['parent_id'] == $parentId) {
            $children = buildArrayTree($items, $item['id']);
            if ($children) {
                $item['children'] = $children;
            }
            $branch[] = $item;
        }
    }
    return $branch;
}

使用邻接列表模型

邻接列表是数据库中存储树结构的常见方式，可以通过单次查询获取所有节点。

function buildTreeFromAdjacencyList($pdo) {
    $stmt = $pdo->query('SELECT id, parent_id, name FROM tree_nodes');
    $items = $stmt->fetchAll(PDO::FETCH_ASSOC);

    $tree = [];
    $references = [];

    foreach ($items as &$item) {
        $references[$item['id']] = &$item;
        $item['children'] = [];
    }

    foreach ($items as &$item) {
        if ($item['parent_id'] && isset($references[$item['parent_id']])) {
            $references[$item['parent_id']]['children'][] = &$item;
        } else {
            $tree[] = &$item;
        }
    }

    return $tree;
}

使用嵌套集模型

嵌套集模型是另一种数据库存储树结构的方法，查询效率更高但更新较复杂。

function getNestedSetTree($pdo) {
    $stmt = $pdo->query('SELECT id, lft, rgt, name FROM nested_set ORDER BY lft');
    return $stmt->fetchAll(PDO::FETCH_ASSOC);
}

function displayNestedSetTree($tree, $level = 0) {
    foreach ($tree as $node) {
        echo str_repeat(' ', $level * 4) . $node['name'] . "\n";
        // 这里可以根据lft和rgt值判断是否有子节点
    }
}

使用预排序遍历树算法(MPTT)

MPTT是对嵌套集模型的改进，适合频繁读取但较少更新的场景。

class MPTT {
    private $pdo;
    private $table = 'tree';

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

    public function rebuildTree($parent = 0, $left = 1) {
        $right = $left + 1;
        $stmt = $this->pdo->prepare("SELECT id FROM {$this->table} WHERE parent_id = ?");
        $stmt->execute([$parent]);

        while ($row = $stmt->fetch(PDO::FETCH_ASSOC)) {
            $right = $this->rebuildTree($row['id'], $right);
        }

        $update = $this->pdo->prepare("UPDATE {$this->table} SET lft = ?, rgt = ? WHERE id = ?");
        $update->execute([$left, $right, $parent]);

        return $right + 1;
    }
}

使用第三方库

对于复杂项目，可以考虑使用专门的树结构处理库：

NestedTree：基于Doctrine的嵌套集实现
TreeBehavior：CakePHP的树行为扩展
baum/baum：Laravel的嵌套集实现

// 使用baum/baum示例
use Baum\Node;

class Category extends Node {
    protected $table = 'categories';
}

// 创建树节点
$root = Category::create(['name' => 'Root']);
$child1 = Category::create(['name' => 'Child 1']);
$child1->makeChildOf($root);