php二叉查找树的使用

Z时代
2024-01-10
分类：综合

美女程序员鼓励师

本文操作系统：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);
}
}
}
?>