PHP树结构实现与遍历算法

PHP树结构实现与遍历算法

树是编程中常用的数据结构。分类、组织架构、评论回复都可以用树来表示。今天说说PHP中树结构的实现。

二叉树是最基本的树结构。

```php
class TreeNode
{
public function __construct(
public mixed $data,
public ?TreeNode $left = null,
public ?TreeNode $right = null
) {}
}

class BinaryTree
{
public ?TreeNode $root = null;

public function insert(int $value): void
{
$this->root = $this->insertRecursive($this->root, $value);
}

private function insertRecursive(?TreeNode $node, int $value): TreeNode
{
if ($node === null) return new TreeNode($value);
if ($value < $node->data) $node->left = $this->insertRecursive($node->left, $value);
else $node->right = $this->insertRecursive($node->right, $value);
return $node;
}

// 前序
public function preorder(?TreeNode $node = null): array
{
if ($node === null) $node = $this->root;
if ($node === null) return [];
return array_merge([$node->data], $this->preorder($node->left), $this->preorder($node->right));
}

// 中序
public function inorder(?TreeNode $node = null): array
{
if ($node === null) $node = $this->root;
if ($node === null) return [];
return array_merge($this->inorder($node->left), [$node->data], $this->inorder($node->right));
}

// 后序
public function postorder(?TreeNode $node = null): array
{
if ($node === null) $node = $this->root;
if ($node === null) return [];
return array_merge($this->postorder($node->left), $this->postorder($node->right), [$node->data]);
}

// 层序
public function levelOrder(): array
{
if ($this->root === null) return [];
$result = [];
$queue = [$this->root];
while (!empty($queue)) {
$node = array_shift($queue);
$result[] = $node->data;
if ($node->left) $queue[] = $node->left;
if ($node->right) $queue[] = $node->right;
}
return $result;
}

public function search(int $value): bool
{
$current = $this->root;
while ($current !== null) {
if ($value === $current->data) return true;
if ($value < $current->data) $current = $current->left;
else $current = $current->right;
}
return false;
}
}

$tree = new BinaryTree();
foreach ([5, 3, 7, 2, 4, 6, 8] as $v) $tree->insert($v);

echo "前序: " . implode(', ', $tree->preorder()) . "\n";
echo "中序: " . implode(', ', $tree->inorder()) . "\n";
echo "后序: " . implode(', ', $tree->postorder()) . "\n";
echo "层序: " . implode(', ', $tree->levelOrder()) . "\n";
echo "查找4: " . ($tree->search(4) ? '找到' : '未找到') . "\n";
?>
>

N叉树每个节点可以有多个子节点。

```php
class NaryTreeNode
{
public function __construct(
public mixed $data,
public array $children = []
) {}

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

class Tree
{
public ?NaryTreeNode $root = null;

public function dfs(?NaryTreeNode $node = null, int $depth = 0): array
{
if ($node === null) $node = $this->root;
if ($node === null) return [];
$result = [['data' => $node->data, 'depth' => $depth]];
foreach ($node->children as $child) {
$result = array_merge($result, $this->dfs($child, $depth + 1));
}
return $result;
}
}
?>

分类树的扁平化和还原。

```php
class CategoryTree
{
public static function fromFlat(array $items, int $parentId = 0): array
{
$tree = [];
foreach ($items as $item) {
if ($item['parent_id'] === $parentId) {
$children = self::fromFlat($items, $item['id']);
$node = ['id' => $item['id'], 'name' => $item['name']];
if (!empty($children)) $node['children'] = $children;
$tree[] = $node;
}
}
return $tree;
}

public static function toFlat(array $tree, int $parentId = 0): array
{
$items = [];
foreach ($tree as $node) {
$items[] = ['id' => $node['id'], 'name' => $node['name'], 'parent_id' => $parentId];
if (!empty($node['children'])) {
$items = array_merge($items, self::toFlat($node['children'], $node['id']));
}
}
return $items;
}
}
?>

树结构在PHP中很常用。文件系统、组织架构、评论回复、菜单导航都可以用树来表示。理解树的遍历和操作在处理层次结构数据时很有帮助。递归是处理树的核心方法。