PHP二叉树递归遍历：避免无限循环的陷阱-php教程-PHP中文网

PHP二叉树递归遍历：避免无限循环的陷阱

霞舞

发布： 2025-07-31 17:02:10

原创

467人浏览过

php二叉树递归遍历：避免无限循环的陷阱

本文将围绕PHP二叉树递归遍历中可能出现的无限循环问题展开，通过分析常见错误原因，例如构造函数命名错误、内部函数作用域问题以及逻辑判断缺陷，并提供修正后的代码示例，帮助读者构建正确的二叉搜索树，并实现前序、中序和后序遍历。

在PHP中实现二叉树的递归遍历，需要特别注意一些细节，以避免潜在的无限循环和错误。以下将详细分析问题代码，并提供修正后的方案。

问题分析

原代码存在以下几个主要问题：

构造函数命名错误： PHP的构造函数应该命名为__construct()，而不是__constructor()。这个错误会导致对象初始化失败，从而影响后续的逻辑判断。
内部函数作用域问题： 在PHP中，函数内部定义的函数只能在该函数的作用域内使用。在create()函数中定义addSide()函数，会导致在类的方法中无法正确调用，同时在循环中重复定义该函数也会导致错误。此外，内部函数无法访问 $this。
create() 函数逻辑问题： create() 函数中，在找到合适位置插入新节点时，有时返回 $this（BinaryTree 对象），有时返回新创建的 Node 对象，导致类型不一致。此外，插入节点的逻辑存在问题，可能导致无限循环。
遍历函数中缺少 $this 调用： 在 preOrder、postOrder 和 inOrder 函数中，内部定义的 traversePreOrder、traversePostOrder 和 traverseInOrder 函数无法直接调用类的其他方法，需要使用 $this 关键字。
输出数组的方式错误： PHP中不能直接使用 echo 输出数组，需要使用 print_r() 或 implode() 函数。

解决方案

针对以上问题，可以采取以下措施进行修正：

UP简历

基于AI技术的免费在线简历制作工具

128

查看详情

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

修正构造函数命名： 将所有__constructor() 更正为 __construct()。
移除内部函数： 将 addSide() 以及 traversePreOrder、traversePostOrder 和 traverseInOrder 函数从内部函数改为类的方法。
统一返回值类型： 在 create() 函数中，始终返回新创建的 Node 对象。
使用循环简化插入逻辑： 使用 while 循环简化 create() 函数中的插入逻辑，使其更易于理解和维护。
使用 $this 调用类方法： 在遍历函数中，使用 $this 关键字调用 traversePreOrder、traversePostOrder 和 traverseInOrder 方法。
使用 implode() 输出数组： 使用 implode() 函数将数组转换为字符串，并使用逗号分隔。
传递 $visited 数组引用： 为了在递归遍历中正确收集节点值，需要将 $visited 数组通过引用传递给遍历函数。

修正后的代码示例

<?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; //no warning
    }

    $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;

登录后复制