二叉树遍历是指按照特定顺序访问二叉树中的所有节点，常见的遍历方式包括深度优先遍历和广度优先遍历，其中深度优先遍历又分为前序、中序、后序三种类型，下面先介绍PHP中二叉树节点的定义方式。
二叉树节点定义
在PHP中实现二叉树遍历前，首先需要定义二叉树节点的结构，每个节点包含自身的值、左子节点和右子节点，具体定义代码如下：
<?php
/**
* 二叉树节点类
*/
class TreeNode {
public $val; // 节点值
public $left; // 左子节点
public $right; // 右子节点
public function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
?>
深度优先遍历实现
深度优先遍历会优先沿着一条路径走到最深的节点，再回溯访问其他路径，三种遍历的核心区别是访问根节点的时机不同。
前序遍历
前序遍历的顺序是根节点 - 左子树 - 右子树，即先访问当前节点，再递归遍历左子树，最后递归遍历右子树，递归实现代码如下：
<?php
/**
* 前序遍历递归实现
* @param TreeNode|null $root 根节点
* @return array 遍历结果数组
*/
function preorderTraversal($root) {
$result = [];
if ($root === null) {
return $result;
}
// 先访问根节点
$result[] = $root->val;
// 递归遍历左子树
$result = array_merge($result, preorderTraversal($root->left));
// 递归遍历右子树
$result = array_merge($result, preorderTraversal($root->right));
return $result;
}
?>
如果需要用迭代方式实现前序遍历，可以使用栈来模拟递归过程，代码如下：
<?php
/**
* 前序遍历迭代实现
* @param TreeNode|null $root 根节点
* @return array 遍历结果数组
*/
function preorderTraversalIterative($root) {
$result = [];
if ($root === null) {
return $result;
}
$stack = [$root];
while (!empty($stack)) {
$node = array_pop($stack);
// 访问当前节点
$result[] = $node->val;
// 右子节点先入栈，保证左子节点先出栈访问
if ($node->right !== null) {
array_push($stack, $node->right);
}
if ($node->left !== null) {
array_push($stack, $node->left);
}
}
return $result;
}
?>
中序遍历
中序遍历的顺序是左子树 - 根节点 - 右子树，即先递归遍历左子树，再访问当前节点，最后递归遍历右子树，递归实现代码如下：
<?php
/**
* 中序遍历递归实现
* @param TreeNode|null $root 根节点
* @return array 遍历结果数组
*/
function inorderTraversal($root) {
$result = [];
if ($root === null) {
return $result;
}
// 递归遍历左子树
$result = array_merge($result, inorderTraversal($root->left));
// 访问根节点
$result[] = $root->val;
// 递归遍历右子树
$result = array_merge($result, inorderTraversal($root->right));
return $result;
}
?>
后序遍历
后序遍历的顺序是左子树 - 右子树 - 根节点，即先递归遍历左子树，再递归遍历右子树，最后访问当前节点，递归实现代码如下：
<?php
/**
* 后序遍历递归实现
* @param TreeNode|null $root 根节点
* @return array 遍历结果数组
*/
function postorderTraversal($root) {
$result = [];
if ($root === null) {
return $result;
}
// 递归遍历左子树
$result = array_merge($result, postorderTraversal($root->left));
// 递归遍历右子树
$result = array_merge($result, postorderTraversal($root->right));
// 访问根节点
$result[] = $root->val;
return $result;
}
?>
广度优先遍历（层次遍历）实现
层次遍历是按照树的层级从上到下、从左到右依次访问所有节点，实现过程需要使用队列来保存每一层的节点，代码如下：
<?php
/**
* 层次遍历实现
* @param TreeNode|null $root 根节点
* @return array 遍历结果数组
*/
function levelOrderTraversal($root) {
$result = [];
if ($root === null) {
return $result;
}
$queue = [$root];
while (!empty($queue)) {
$node = array_shift($queue);
$result[] = $node->val;
// 左子节点入队
if ($node->left !== null) {
array_push($queue, $node->left);
}
// 右子节点入队
if ($node->right !== null) {
array_push($queue, $node->right);
}
}
return $result;
}
?>
测试示例
我们可以构造一个简单的二叉树来测试上述遍历方法的正确性，测试代码如下：
<?php
// 构造二叉树：根节点1，左子节点2，右子节点3，节点2的左子节点4，节点2的右子节点5
$node4 = new TreeNode(4);
$node5 = new TreeNode(5);
$node2 = new TreeNode(2, $node4, $node5);
$node3 = new TreeNode(3);
$root = new TreeNode(1, $node2, $node3);
echo "前序遍历结果：" . implode(',', preorderTraversal($root)) . PHP_EOL;
echo "中序遍历结果：" . implode(',', inorderTraversal($root)) . PHP_EOL;
echo "后序遍历结果：" . implode(',', postorderTraversal($root)) . PHP_EOL;
echo "层次遍历结果：" . implode(',', levelOrderTraversal($root)) . PHP_EOL;
?>
上述测试代码的输出结果如下：
- 前序遍历结果：1,2,4,5,3
- 中序遍历结果：4,2,5,1,3
- 后序遍历结果：4,5,2,3,1
- 层次遍历结果：1,2,3,4,5
不同遍历方式适用于不同的场景，比如中序遍历二叉搜索树会得到有序的节点序列，层次遍历适合需要按层级处理节点的场景，开发者可以根据实际需求选择合适的遍历方式。