PHP二叉树递归遍历死循环与$this非对象上下文报错排查

• $this报错原因：PHP作用域规则和JS存在差异，在类方法内部直接声明的普通函数属于全局作用域，不属于当前类的实例上下文，不会自动继承$this指针，因此在addSide函数内使用$this会抛出非对象上下文的警告。
• 死循环原因：addSide函数内对$current的赋值仅作用于函数局部作用域，无法修改外层while循环中的$current变量，导致循环内的$current永远停留在根节点，每次判断都走相同分支，始终无法退出循环。
• 额外隐藏问题：你定义的构造函数名为__constructor，PHP标准构造方法名称为__construct，多写的后缀会导致构造函数不会被自动调用，节点的value属性无法正常初始化。同时三个遍历方法中的内层遍历函数默认无法访问外层的$visited数组，最终遍历结果会为空。

以下是完整修复后的代码：

<?php

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

    // 修正构造函数名
    function __construct($value) {
        $this->value = $value;
    }
}

class BinaryTree {
    public $root;

    // 修正构造函数名
    function __construct() {}

    function create($value) {
        $newNode = new Node($value);
        if (!$this->root) {
            $this->root = $newNode;
            return $this;
        }
        $current = $this->root;
        // 去掉内层addSide函数，逻辑直接写到循环中
        while (true) {
            if ($value === $current->value) return $this;
            if ($value < $current->value) {
                if (!$current->left) {
                    $current->left = $newNode;
                    return $this;
                }
                $current = $current->left;
            } else {
                if (!$current->right) {
                    $current->right = $newNode;
                    return $this;
                }
                $current = $current->right;
            }
        }
    }

    function preOrder() {
        $visited = [];
        $current = $this->root;
        // 改成匿名函数，用use引用$visited和函数自身实现递归
        $traversePreOrder = function($node) use (&$visited, &$traversePreOrder) {
            array_push($visited, $node->value);
            if ($node->left) $traversePreOrder($node->left);
            if ($node->right) $traversePreOrder($node->right);
        };
        $traversePreOrder($current);
        return $visited;
    }

    function postOrder() {
        $visited = [];
        $current = $this->root;
        $traversePostOrder = function($node) use (&$visited, &$traversePostOrder) {
            if ($node->left) $traversePostOrder($node->left);
            if ($node->right) $traversePostOrder($node->right);
            array_push($visited, $node->value);
        };
        $traversePostOrder($current);
        return $visited;
    }

    function inOrder() {
        $visited = [];
        $current = $this->root;
        $traverseInOrder = function($node) use (&$visited, &$traverseInOrder) {
            if ($node->left) $traverseInOrder($node->left);
            array_push($visited, $node->value);
            if ($node->right) $traverseInOrder($node->right);
        };
        $traverseInOrder($current);
        return $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;

修复后运行输出如下：

inOrder: 12,29,30,45,50
preOrder: 50,30,12,29,45
postOrder: 29,12,45,30,50

内容的提问来源于stack exchange，提问作者user14849955