- 浏览: 134899 次
- 性别:
- 来自: 北京
文章分类
最新评论
<?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() < $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; } } ?>
发表评论
文章已被作者锁定,不允许评论。
-
c实现bitmap
2013-05-14 14:34 1314直接上代码. #include <stdio.h> ... -
nginx hash源码分析
2013-02-05 19:05 1192HASH是NGINX核心数据结构之一.见几个链接.分析的很详细 ... -
贪心算法与动态规划的区别
2012-11-24 21:07 31441.贪心算法和动态规划区别 贪心算法是自顶向下的,它会先做在 ... -
PHP实现各种排序
2011-11-23 17:32 901<?php /** * 各种排序 * @aut ... -
PHP实现克鲁斯卡尔(kruscal)算法
2011-11-05 21:18 1150<?php require 'edge.php ... -
PHP实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法
2011-11-02 18:35 4610<?php require 'mGraph.p ... -
php实现图的邻接表,关键路径,拓朴排序
2011-11-02 18:30 1800<?php //调用 require ... -
PHP实现二叉树,线索二叉树
2011-10-26 19:56 6282<?php require 'biTree ... -
php 实现KMP算法
2011-10-23 12:32 1818<?php /** * KMP算法的P ... -
php实现单链表(静态链表)
2011-10-21 14:40 1788<?php /* * 单链表的PH ...
相关推荐
java数据结构与算法之平衡二叉树AVL树的设计与实现分析.doc
首先实现BST二叉搜索树,在BST的基础上做出AVL树,有插入、删除、查询、调整平衡的功能,而且可以和BST比较的过程。By Michael Zhou
排序二叉树 AVL树 哈夫曼树增删改查Java实现
主要介绍了C语言数据结构之平衡二叉树(AVL树)实现方法,结合实例形式分析了C语言平衡二叉树的相关定义与使用技巧,需要的朋友可以参考下
关于平衡二叉树的学习笔记,并提供二叉树平衡、插入及删除的代码、提供一个简单的打印二叉树结构的函数(打印对齐不是很好),方便代码调试。
平衡二叉树(AVL树).docx
C++实现类模板 包括二叉树、搜索二叉树、AVL树及它们的各种算法实现(包括建立、输出、前序遍历、中序遍历、后序遍历、插入、删除、搜索、重构、求树高、统计叶子总数等等)
平衡二叉树的实现 建立 搜索 插入 删除 遍历 希望对你有所帮助
平衡二叉树(Balanced Binary Tree)又被称为AVL树。具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。构造与调整方法。 实验目的: 二叉排序树的实现...
二叉树的应用:二叉排序树BST和平衡二叉树AVL的构造实验报告
一棵AVL树或者是空树,或者是具有下列性质的二叉搜索树:它的左子树和右子树都是AVL树,且左子树和右子树的高度之差的绝对值不超过1。
AVL管理数据 struct branch{ unsigned int data; /* actual data */ struct branch * l_chld, * r_chld; /* left & right child */ short bc; /* balance coefficient */ }; #define avl_entry (T, P, M) (T *)...
NULL 博文链接:https://709002341.iteye.com/blog/2258678
这是一个用C实现的AVL tree,带MFC的测试程序。 在我的机器上(P4 T2050 Duo, 1G memory)列C盘所有文件并组织成AVL tree,一共是70000多个文件和目录,耗时大约是5-7秒
自己写的AVL树模板源代码,包括插入,删除等操作.
平衡二叉树插入节点和删除节点
java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析.docx
java数据结构与算法之平衡二叉树(AVL树)的设计与实现分析.pdf