先序遍历(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;
    }
    $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;
}
function inorderTraversal($root) {
    $result = [];
    $stack = [];
    $current = $root;
    while ($current !== null || !empty($stack)) {
        while ($current !== null) {
            array_push($stack, $current);
            $current = $current->left;
        }
        $current = array_pop($stack);
        $result[] = $current->val;
        $current = $current->right;
    }
    return $result;
}
function postorderTraversal($root) {
    if ($root === null) {
        return [];
    }
    $stack1 = [$root];
    $stack2 = [];
    while (!empty($stack1)) {
        $node = array_pop($stack1);
        array_push($stack2, $node);
        if ($node->left !== null) {
            array_push($stack1, $node->left);
        }
        if ($node->right !== null) {
            array_push($stack1, $node->right);
        }
    }
    $result = [];
    while (!empty($stack2)) {
        $node = array_pop($stack2);
        $result[] = $node->val;
    }
    return $result;
}
// 创建一个简单的二叉树
$root = new TreeNode(1);
$root->right = new TreeNode(2);
$root->right->left = new TreeNode(3);

// 先序遍历
echo "先序遍历结果: ";
print_r(preorderTraversal($root));

// 中序遍历
echo "中序遍历结果: ";
print_r(inorderTraversal($root));

// 后序遍历
echo "后序遍历结果: ";
print_r(postorderTraversal($root));