当前位置：首页 > PHP

php 实现树

2026-02-14 11:52:04PHP

实现树结构的方法

在PHP中实现树结构通常需要定义节点类并管理父子关系。以下是几种常见方法：

使用递归类结构

定义一个节点类，包含子节点数组和递归方法：

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

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

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

    public function traverse() {
        echo $this->value . "\n";
        foreach ($this->children as $child) {
            $child->traverse();
        }
    }
}

使用嵌套集合模型

适合数据库存储的树结构实现方式：

class NestedSetTree {
    private $left = 'lft';
    private $right = 'rgt';
    private $table = 'tree_nodes';

    public function getDescendants($nodeId) {
        // 查询所有左值大于当前节点且右值小于当前节点的记录
        $query = "SELECT * FROM {$this->table} 
                 WHERE {$this->left} > (SELECT {$this->left} FROM {$this->table} WHERE id = ?)
                 AND {$this->right} < (SELECT {$this->right} FROM {$this->table} WHERE id = ?)";
        // 执行数据库查询...
    }
}

使用闭包表设计

另一种数据库友好的树结构实现：

class ClosureTableTree {
    private $table = 'tree_closure';
    private $nodeTable = 'tree_nodes';

    public function addNode($parentId, $nodeData) {
        // 插入新节点
        $newNodeId = $this->insertNode($nodeData);

        // 在闭包表中建立关系
        $this->db->query("INSERT INTO {$this->table} (ancestor, descendant, depth)
                         SELECT ancestor, $newNodeId, depth+1 FROM {$this->table}
                         WHERE descendant = $parentId
                         UNION ALL SELECT $newNodeId, $newNodeId, 0");
    }
}

使用多维数组

简单的内存树结构实现：

php 实现树

$tree = [
    'value' => 'root',
    'children' => [
        [
            'value' => 'child1',
            'children' => []
        ],
        [
            'value' => 'child2',
            'children' => [
                ['value' => 'grandchild1', 'children' => []]
            ]
        ]
    ]
];

function traverseTree($node) {
    echo $node['value'] . "\n";
    foreach ($node['children'] as $child) {
        traverseTree($child);
    }
}

树操作常用方法

深度优先搜索

function dfs(TreeNode $node) {
    echo $node->value . "\n";
    foreach ($node->children as $child) {
        dfs($child);
    }
}

广度优先搜索

function bfs(TreeNode $root) {
    $queue = [$root];
    while (!empty($queue)) {
        $node = array_shift($queue);
        echo $node->value . "\n";
        foreach ($node->children as $child) {
            $queue[] = $child;
        }
    }
}

查找节点

function findNode(TreeNode $node, $value) {
    if ($node->value == $value) {
        return $node;
    }
    foreach ($node->children as $child) {
        $found = findNode($child, $value);
        if ($found) {
            return $found;
        }
    }
    return null;
}