二叉树(二)

PHP admin 1268℃ 0评论

前两天忘记了,现在补上!PHP实现二叉树

/**
  * 2014-11-28
  * @author 冷布丁
  *
  */
 
 class binary_tree{
     public $data=null;              // 节点值
     public $leftNode=null;          // 左节点
     public $rightNode=null;         // 又节点
 
    public function __construct($data=null,$leftNode=null,$rightNode=null){
         $this->data=$data;
 
         if($data===null){                       //当改节点为空时,将左右节点赋值为NULL
             $this->leftNode=null;
             $this->rightNode=null;
         }elseif($this->left == null){           //当 该节点有值 ,初始化该子节点
             $this->leftNode = new binary_tree();
             $this->rightNode = new binary_tree();
         }else{                                  //如果左右节点都有值赋值给该节点的子节点赋值
             $this->leftNode=$leftNode;
             $this->rightNode= $rightNode;
         }
     }
     /**
      * 判断该节点是否为空
      * @return boolean
      */
     public function isEmpty(){
         return $this->data ===null;
     }
 
     /**
      * 判断该节点是否为叶子节点
      * @return boolean
      */
     public function isLeaf($pos='left'){
         return !$this->isEmpty() && (($pos == 'left' && $this->leftNode->isEmpty()) || ($pos == 'right' && $this->rightNode->isEmpty()));
     }
 
     /**
      * 获取该节点值
      * @return boolean|string
      */
     public function getData(){
         if($this->isEmpty())return false;
         return $this->data;
     }
 
     /**
      * 添加节点
      * @param node $data
      * @return boolean
      */
     public function addNode($data){
         if(!$this->isEmpty()) return false;
         $this->data=$data;
         $this->leftNode = new binary_tree();
         $this->rightNode = new binary_tree();
     }
 
     /**
      * 判断该数据是否在置顶位置并将其删除
      * @param data $data
      * @param string $ac
      * @return boolean|Ambigous <NULL>
      */
     public function deleteNode($data,$ac='leaf'){
         $findNode=$this->find($data);         
         $currentNode=&$findNode['current'];
 
         if(!is_object($currentNode) || $currentNode->isEmpty()) return false;
 
         switch($ac){
             case 'two':
                 if(!$currentNode->leftNode->isEmpty() && !$currentNode->rightNode->isEmpty()){
                     $this->data=null;
                 }
                 break;
             case 'onlyOne':
 
                 if(($currentNode->leftNode->isEmpty() && !$currentNode->rightNode->isEmpty()) || 
                    (!$currentNode->leftNode->isEmpty() && $currentNode->rightNode->isEmpty())
                 ){
                     $currentNode->data=null;
 
                 }
 
                 return false;                 
                 break;
             case 'leat':
             default:
                 if($currentNode->isLeaf('left') && $currentNode->isLeaf('right')){
                     $currentNode->data=null;
                 }                  
                 return false;
 
         }
 
         return $findNode['current'];
     }
 
     /**
      * 获取左节点
      * @return boolean|Ambigous <NULL, string, binary_tree>
      */
     public function getLeftNode(){
         if($this->leftNode->isEmpty()) return false;
         return $this->leftNode;
     }
 
     /**
      * 获取右节点
      * @return boolean|Ambigous <NULL, string, binary_tree>
      */
     public function getRightNode(){
         if($this->rightNode->isEmpty()) return false;
         return $this->rightNode;
     }
 
   /**
      * 删除左子节点 并 返回左节点的值
      * @return boolean|Ambigous <NULL, binary_tree, string>
      */
     public function deleteLeftNode(){
         if($this->isEmpty() || $this->leftNode->isEmpty()) return false;
         $currentNode = $this->leftNode;
         $this->leftNode = new binary_tree();
         return $currentNode;
     }
 
     /**
      * 删除右节点 并返回 右节点的值
      * @return boolean|Ambigous <NULL, string, binary_tree>
      */
     public function deleteRightNode(){
         if($this->isEmpty() || $this->rightNode->isEmpty()) return false;
         $currentNode = $this->rightNode;
         $this->rightNode = new binary_tree();
         return $currentNode;
     }
 
     /**
      * 前序排序
      * @param node $node
      * @return boolean
      */
     public function preOrder($node){
         if($node->isEmpty()) return false;
         $l=$r=array();
         $l=$this->preOrder($node->leftNode);
 
         $r=$this->preOrder($node->rightNode);
         if(!$l){
             $l=array();
         }
         if(!$r){
             $r=array();
         }
         return array_merge(array($node->data),$l,$r);
     }
 
     /**
      * 中序排序
      * @param node $node
      * @return boolean
      */
     public function middleOrder($node){
         if($node->isEmpty()) return false;
         $l=$r=array();
         $l=$this->middleOrder($node->leftNode);
 
         $r=$this->middleOrder($node->rightNode);
         if(!$l){
             $l=array();
         }
         if(!$r){
             $r=array();
         }
         return array_merge($l,array($node->data),$r);
     }
 
     /**
      * 后续排序
      * @param node $node
      * @return boolean
      */
     public function lastOrder($node){
         if($node->isEmpty()) return false;
         $l=$r=array();
         $l=$this->lastOrder($node->leftNode);
         $r=$this->lastOrder($node->rightNode);
         if(!$l){
             $l=array();
         }
         if(!$r){
             $r=array();
         }
         return array_merge($l,$r,array($node->data));
     }
 
     /**
      * 排序
      * @param string $order
      * @return boolean|Ambigous <boolean, multitype:>
      */
     public function getList($order='pre'){
 
         if($this->isEmpty()) return false;
 
         switch($order){
             case 'pre':
                 $orderlist=$this->preOrder($this);
                 break;
             case 'middle':
                 $orderlist=$this->middleOrder($this);
                 break;
             case 'last':
                 $orderlist=$this->lastOrder($this);
         }
         return $orderlist;
     }
 
     public function compare($data){
 
         return $data-$this->data;
     }
 
     /**
      * 获取叶子节点
      * @param binary_tree $node
      * @param data $data
      * @param string $pos
      * @return boolean|binary_tree|unknown
      */
     public function getLeafNode($node,$data,$pos='left'){
 
         while(!$node->isLeaf($pos)){
             if(!is_object($node->rightNode) || !is_object($node->leftNode)){
                 break;
             }
             $currentNode=$node;
             if($pos=='left'){
 
                 $diff=$node->compare($data);
                 if($diff==0){
                     return false;
                 }elseif($diff<0){
                     $node=$node->leftNode;
                 }else{
                     $node=$node->rightNode;
                 }
             }else{
 
                 $diff=$node->compare($data);
                 if($diff==0){
                     return false;
                 }elseif($diff<0){
                     $node=$node->leftNode;
                 }else{
                     $node=$node->rightNode;
                 }
 
 
             }
             if(!$node){
                 $node = new binary_tree();
 
 
                 break;
             }
 
         }
 
         if($node->isLeaf($pos))  return $node;
         return $currentNode;
 
     }
 
      /**
       * 查找指定元素
       * @param data $data
       * @return multitype:NULL |boolean
       */
     public function find($data){
        $parentNode=$currentNode=$this;
        $pos='root';
        while (!$currentNode->isEmpty()){
            $diff=$currentNode->compare($data);
 
            if($diff==0){
 
                return array('current'=>&$currentNode,'parent'=>&$parentNode,'pos'=>&$pos);
            }elseif($diff<0){
                if(!$currentNode->leftNode->isEmpty()){
                    $parentNode=&$currentNode;
                    $pos='left';
                    $currentNode=&$currentNode->leftNode;
                }else{
                    $parentNode=&$currentNode;
                    $pos='right';
                    $currentNode= &$currentNode->rightNode;
                }
            }else{
                if(!$currentNode->rightNode->isEmpty()){
                    $parentNode=&$currentNode;
                    $pos='right';
                    $currentNode=&$currentNode->rightNode;
                }else{
                    $parentNode=&$currentNode;
                    $pos='left';
                    $currentNode=&$currentNode->leftNode;
                }
            }
 
        }
        return false;
     }
 
     /**
      * 向二叉树里面插入数据
      * @param unknown $data
      * @return boolean
      */
     public function insert($data){
 
 
         if($this->isEmpty()){
 
             $this->addNode($data);
         }else{
 
             $diff = $this->compare($data);
 
             if($diff==0){
                 return false;
             }elseif($diff<0){
 
                 $LeaNode=$this->getLeafNode($this,$data);
                 $LeaNode->leftNode->insert($data);
             }else{
 
                 $LeaNode=$this->getLeafNode($this,$data,'right');
 
 
                 $LeaNode->rightNode->insert($data);
 
             }
         }
     }
 }
 $binaryTree = new binary_tree();
 
 $binaryTree->insert(100);
 $binaryTree->insert(60);
 
 $binaryTree->insert(50);
 $binaryTree->insert(120);
 $binaryTree->insert(140);
 $binaryTree->insert(160);
 $binaryTree->insert(80);
 $binaryTree->insert(70);
 $binaryTree->insert(40);
 
 echo '<pre>';
 //排序实现有三种 前序、中序、后续、层级排序没有实现
 
 $orderlist=$binaryTree->getList('last');
 //查找
 $obj=$binaryTree->find(50);
 // 删除 有三种方式  leaf、onlyOne、two;
 // leaf 只能删除叶子节点
 // onlyOne 只能删除有一个子节点
 // two 删除有两个节点
 $node=$binaryTree->deleteNode(80,'onlyOne');
 var_dump($binaryTree);die;

转载请注明:My House » 二叉树(二)

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址