PHP树数据结构与遍历算法

PHP树数据结构与遍历算法树是计算机科学中重要的数据结构。在PHP中树结构可以用于表示分类、组织架构、评论回复等。今天说说各种树结构的PHP实现。二叉树是最基本的树结构。每个节点最多有两个子节点。phpclass BinaryTreeNode{public function __construct(public mixed $data,public ?BinaryTreeNode $left null,public ?BinaryTreeNode $right null) {}}class BinaryTree{public ?BinaryTreeNode $root null;public function __construct(?BinaryTreeNode $root null){$this-root $root;}// 前序遍历public function preorder(?BinaryTreeNode $node null): array{$node $node ?? $this-root;if ($node null) return [];return array_merge([$node-data],$this-preorder($node-left),$this-preorder($node-right));}// 中序遍历public function inorder(?BinaryTreeNode $node null): array{$node $node ?? $this-root;if ($node null) return [];return array_merge($this-inorder($node-left),[$node-data],$this-inorder($node-right));}// 后序遍历public function postorder(?BinaryTreeNode $node null): array{$node $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 insertBST(int $value): void{$this-root $this-insertRecursive($this-root, $value);}private function insertRecursive(?BinaryTreeNode $node, int $value): BinaryTreeNode{if ($node null) {return new BinaryTreeNode($value);}if ($value $node-data) {$node-left $this-insertRecursive($node-left, $value);} elseif ($value $node-data) {$node-right $this-insertRecursive($node-right, $value);}return $node;}// 二叉搜索树查找public function searchBST(int $value): ?BinaryTreeNode{$current $this-root;while ($current ! null) {if ($value $current-data) return $current;if ($value $current-data) $current $current-left;else $current $current-right;}return null;}// 树的高度public function height(?BinaryTreeNode $node null): int{$node $node ?? $this-root;if ($node null) return 0;return 1 max($this-height($node-left), $this-height($node-right));}}$tree new BinaryTree();foreach ([5, 3, 7, 2, 4, 6, 8] as $value) {$tree-insertBST($value);}echo 前序: . implode(, , $tree-preorder()) . \n;echo 中序: . implode(, , $tree-inorder()) . \n;echo 后序: . implode(, , $tree-postorder()) . \n;echo 层序: . implode(, , $tree-levelOrder()) . \n;echo 高度: . $tree-height() . \n;$found $tree-searchBST(4);echo 查找4: . ($found ? 找到 : 未找到) . \n;?N叉树多叉树更灵活每个节点可以有多个子节点。phpclass TreeNode{public function __construct(public mixed $data,public array $children []) {}public function addChild(TreeNode $child): void{$this-children[] $child;}}class Tree{public ?TreeNode $root null;public function __construct(?TreeNode $root null){$this-root $root;}public function dfs(?TreeNode $node null, int $depth 0): array{$node $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;}public function bfs(): array{if ($this-root null) return [];$result [];$queue [[$this-root, 0]];while (!empty($queue)) {[$node, $depth] array_shift($queue);$result[] [data $node-data, depth $depth];foreach ($node-children as $child) {$queue[] [$child, $depth 1];}}return $result;}public function toArray(?TreeNode $node null): ?array{$node $node ?? $this-root;if ($node null) return null;return [data $node-data,children array_map(fn($child) $this-toArray($child), $node-children),];}}?分类树的扁平化与还原phpclass 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, int $depth 0): array{$items [];foreach ($tree as $node) {$items[] [id $node[id],name $node[name],parent_id $parentId,depth $depth,];if (!empty($node[children])) {$items array_merge($items, self::toFlat($node[children], $node[id], $depth 1));}}return $items;}public static function getPath(array $tree, int $targetId): array{foreach ($tree as $node) {if ($node[id] $targetId) {return [$node];}if (!empty($node[children])) {$path self::getPath($node[children], $targetId);if (!empty($path)) {return array_merge([$node], $path);}}}return [];}}$flatCategories [[id 1, name 电子产品, parent_id 0],[id 2, name 手机, parent_id 1],[id 3, name 电脑, parent_id 1],[id 4, name 笔记本电脑, parent_id 3],[id 5, name 配件, parent_id 0],[id 6, name 充电器, parent_id 5],];$tree CategoryTree::fromFlat($flatCategories);echo 树形结构:\n;echo json_encode($tree, JSON_PRETTY_PRINT | JSON_UNESCAPED_UNICODE) . \n;$path CategoryTree::getPath($tree, 4);echo 路径: . implode( , array_column($path, name)) . \n;$flat CategoryTree::toFlat($tree);echo 扁平化:\n;foreach ($flat as $item) {echo str_repeat( , $item[depth]) . - {$item[name]}\n;}?树结构在PHP中很常用。文件系统、组织架构、评论回复、菜单导航都可以用树来表示。理解树的遍历和操作在处理层次结构数据时很有帮助。递归是处理树的核心方法但要注意深度过大时的性能问题。