PHP 二叉树递归遍历中的无限循环问题排查与修复

本文旨在解决 PHP 中二叉树递归遍历时出现的无限循环问题，并提供修复方案。通过分析问题代码，指出 __constructor 拼写错误、内部函数使用不当、缺少 $this 引用等常见错误，并提供修正后的代码示例，帮助开发者避免类似问题，实现正确的二叉树遍历。

在 PHP 中实现二叉树的递归遍历，需要注意一些关键点，以避免出现无限循环和其它错误。以下将详细介绍这些注意事项，并提供修正后的代码示例。

常见错误与修复方案

1. 构造函数名称错误： PHP 中类的构造函数应该命名为 __construct()，而不是 __constructor()。这是导致对象属性未正确初始化的一个常见错误。

   class Node {
       public $value;
       public $right = null;
       public $left = null;
   
       function __construct($value) { // Corrected constructor name
           $this->value = $value;
       }
   }

   登录后复制

2. 内部函数使用不当： 在 PHP 中，不建议在函数内部定义函数。这可能导致“Cannot redeclare function”错误，尤其是在多次调用该函数时。

   立即学习“PHP免费学习笔记（深入）”；

   应该将内部函数移到类级别，并使用 $this-> 引用来调用它们。

   

   无涯·问知

   无涯·问知，是一款基于星环大模型底座，结合个人知识库、企业知识库、法律法规、财经等多种知识源的企业级垂直领域问答产品

   40

   查看详情

   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
   }

   登录后复制

3. 缺少 $this 引用： 在类的方法中调用其他方法时，必须使用 $this-> 引用，除非被调用的函数是 PHP 内置函数或在代码执行期间可用。

   class BinaryTree {
       // ...
   
       function preOrder() {
           $visited = [];
           $current = $this->root;
           $this->traversePreOrder($current, $visited); // Correctly using $this->
           return $visited;
       }
   }

   登录后复制

4. 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;
   }

   登录后复制

5. 遍历时未按引用传递 $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);
   }

   登录后复制

6. 输出数组的方式： echo 不能直接输出数组。应该使用 print_r() 函数或 implode() 函数将数组转换为字符串。

   echo "inOrder: ". implode(",",$tree->inOrder()),PHP_EOL; // Using implode to convert array to string

   登录后复制

完整修正后的代码示例

<?php

class Node {
    public $value;
    public $right = null;
    public $left = null;

    function __construct($value) {
        $this->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 引用、确保遍历数组按引用传递，以及使用合适的函数输出数组。遵循这些建议，可以有效地避免无限循环和其他常见错误，编写出健壮且高效的二叉树遍历代码。

以上就是PHP 二叉树递归遍历中的无限循环问题排查与修复的详细内容，更多请关注php中文网其它相关文章！