PHP实现平衡二叉树(AVL树)
<?php require 'bstOrder.php';
$test = range(1, 10);
//$test = array(3,9,1,4,8,5,7,6,2,10);
$tree = new Bst($test, true);
//$tree->deleteNode('30');(非平衡树可删除,平衡树的没写删除操作)
print_r($tree->getTree());
?>
bstOrder.php
<?php /**
* PHP实现二叉排序树
* @author zhaojiangwei
* @since 2011/11/16 16:29
*
*/
class Node{
private $data;
private $left;
private $right;
private $bf;//平衡度
public function Node($data = NULL, $bf = 0, $left = NULL, $right = NULL){
$this->data = $data;
$this->left = $left;
$this->right = $right;
$this->bf = $bf;
}
public function getBf(){
return $this->bf;
}
public function setBf($bf){
$this->bf = $bf;
}
public function getData(){
return $this->data;
}
public function setData($data){
$this->data = $data;
}
public function &getLeft(){
return $this->left;
}
public function &getRight(){
return $this->right;
}
public function setLeft($left){
$this->left = $left;
}
public function setRight($right){
$this->right = $right;
}
}
class Bst{
private $head;//头结点
private $data;//初始输入的数据,为数组形式,如array('a','b');
private $tag;//查找时设置的前一结点(已无效,没用)
//$bst:是否创建AVL树
public function Bst($data, $bst = FALSE){
$this->data = $data;
$this->head = NULL;
if(!$bst){
$this->createBst();
}else{
$this->createBfBst();
}
}
public function createBfBst(){
foreach($this->data as $value){
$this->insertBfNode($this->head, $value);
}
}
private function insertBfNode(&$node, $value){
if($node == NULL){
$node = new Node($value, 0);
return TRUE;
}else{
if($node->getData() > $value){
if(!$this->insertBfNode($node->getLeft(), $value)){
return FALSE;
}
switch($node->getBf()){
case 0:
$node->setBf(1);
return TRUE;
case 1:
$this->rightRotate($node);
return FALSE;
case -1:
$node->setBf(0);
return FALSE;
}
}elseif($node->getData() insertBfNode($node->getRight(), $value)){
return FALSE;
}
switch($node->getBf()){
case 0:
$node->setBf(-1);
return TRUE;
case 1:
$node->setBf(0);
return FALSE;
case -1:
$this->leftRotate($node);
return FALSE;
}
}else{
return FAlse;
}
}
}
private function excuteLeft(&$node){
$temp = $node;
$node = $node->getRight();
$temp->setRight($node->getLeft());
$node->setLeft($temp);
}
private function excuteRight(&$node){
$temp = $node;
$node = $node->getLeft();
$temp->setLeft($node->getRight());
$node->setRight($temp);
}
private function leftRotate(&$node){
$right = &$node->getRight();
switch($right->getBf()){
case 1:
$left = &$right->getLeft();
switch($left->getBf()){
case -1:
$right->setBf(0);
$node->setBf(1);
break;
case 0:
$right->setBf(0);
$node->setBf(0);
break;
case 1:
$right->setBf(-1);
$node->setBf(0);
break;
}
$left->setBf(0);
$this->excuteRight($right);
$this->excuteLeft($node);
break;
case -1:
$node->setBf(0);
$right->setBf(0);
$this->excuteLeft($node);
break;
}
}
private function rightRotate(&$node){
$left = &$node->getLeft();
switch($left->getBf()){
case -1:
$right = &$left->getRight();
switch($right->getBf()){
case -1:
$left->setBf(1);
$node->setBf(0);
break;
case 0:
$left->setBf(0);
$node->setBf(0);
break;
case 1:
$left->setBf(0);
$node->setBf(-1);
break;
}
$right->setBf(0);
$this->excuteLeft($left);
$this->excuteRight($node);
break;
case 1:
$node->setBf(0);
$left->setBf(0);
$this->excuteRight($node);
break;
}
}
public function createBst(){
foreach($this->data as $value){
$this->insertNode($value);
}
}
//$pre:如果找不到该结点,是否返回前值
public function &searchBst(& $node, $key, $pre = FALSE){
if($node == NULL){
if($pre){
return $this->tag;
}else{
return FALSE;
}
}
if($key > $node->getData()){
$this->tag = $node;
return $this->searchBst($node->getRight(), $key, $pre);
}elseif($key getData()){
$this->tag = $node;
return $this->searchBst($node->getLeft(), $key, $pre);
}else{
return $node;
}
}
public function insertNode($key){
if(!$this->head){
$this->head = new Node($key);
}else{
$pre = $this->searchBst($this->head, $key, TRUE);
$node = new Node($key);
if($pre->getData() > $key){
$pre->setLeft($node);
}else{
$pre->setRight($node);
}
}
}
public function deleteNode($key){
$node = &$this->searchBst($this->head, $key);
if(!$node){
return FALSE;
}
if($node->getLeft() == NULL){
$node = $node->getRight();
}elseif($node->getRight() == NULL){
$node = $node->getLeft();
}else{
$leftBig = &$this->searchLeftBig($node);
$node->setData($leftBig->getData());
if($leftBig->getLeft()){
$leftBig = $leftBig->getLeft();
}
}
}
private function &searchLeftBig(& $key){
$result = &$key->getLeft();
while($result){
if($result->getRight() == NULL){
return $result;
}
$result = &$result->getRight();
}
}
public function getTree(){
return $this->head;
}
}
?>