php 递归函数提供三种方法进行二叉树遍历：前序遍历（自顶向下，先根节点后左子树再右子树）；中序遍历（自底向上，先左子树后根节点再右子树）；后序遍历（自底向上，先左子树后右子树再根节点）。
PHP 递归函数如何进行二叉树遍历
前言
二叉树是一种广泛用于数据结构和算法的数据结构。遍历二叉树是访问和处理其所有节点的常见操作。PHP 提供了递归函数来实现不同类型的二叉树遍历，例如：
立即学习“PHP免费学习笔记（深入）”；
前序遍历 (pre-order)
前序遍历以根节点开始，然后先遍历其左子树，再遍历其右子树。
|
1
2
3
4
5
6
7
|
function preOrderTraversal($node) {
if ($node) {
echo $node->data;
preOrderTraversal($node->left);
preOrderTraversal($node->right);
}
}
|
中序遍历 (in-order)
中序遍历先遍历左子树，然后访问根节点，最后遍历右子树。
|
1
2
3
4
5
6
7
|
function inOrderTraversal($node) {
if ($node) {
inOrderTraversal($node->left);
echo $node->data;
inOrderTraversal($node->right);
}
}
|
后序遍历 (post-order)
后序遍历先遍历左子树，然后遍历右子树，最后访问根节点。
|
1
2
3
4
5
6
7
|
function postOrderTraversal($node) {
if ($node) {
postOrderTraversal($node->left);
postOrderTraversal($node->right);
echo $node->data;
}
}
|
实战案例
假设我们有一个二叉树：
我们可以使用这些函数遍历这棵二叉树并打印其节点数据：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Node {
public $data;
public $left;
public $right;
}
$root = new Node();
$root->data = 1;
$root->left = new Node();
$root->left->data = 2;
$root->left->left = new Node();
$root->left->left->data = 4;
$root->left->right = new Node();
$root->left->right->data = 5;
$root->right = new Node();
$root->right->data = 3;
preOrderTraversal($root);
inOrderTraversal($root);
postOrderTraversal($root);
|
登录后复制
