在 PHP 中,可以使用遞歸或迭代方法來遍歷二叉樹節點。這里,我們將介紹兩種方法:前序遍歷、中序遍歷和后序遍歷。
首先,定義一個簡單的二叉樹節點類:
class TreeNode {
public $value;
public $left;
public $right;
public function __construct($value) {
$this->value = $value;
$this->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;
}
}
}
}
使用這些遍歷函數,可以方便地遍歷二叉樹的節點。