<?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()); 
?>

<?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;