php二叉查找树的使用

744次阅读
没有评论

php二叉查找树的使用

本文操作系统:windows7系统、PHP5.6版本、DELL G3电脑。

1.概念

二叉查找树,也称二叉搜索树、有序二叉树,排序二叉树,是指一棵空树或者具有下列性质的二叉树:

1)所有子树上面的左节点的值都比根结点要小,右节点的值都比根结点要大

2)任意结点的左右子树也都是二叉查找树

3)通过中序遍历,将得到的是一个有序的数列

2.特性

若左子树不为空,则左子树上所有结点的值均小于它的根结点的值;

若右子树不为空,则右子树上所有结点的值均大于或等于它的根结点的值;

它的左、右子树也分别为二叉查找树。

3.实例

<?php
class Node{
private $num;//学生学号
private $name;//学生姓名
private $scoreChinese;//学生语文成绩
private $scoreMath;//数学成绩
private $scoreEnglish;//英语成绩
private $left;
private $right;
public function __construct(){
$this->left  = null;
$this->right = null;
}
public function __set($key,$value){
$this->$key = $value;
}
public function __get($key){
if(isset($this->$key)){
return $this->$key;
}
}
}
class Tree{
private $top;//树顶节点
public function __construct($array){
//生成树
$falses = $this->makeTree($array);
$this->readTree();
}
public function makeTree($array){
if(empty($array)){
$this->top = null;
return;
}
//选择树顶节点
$temp = $array[floor(count($array)/2)];
$this->top->num   = $temp['num'];
$this->top->name   = $temp['name'];
$this->top->scoreChinese = $temp['scoreChinese'];
$this->top->scoreMath  = $temp['scoreMath'];
$this->top->scoreEnglish = $temp['scoreEnglish'];
$this->top->left   = null;
$this->top->right   = null;
unset($array[floor(count($array)/2)]);
$false  = 0;//建树失败的节点
foreach($array as $value){
if(false == $this->insert($value)){
$false++;
}
}
}
/**
插入节点
*/
public function insert($info){
$aNode = new Node();
$aNode->num      = $info['num'];
$aNode->name   = $info['name'];
$aNode->scoreChinese = $info['scoreChinese'];
$aNode->scoreMath    = $info['scoreMath'];
$aNode->scoreEnglish = $info['scoreEnglish'];
$aNode->left   = null;
$aNode->right   = null;
if(null == $this->top){
$this->top = $aNode;
return;
}
$nowNode = $this->top;
while(true){
if($nowNode->num == $aNode->num){
return false;
}elseif($nowNode->num>$aNode->num && null == $nowNode->left){
$nowNode->left = $aNode;
return true;
}elseif($nowNode->num<$aNode->num && null == $nowNode->right){
$nowNode->right = $aNode;
return true;
}elseif($nowNode->num>$aNode->num && $nowNode->left != null){
$nowNode = $nowNode->left;
}elseif($nowNode->num<$aNode->num && $nowNode->right != null){
$nowNode = $nowNode->right;
}
}
}
/**
查询节点
*/
public function search($num){
$nowNode = $this->top;
while(true){
if($nowNode->num == $num){
return $nowNode;
}elseif($nowNode->num>$num && null == $nowNode->left){
return null;
}elseif($nowNode->num<$num && null == $nowNode->right){
return null;
}elseif($nowNode->num>$num && $nowNode->left!=null){
$nowNode = $nowNode->left;
}elseif($nowNode->num<$num && $nowNode->right!=null){
$nowNode = $nowNode->right;
}
}
}
/**
树是否为空
*/
public function isEmpty(){
if(is_null($this->top)){
return true;
}else{
return false;
}
}
/**
中序便利树
*/
public function readTree(){
$result = array();
$this->read($this->top,$result);
return $result;
}
private function read($nowNode,&$result){
if(null != $nowNode->left){
$this->read($nowNode->left,$result);
}
array_push($result,$nowNode);
if(null != $nowNode->right){
$this->read($nowNode->right,$result);
}
}
}
?>

以上就是php二叉查找树的使用,相信大家对这种名称有些新奇的算法比较感兴趣。在学会了相关的用法后,赶快动手尝试下它的使用吧。更多php学习指路:php数组

神龙|纯净稳定代理IP免费测试>>>>>>>>天启|企业级代理IP免费测试>>>>>>>>IPIPGO|全球住宅代理IP免费测试

相关文章:

版权声明:程序人生2022-12-08发表,共计3051字。
新手QQ群:570568346,欢迎进群讨论 Python51学习