PHP兑现平衡二叉树(AVL树)

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