• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

平衡二叉树:php实现平衡二叉树(avl树)_php

php 搞代码 3年前 (2018-06-21) 90次浏览 已收录 0个评论

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

http://www.gaodaima.com/?p=50152平衡二叉树:php实现平衡二叉树(avl树)_php

//$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

欢迎大家阅读《平衡二叉树:php实现平衡二叉树(avl树)_php》,跪求各位点评,若觉得好的话请收藏本文,by 搞代码


喜欢 (0)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址