PHP 二叉树递归遍历无限循环问题
PHP Binary Tree Recursive Traversal Infinite Loop Issue
我有一个二叉树和节点class,可以创建节点,然后递归遍历根节点以获得前序、post 和中序节点顺序。这段代码在 JS 中有效,但由于某种原因无限循环并出现“不能在非对象上下文中使用‘$this’”的警告。在 addSide()
函数中返回 $this 时。是什么导致了这个无限循环,我该如何解决?
<?php
class Node {
public $value;
public $right = null;
public $left = null;
function __constructor($value) {
$this->value = $value;
}
}
class BinaryTree {
public $root;
function __constructor() {}
function create($value) {
$newNode = new Node($value);
if (!$this->root) {
$this->root = $newNode;
return $this; //no warning
}
$current = $this->root;
function addSide($side, $current, $newNode) {
if (!$current->$side) {
$current->$side = $newNode;
return $this; //Warning: "Cannot use '$this' in non-object context."
}
$current = $current->$side;
};
while (true) {
if ($value === $current->value) return $this;
if ($value < $current->value) addSide("left", $current, $newNode);
else addSide("right", $current, $newNode);
}
}
function preOrder() {
$visited = [];
$current = $this->root;
function traversePreOrder($node) {
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;
function traversePostOrder($node) {
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;
function traverseInOrder($node) {
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: ". $tree->inOrder());
echo("preOrder: ". $tree->preOrder());
echo("postOrder: ". $tree->postOrder());
由于您似乎没有 PHP 背景,因此需要注意以下几点:
它是 __construct()
而不是 __constructor()
。这成为值比较期间代码中的一个主要问题。
无需在函数内部创建函数。当一个方法被调用两次时,这可能会导致 cannot redeclare function 问题。
当从 class 中的另一个方法调用方法时,$this->
是必需的,除非被调用的函数是 PHP 中的内置函数或至少在代码执行期间可用。
您似乎正在创建 二叉搜索树 而不仅仅是 二叉树.
在遍历过程中收集值时通过引用传递$visited
。
您不能使用echo
打印数组。使用 print_r()
或使用 implode()
使用定界符(比如 ,
)将数组转换为字符串,然后使用 echo.
打印它
在create()
中,你有时return一个节点,有时$this
。两者不一样。前者是 Node
class 的对象,后者是 BinaryTree
class.
的对象
在create()
方法中,只需要根据给定的值从当前代码开始向左或向右遍历即可,使用简单的while循环即可实现。
更正后的代码:
<?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;
我有一个二叉树和节点class,可以创建节点,然后递归遍历根节点以获得前序、post 和中序节点顺序。这段代码在 JS 中有效,但由于某种原因无限循环并出现“不能在非对象上下文中使用‘$this’”的警告。在 addSide()
函数中返回 $this 时。是什么导致了这个无限循环,我该如何解决?
<?php
class Node {
public $value;
public $right = null;
public $left = null;
function __constructor($value) {
$this->value = $value;
}
}
class BinaryTree {
public $root;
function __constructor() {}
function create($value) {
$newNode = new Node($value);
if (!$this->root) {
$this->root = $newNode;
return $this; //no warning
}
$current = $this->root;
function addSide($side, $current, $newNode) {
if (!$current->$side) {
$current->$side = $newNode;
return $this; //Warning: "Cannot use '$this' in non-object context."
}
$current = $current->$side;
};
while (true) {
if ($value === $current->value) return $this;
if ($value < $current->value) addSide("left", $current, $newNode);
else addSide("right", $current, $newNode);
}
}
function preOrder() {
$visited = [];
$current = $this->root;
function traversePreOrder($node) {
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;
function traversePostOrder($node) {
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;
function traverseInOrder($node) {
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: ". $tree->inOrder());
echo("preOrder: ". $tree->preOrder());
echo("postOrder: ". $tree->postOrder());
由于您似乎没有 PHP 背景,因此需要注意以下几点:
它是
__construct()
而不是__constructor()
。这成为值比较期间代码中的一个主要问题。无需在函数内部创建函数。当一个方法被调用两次时,这可能会导致 cannot redeclare function 问题。
当从 class 中的另一个方法调用方法时,
$this->
是必需的,除非被调用的函数是 PHP 中的内置函数或至少在代码执行期间可用。您似乎正在创建 二叉搜索树 而不仅仅是 二叉树.
在遍历过程中收集值时通过引用传递
$visited
。您不能使用
打印它echo
打印数组。使用print_r()
或使用implode()
使用定界符(比如,
)将数组转换为字符串,然后使用 echo.在
的对象create()
中,你有时return一个节点,有时$this
。两者不一样。前者是Node
class 的对象,后者是BinaryTree
class.在
create()
方法中,只需要根据给定的值从当前代码开始向左或向右遍历即可,使用简单的while循环即可实现。
更正后的代码:
<?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;