本文操作系统: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免费测试