所以我一直在做我的研究，我正在尝试在PHP中制作BST函数。我遇到了几个问题，实际上只是一个。插入重复值时，它将出错并且程序崩溃。我不确定为什么会发生这种情况。我已经在下面插入了类文件。
<?php
class Node{
public $value;
public $leftChild;
public $rightChild;
public function __construct($item){
$this->value = $item;
//new nodes are blank
$this->leftChild = null;
$this->rightChild = null;
}
public function inOrder(){
if($this->leftChild !== null){
$this->leftChild->inOrder();
}
print $this->value."</br>";
if($this->rightChild !== null){
$this->rightChild->inOrder();
}
}
public function preOrder(){
print $this->value."</br>";
if($this->leftChild !== null){
$this->leftChild->preOrder();
}
if($this->rightChild !== null){
$this->rightChild->preOrder();
}
}
public function postOrder(){
if($this->leftChild !== null){
$this->leftChild->postOrder();
}
if($this->rightChild !== null){
$this->rightChild->postOrder();
}
print $this->value."</br>";
}
}
class BinaryTree{
protected $root; //the root node of the tree
public function __construct(){
$this->root = null;
}
public function isEmpty(){
return $this->root === null;
}
public function insert($item){
//check if the tree is empty or if the current node is empty
if($this->isEmpty()){
//special case if tree is empty
$this->root = new Node($item);
}else{
//get the first node in the tree and begin the walk through
$current = $this->root;
while($current != null){
if($item < $current->value){
if($current->leftChild !== null){
$current = $current->leftChild;
}else{
$current->leftChild = new Node($item);
$current = $current->leftChild;
}
}elseif($item >= $current->value){
if($current->rightChild !== null){
$current = $current->rightChild;
}else{
$current->rightChild = new Node($item);
$current = $current->rightChild;
}
}else{
return;
}
//insert the node somewhere in the tree starting at the root
}
}
}
public function inOrderTraversal(){
//dump the tree rooted at "root"
$this->root->inOrder();
}
public function preOrderTraversal(){
//dump the tree rooted at "root"
$this->root->preOrder();
}
public function postOrderTraversal(){
$this->root->postOrder();
}
}
?>
这是我用来显示结果的一小段代码
<?php
error_reporting(E_ALL);
require_once "assets/class/tree.class.php";
?>
<!DOCTYPE html>
<html>
<head>
<title></title>
</head>
<body>
<?
$array = array(1, 3, 2, 3, 4, 3, 2);
$tree = new BinaryTree();
for($i = 0; $i < count($array); $i++){
$tree->insert($array[$i]);
}
print_r($tree->inOrderTraversal());
?>
</body>
</html>
当通过我的错误日志进行更多研究时，我发现：
PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 16 bytes) on line 77
我找出了我的错误。发生的事情是，一旦找到值，我就不允许循环中断。从而创建一个无限循环。通过添加中断，我已经解决了这个错误。
while($current != null){
if($item < $current->value){
if($current->leftChild !== null){
$current = $current->leftChild;
}else{
$current->leftChild = new Node($item);
$current = $current->leftChild;
break;
}
}elseif($item >= $current->value){
if($current->rightChild !== null){
$current = $current->rightChild;
}else{
$current->rightChild = new Node($item);
$current = $current->rightChild;
break;
}
}else{
return;
}
//insert the node somewhere in the tree starting at the root
}