在 PHP 中,可以使用递归或迭代方法来遍历二叉树节点。这里,我们将介绍两种方法:前序遍历、中序遍历和后序遍历。
首先,定义一个简单的二叉树节点类:
class TreeNode {
public $value;
public $left;
public $right;
public function __construct($value) {
$this->value = https://www.yisu.com/ask/$value;>left = null;
$this->right = null;
}
}
递归遍历
- 前序遍历(根->左->右)
function preOrderTraversal($node) {
if ($node === null) {
return;
}
echo $node->value . " ";
preOrderTraversal($node->left);
preOrderTraversal($node->right);
}
- 中序遍历(左->根->右)
function inOrderTraversal($node) {
if ($node === null) {
return;
}
inOrderTraversal($node->left);
echo $node->value . " ";
inOrderTraversal($node->right);
}
- 后序遍历(左->右->根)
function postOrderTraversal($node) {
if ($node === null) {
return;
}
postOrderTraversal($node->left);
postOrderTraversal($node->right);
echo $node->value . " ";
}
迭代遍历
- 前序遍历(根->左->右)
function preOrderTraversalIterative($node) {
if ($node === null) {
return;
}
$stack = [$node];
while ($stack) {
$current = $stack[count($stack) - 1];
$stack = array_slice($stack, 0, -1);
echo $current->value . " ";
if ($current->right !== null) {
$stack[] = $current->right;
}
if ($current->left !== null) {
$stack[] = $current->left;
}
}
}
- 中序遍历(左->根->右)
function inOrderTraversalIterative($node) {
if ($node === null) {
return;
}
$stack = [];
$current = $node;
while ($current !== null || count($stack) > 0) {
while ($current !== null) {
$stack[] = $current;
$current = $current->left;
}
$current = array_pop($stack);
echo $current->value . " ";
$current = $current->right;
}
}
- 后序遍历(左->右->根)
function postOrderTraversalIterative($node) {
if ($node === null) {
return;
}
$stack = [];
$lastVisitedNode = null;
$current = $node;
while ($current !== null || count($stack) > 0) {
if ($current !== null) {
$stack[] = $current;
$current = $current->left;
} else {
$topNode = array_pop($stack);
if ($topNode->right !== null && $lastVisitedNode !== $topNode->right) {
$current = $topNode->right;
} else {
echo $topNode->value . " ";
$lastVisitedNode = $topNode;
}
}
}
}
使用这些遍历函数,可以方便地遍历二叉树的节点。