PHP实现平衡二叉树(AVL树)_PHP_编程开发_程序员俱乐部

<?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');(非平衡树可删除,平衡树的没写caozuo.html" target="_blank">删除操作)
    print_r($tree->getTree()); 
?>

<?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);
                            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 < $node->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;
        }
    }
?>