PHP树结构实现与遍历算法

PHP树结构实现与遍历算法树是编程中常用的数据结构。分类、组织架构、评论回复都可以用树来表示。今天说说PHP中树结构的实现。二叉树是最基本的树结构。phpclass 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叉树每个节点可以有多个子节点。phpclass 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;}}?分类树的扁平化和还原。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): 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中很常用。文件系统、组织架构、评论回复、菜单导航都可以用树来表示。理解树的遍历和操作在处理层次结构数据时很有帮助。递归是处理树的核心方法。