deleteNode('30');(非平衡树可删除,平衡树的没写删除操作) print_r($tree->getTree()); ?>
bstOrder.php
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; } } ?>
![大前端线上培训班](http://m.sbmmt.com/img/upload/article/000/000/001/6176124da5ca5514.png)
相关文章推荐
• 怎样使用PHP中的spl_autoload_register() 和 __autoload() 函数?• 你必须了解PHP中什么是抽象类和抽象方法• PHP中怎样去判断对象是否属于一个类?• 五分钟带你看PHP中的接口interface声明与应用(实例详解)• PHP中怎样完成Cookie的创建、读取和删除?jquery 基础视频教程
jQuery 很容易学习,希望通过我们的《jquery 基础视频教程》可以帮助大家来更好的学习jQuery。 jQuery 是一个 JavaScript 库,简化了 JavaScript 编程。
jQuery教程45064次播放
javascript三级联动视频教程
《javascript三级联动视频教程》介绍了javascript开发的三级联动功能,该功能在日常使用中还是经常能用的到的一个。
JavaScript教程26409次播放
独孤九贱(3)_JavaScript视频教程
javascript是运行在浏览器上的脚本语言,连续多年,被评为全球最受欢迎的编程语言。是前端开发必备三大法器中,最具杀伤力。如果前端开发是降龙十八掌,好么javascript就是第18掌:亢龙有悔。没有它,你的前端生涯是不完整的。《php.cn独孤九贱(3)-JavaScript视频教程》课程特色:php中文网原创幽默段子系列课程,以恶搞,段子为主题风格的php视频教程!轻松的教学风格,简短的教学模式,让同学们在不知不觉中,学会了javascript知识。
JavaScript教程112770次播放
独孤九贱(6)_jQuery视频教程
jQuery是一个快速、简洁的JavaScript框架。设计的宗旨是“write Less,Do More”,即倡导写更少的代码,做更多的事情。它封装JavaScript常用的功能代码,提供一种简便的JavaScript设计模式,优化HTML文档操作、事件处理、动画设计和Ajax交互。 核心特性可以总结为:具有独特的链式语法和短小清晰的多功能接口;具有高效灵活的css选择器,并且可对CSS选择器进行扩展;拥有便捷的插件扩展机制和丰富的插件。兼容各种主流浏览器,如IE 6.0+、FF 1.5+、Safari 2.0+、Opera 9.0+等,是全球最流行的前端开发框架之一。PHP中文网根据最新版本,独家录制jQuery最新视频教程,回馈PHP中文网的新老用户。
jQuery教程92496次播放