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