平衡二叉树: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() < $value){
if(!$this->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); 本文链接http://www.cxybl.com/html/wlbc/Php/20120607/28509.html