当前位置：首页 > PHP

php 实现树

2026-02-28 11:03:43PHP

PHP 实现树结构的方法

在 PHP 中实现树结构通常用于处理层级数据，如菜单、分类或组织架构。以下是几种常见的实现方式：

使用递归方法构建树

递归是处理树结构的经典方法。通过递归函数可以遍历树的每个节点。

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

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

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

// 构建树
$root = new TreeNode('Root');
$child1 = new TreeNode('Child 1');
$child2 = new TreeNode('Child 2');
$root->addChild($child1);
$root->addChild($child2);

// 递归遍历树
function traverseTree(TreeNode $node) {
    echo $node->value . "\n";
    foreach ($node->children as $child) {
        traverseTree($child);
    }
}

traverseTree($root);

使用数组表示树结构

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

$tree = [
    'value' => 'Root',
    'children' => [
        [
            'value' => 'Child 1',
            'children' => []
        ],
        [
            'value' => 'Child 2',
            'children' => []
        ]
    ]
];

从数据库构建树

当数据存储在数据库中时，通常使用邻接列表模型（Adjacency List Model）。

CREATE TABLE tree_nodes (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    parent_id INT NULL,
    FOREIGN KEY (parent_id) REFERENCES tree_nodes(id)
);

通过查询数据库并构建树：

function buildTree(array $elements, $parentId = null) {
    $branch = [];
    foreach ($elements as $element) {
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[] = $element;
        }
    }
    return $branch;
}

// 假设从数据库获取所有节点
$elements = [
    ['id' => 1, 'name' => 'Root', 'parent_id' => null],
    ['id' => 2, 'name' => 'Child 1', 'parent_id' => 1],
    ['id' => 3, 'name' => 'Child 2', 'parent_id' => 1]
];

$tree = buildTree($elements);
print_r($tree);

使用预排序遍历树（MPTT）

对于大型树结构，Modified Preorder Tree Traversal（MPTT）算法更高效。这种方法通过为每个节点分配左右值来实现快速查询。

CREATE TABLE tree_nodes (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    lft INT NOT NULL,
    rgt INT NOT NULL
);

PHP 实现：

class MPTT {
    private $db;

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

    public function rebuildTree($parent = 0, $left = 1) {
        $right = $left + 1;
        $stmt = $this->db->prepare("SELECT id FROM tree_nodes WHERE parent_id = ?");
        $stmt->execute([$parent]);
        $children = $stmt->fetchAll(PDO::FETCH_COLUMN);

        foreach ($children as $id) {
            $right = $this->rebuildTree($id, $right);
        }

        $stmt = $this->db->prepare("UPDATE tree_nodes SET lft = ?, rgt = ? WHERE id = ?");
        $stmt->execute([$left, $right, $parent]);
        return $right + 1;
    }
}

使用第三方库

对于复杂的树操作，可以考虑使用专门的库：

Nette\Utils\Tree：Nette 框架提供的树结构工具
Doctrine Extensions：包含树行为扩展
KnpLabs/DoctrineBehaviors：提供树功能

安装 KnpLabs/DoctrineBehaviors：

composer require knplabs/doctrine-behaviors

使用示例：

use Knp\DoctrineBehaviors\Model\Tree\Node;
use Knp\DoctrineBehaviors\Model\Tree\NodeInterface;

class Category implements NodeInterface {
    use Node;

    // ...
}

树结构的常见操作

查找节点

function findNode($tree, $value) {
    if ($tree['value'] == $value) {
        return $tree;
    }
    foreach ($tree['children'] as $child) {
        $found = findNode($child, $value);
        if ($found) {
            return $found;
        }
    }
    return null;
}

计算树深度

function treeDepth($node) {
    if (empty($node['children'])) {
        return 1;
    }
    $maxDepth = 0;
    foreach ($node['children'] as $child) {
        $depth = treeDepth($child);
        if ($depth > $maxDepth) {
            $maxDepth = $depth;
        }
    }
    return $maxDepth + 1;
}

扁平化树结构

function flattenTree($node, &$result = []) {
    $result[] = $node['value'];
    foreach ($node['children'] as $child) {
        flattenTree($child, $result);
    }
    return $result;
}

以上方法涵盖了 PHP 中实现树结构的主要技术，从简单到复杂，适用于不同场景需求。

php 实现树