二叉树遍历教程：先序、中序、后序、层序遍历的实现与应用

二叉树

结构

二叉树是一种常见的树状数据结构，其特点是每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以为空树，也可以由一个根节点和分别作为根的左子树和右子树组成，而左右子树本身也必须是二叉树。

二叉树是许多其他数据结构的基础，如二叉排序树和 Huffman 编码等。在机器学习算法中，基于树的学习算法也大量使用二叉树的结构。

遍历方式

层序遍历

从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点

先序遍历（Preorder Traversal）根 – 左 – 右

若二叉树为空，则什么都不做；
若二叉树非空：访问根节点 -> 递归遍历左子树 -> 递归遍历右子树

这种先处理父节点、后处理子节点的特性，使其在需要优先利用根节点信息、自上而下构建 / 遍历结构的场景中极具价值。

应用场景

文件系统目录遍历：遍历目录时，通常先显示父文件夹，再显示其下的子文件夹和文件。
生成 XML 或 JSON 数据
前缀信息生成
创建/复制二叉树：先确定根节点，才能进一步构建左、右子树

中序遍历（Inorder Traversal）左 – 根 – 右

应用场景

二叉搜索树操作：在二叉搜索树中查找第 k 小的元素、判断一棵树是否为二叉搜索树等操作都可以借助中序遍历实现
有序输出：当需要将二叉树的节点按顺序输出时，中序遍历是一个很好的选择

后序遍历（Postorder Traversal）左 – 右 – 根

应用场景

计算文件系统磁盘使用量
内存释放：在释放二叉树的内存时，需要先释放子节点的内存，最后释放根节点的内存，后序遍历正好满足这个需求

代码示例

<?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;
    }
}
// 前序遍历
function preorderTraversal($root, &$result = []) {
    if ($root == null) {
        return;
    }
    $result[] = $root->val;
    preorderTraversal($root->left, $result);
    preorderTraversal($root->right, $result);
    return $result; 
}
// 中序遍历
function inorderTraversal($root, &$result = []) {
    if ($root == null) {
        return;
    }
    inorderTraversal($root->left, $result);
    $result[] = $root->val;
    inorderTraversal($root->right, $result);
    return $result; 
}
// 后序遍历
function postorderTraversal($root, &$result = []) {
    if ($root == null) {
        return;
    }
    inorderTraversal($root->left, $result);
    inorderTraversal($root->right, $result);
    $result[] = $root->val;
    return $result; 
}

// 层序遍历实现
function levelOrderTraversal($root) {
    $result = [];
    if ($root === null) {
        return $result; // 空树直接返回空数组
    }
    
    // 用数组模拟队列（先进先出）
    $queue = [];
    // 根节点入队
    array_push($queue, $root);
    
    // 队列不为空时循环
    while (!empty($queue)) {
        // 当前层的节点数量（控制每层遍历的边界）
        $levelSize = count($queue);
        $currentLevel = []; // 存储当前层的节点值
        
        // 遍历当前层的所有节点
        for ($i = 0; $i < $levelSize; $i++) {
            // 出队一个节点（队首元素）
            $node = array_shift($queue);
            // 记录当前节点值
            $currentLevel[] = $node->val;
            
            // 左子节点入队（如果存在）
            if ($node->left !== null) {
                array_push($queue, $node->left);
            }
            // 右子节点入队（如果存在）
            if ($node->right !== null) {
                array_push($queue, $node->right);
            }
        }
        
        // 将当前层的结果加入总结果
        $result[] = $currentLevel;
    }
    
    return $result;
}

// 初始化二叉树
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);
$root->right->left = new TreeNode(6);
$root->right->right = new TreeNode(7);

echo "前序遍历：";
echo implode(',', preorderTraversal($root));
echo "\n";
echo "中序遍历：";
echo implode(',', inorderTraversal($root));
echo "\n";
echo "后序遍历：";
echo implode(',', postorderTraversal($root));
echo "\n";
echo "层序遍历：";
foreach (levelOrderTraversal($root) as $level) {
    echo implode(',', $level) . ',';
}

输出结果

前序遍历：1,2,4,5,3,6,7
中序遍历：4,2,5,1,6,3,7
后序遍历：4,2,5,6,3,7,1
层序遍历：1,2,3,4,5,6,7,

二叉树遍历教程：先序、中序、后序、层序遍历的实现与应用

二叉树

结构

分类

满二叉树(Full Binary Tree)

完全二叉树(Complete Binary Tree)

平衡二叉树(Balanced Binary Tree / AVL Tree)

二叉搜索/排序树(Binary Search Tree / BST)

哈夫曼树

遍历方式

层序遍历

先序遍历（Preorder Traversal）根 – 左 – 右

中序遍历（Inorder Traversal）左 – 根 – 右

后序遍历（Postorder Traversal）左 – 右 – 根

代码示例