先序遍历(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));