PHPツリーツリーツリーツリー並べ替えツリー実現
16134 ワード
<?php
/**
* PHP
* @author : xiaojiang 2014-01-01
* */
class Tree {
protected $k = null;
protected $left = null;
protected $right = null;
public function __construct( $k= null , $left = null, $right = null){
$this->k = $k;
$this->left = $left;
$this->right = $right;
}
public function isEmpty(){
return !isset($this->k);
}
public function getKey(){
return isset($this->k) ? $this->k : false;
}
public function setKey($k){
if(!$this->isEmpty())
return ;
$this->k = $k;
$this->left = new Tree();
$this->right = new Tree();
return true;
}
public function deleteKey(){
if(!$this->isLeaf())
return false;
$ret = $this->k;
$this->k = null;
$this->left = null;
$this->right = null;
return $ret;
}
public function setLeftKey( Tree $obj){
if( $this->left || !$this->left->isEmpty())
return false;
$this->left = $obj;
}
public function delLeftKey(){
if($this->isEmpty())
return;
$ret = $this->left ;
$this->left = new Tree();
return $ret;
}
public function setRightKey( Tree $obj){
if( $this->left || !$this->left->isEmpty())
return false;
$this->left = $obj;
}
public function delRightKey(){
if($this->isEmpty())
return;
$ret = $this->left ;
$this->left = new Tree();
return $ret;
}
}
/**
*
* @author: xiaojiang
* */
class bTree extends Tree{
static public function initbTree($array){
$root = new bTree();
foreach($array as $val){
$root->insert($val);
}
return $root;
}
public function compare($obj){
return $this->k - $obj;
}
public function contain($obj){
if ($this->isEmpty())
return false;
$diff = $this->compare($obj);
if($diff == 0){
return true;
}else if($diff > 0){
return $this->right->contain($obj);
}else {
return $this->left->contain($obj);
}
}
public function insert($obj){
if($this->isEmpty()){
$this->setKey($obj);
}else{
$diff = $this->compare($obj);
if($diff > 0){
$this->left->insert($obj);
}else{
$this->right->insert($obj);
}
}
$this->_afterInsert();
}
public function findMax(){
if($this->isEmpty())
return;
if(!$this->right->isEmpty())
return $this->right->findMax();
else
return $this->k;
}
public function findMin(){
if($this->isEmpty())
return ;
if(!$this->left->isEmpty())
return $this->left->findMin();
else
return $this->k;
}
public function setKey($k){
if(!$this->isEmpty())
return ;
$this->k = $k;
$this->left = new bTree();
$this->right = new bTree();
return true;
}
protected function _afterInsert(){}
}
$arr = array(1,5,4,5,10);
$btree = bTree::initbTree($arr);
echo $btree->findMax(); // 10
echo "<br>";
echo $btree->findMin(); // 1マルチ数値ソートに最適です.ロットサイクルの重複判断を回避・・・