本文旨在解决 PHP 中二叉树递归遍历时出现的无限循环问题，并提供修复方案。通过分析问题代码，指出 __constructor 拼写错误、内部函数使用不当、缺少 $this 引用等常见错误，并提供修正后的代码示例，帮助开发者避免类似问题，实现正确的二叉树遍历。
在 PHP 中实现二叉树的递归遍历，需要注意一些关键点，以避免出现无限循环和其它错误。以下将详细介绍这些注意事项，并提供修正后的代码示例。
常见错误与修复方案
-
构造函数名称错误： PHP 中类的构造函数应该命名为 __construct()，而不是 __constructor()。这是导致对象属性未正确初始化的一个常见错误。
class Node { public $value; public $right = null; public $left = null; function __construct($value) { // Corrected constructor name $this->value = $value; } } -
内部函数使用不当： 在 PHP 中，不建议在函数内部定义函数。这可能导致“Cannot redeclare function”错误，尤其是在多次调用该函数时。
立即学习“PHP免费学习笔记（深入）”；
应该将内部函数移到类级别，并使用 $this-> 引用来调用它们。
class BinaryTree { public $root; function __construct() { $this->root = null; } function create($value) { // ... } function preOrder() { $visited = []; $current = $this->root; $this->traversePreOrder($current, $visited); // Calling traversePreOrder using $this-> return $visited; } function traversePreOrder($node, &$visited) { // Moved to class level array_push($visited, $node->value); if ($node->left !== null) $this->traversePreOrder($node->left, $visited); if ($node->right !== null) $this->traversePreOrder($node->right, $visited); } // ... other traversal functions } -
缺少 $this 引用： 在类的方法中调用其他方法时，必须使用 $this-> 引用，除非被调用的函数是 PHP 内置函数或在代码执行期间可用。
class BinaryTree { // ... function preOrder() { $visited = []; $current = $this->root; $this->traversePreOrder($current, $visited); // Correctly using $this-> return $visited; } } -
create() 方法的逻辑问题： create() 方法中，应该使用循环来找到新节点应该插入的位置。此外，应该检查当前节点的值与要插入的值是否相等，如果相等，则可以抛出一个异常，因为二叉搜索树不允许重复的值。
function create($value) { $newNode = new Node($value); if ($this->root === null) { $this->root = $newNode; return $newNode; } $current = $this->root; while($current !== null){ if($current->value > $value){ if($current->left === null){ $current->left = $newNode; break; }else{ $current = $current->left; } }else if($current->value < $value){ if($current->right === null){ $current->right = $newNode; break; }else{ $current = $current->right; } }else{ throw new \Exception("Node with $value already exists."); } } return $newNode; } -
遍历时未按引用传递 $visited 数组： 在递归遍历函数中，需要将 $visited 数组按引用传递，否则每次递归调用都会创建一个新的 $visited 数组，导致最终结果不正确。
function traversePreOrder($node, &$visited) { // Pass $visited by reference array_push($visited, $node->value); if ($node->left !== null) $this->traversePreOrder($node->left, $visited); if ($node->right !== null) $this->traversePreOrder($node->right, $visited); } -
输出数组的方式： echo 不能直接输出数组。应该使用 print_r() 函数或 implode() 函数将数组转换为字符串。
echo "inOrder: ". implode(",",$tree->inOrder()),PHP_EOL; // Using implode to convert array to string
完整修正后的代码示例
value = $value;
}
}
class BinaryTree {
public $root;
function __construct() {
$this->root = null;
}
function create($value) {
$newNode = new Node($value);
if ($this->root === null) {
$this->root = $newNode;
return $newNode;
}
$current = $this->root;
while($current !== null){
if($current->value > $value){
if($current->left === null){
$current->left = $newNode;
break;
}else{
$current = $current->left;
}
}else if($current->value < $value){
if($current->right === null){
$current->right = $newNode;
break;
}else{
$current = $current->right;
}
}else{
throw new \Exception("Node with $value already exists.");
}
}
return $newNode;
}
function preOrder() {
$visited = [];
$current = $this->root;
$this->traversePreOrder($current, $visited);
return $visited;
}
function traversePreOrder($node, &$visited) {
array_push($visited, $node->value);
if ($node->left !== null) $this->traversePreOrder($node->left, $visited);
if ($node->right !== null) $this->traversePreOrder($node->right, $visited);
}
function postOrder() {
$visited = [];
$current = $this->root;
$this->traversePostOrder($current, $visited);
return $visited;
}
function traversePostOrder($node, &$visited) {
if ($node->left !== null) $this->traversePostOrder($node->left, $visited);
if ($node->right !== null) $this->traversePostOrder($node->right, $visited);
array_push($visited, $node->value);
}
function inOrder() {
$visited = [];
$current = $this->root;
$this->traverseInOrder($current, $visited);
return $visited;
}
function traverseInOrder($node, &$visited) {
if ($node->left != null) $this->traverseInOrder($node->left, $visited);
array_push($visited, $node->value);
if ($node->right !== null) $this->traverseInOrder($node->right, $visited);
}
}
$tree = new BinaryTree();
$tree->create(50);
$tree->create(30);
$tree->create(45);
$tree->create(12);
$tree->create(29);
echo "inOrder: ". implode(",",$tree->inOrder()),PHP_EOL;
echo "preOrder: ". implode(",",$tree->preOrder()),PHP_EOL;
echo "postOrder: ". implode(",",$tree->postOrder()),PHP_EOL;总结
在 PHP 中实现二叉树的递归遍历时，务必注意构造函数的正确命名、避免在函数内部定义函数、正确使用 $this 引用、确保遍历数组按引用传递，以及使用合适的函数输出数组。遵循这些建议，可以有效地避免无限循环和其他常见错误，编写出健壮且高效的二叉树遍历代码。
