<?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