數(shù)據(jù)結(jié)構(gòu)之二叉樹——鏈式存儲結(jié)構(gòu)（php代碼實現(xiàn)）

<?php
/**
 * ClearBiTree() 清空二叉樹
 * CreateBiTree() 創(chuàng)建二叉樹
 * BiTreeEmpty() 判斷二叉樹是否為空
 * BiTreeDepth() 返回二叉樹的深度
 * root() 返回二叉樹的根
 * Parent() 返回給定元素的雙親
 * LeftChild() 要返回左孩子的元素
 * RightChild() 要返回右孩子的元素
 * LeftSibling() 要返回左兄弟的元素
 * RightSibling() 要返回右兄弟的元素
 * Insert($data) 插入節(jié)點——遞歸算法
 * insert2($data) 插入節(jié)點——非遞歸算法
 * DeleteSubtree($elem,$LR) 刪除某個節(jié)點的左（右）子樹
 * PreOrderTraverse() 先序遍歷——遞歸算法
 * InOrderTraverse() 中序遍歷——遞歸算法
 * PostOrderTraverse() 后序遍歷——非遞歸算法
 * preOrderTraverse2() 先序遍歷——非遞歸算法
 * preOrderTraverse3() 先序遍歷——非遞歸算法
 * inOrderTraverse2() 中序遍歷——非遞歸算法
 * inOrderTraverse3() 中序遍歷——非遞歸算法
 * postOrderTraverse2() 后序遍歷——非遞歸算法
 */
 
 
class BiNode{
    public $data;
    public $lchild;
    public $rchild;
    public function __construct($data){
        $this->data=$data; //節(jié)點數(shù)據(jù)
        $this->lchild=null;//左孩子的指針
        $this->rchild=null;//右孩子的指針
    }
}
class LinkBiTree{
    private  $root; //二叉樹的根節(jié)點
    private static $preArr; //用于保存先序遍歷后的數(shù)據(jù)
    private static $inArr; //用于保存中序遍歷后的數(shù)據(jù)
    private static $postArr; //用于保存后序遍歷后的數(shù)據(jù)
    private static $levelArr; //用于保存后序遍歷后的數(shù)據(jù)
    private static $count; //記錄創(chuàng)建二叉樹結(jié)點的個數(shù)
    const MAX_LEVEL=2;//二叉樹最大的層數(shù)
    public static  $test;

    public function __construct(){
        $this->root=null;//指向根節(jié)點,初始化時為空樹
        self::$count=0;
    }

    /**
     * 清空二叉樹
     */
    public function ClearBiTree(){
        $this->clearTree($this->root);
    }
    /**
     * @param $root 表示樹的根節(jié)點
     */
    private function clearTree($root){
        if($root){
            if($root->lchild){
                $this->clearTree($root->lchild); //清空左子樹
            }
            if($root->rchild){
                $this->clearTree($root->rchild); //清空右子樹
            }
            unset($root); //釋放根節(jié)點
            $root=null;
        }
    }
    //先序遍歷
    public function PreOrderTraverse(){
        $this->preTraverse($this->root);
        return self::$preArr;
    }
    private function preTraverse($root){
        if($root){
            self::$preArr[]=$root->data; //先訪問根節(jié)點
            $this->preTraverse($root->lchild);//再先序遍歷左子樹
            $this->preTraverse($root->rchild);//最后先序遍歷右子樹
        }
    }

    //中序遍歷
    public function  InOrderTraverse(){
        $this->inTraverse($this->root);
        return self::$inArr;
    }
    private function inTraverse($root){
        if($root){
            $this->inTraverse($root->lchild); //先中序遍歷左子樹
            self::$inArr[]=$root->data; //再訪問根節(jié)點
            $this->inTraverse($root->rchild);//最后中序遍歷右子樹
        }
    }

    //后序遍歷
    public function PostOrderTraverse(){
        $this->postTraverse($this->root);
        return self::$postArr;
    }
    private function postTraverse($root){
        if($root){
            $this->postTraverse($root->lchild); //先后序遍歷左子樹
            $this->postTraverse($root->rchild); //再后序遍歷右子樹
            self::$postArr[]=$root->data; //最后再訪問根節(jié)點
        }
    }

    //層序遍歷
    public function LevelOrderTraverse(){
        for($i=1;$i<=$this->BiTreeDepth();$i++){
            $this->levelTraverse($this->root,$i);
        }
        return self::$levelArr;
    }
    private function levelTraverse($root,$level){
        if($root){
            if($level==1){
                self::$levelArr[]=$root->data;
            }
            $this->levelTraverse($root->lchild,$level-1);
            $this->levelTraverse($root->rchild,$level-1);
        }
    }

    //創(chuàng)建二叉樹
    public function CreateBiTree(){
        $this->createTree($this->root);
    }
    //此處使用先序輸入數(shù)據(jù)的方式來創(chuàng)建的
    private function createTree(&$root){
        $node=new BiNode(mt_rand(1,20));
        self::$count++;
        if(self::$count<=pow(2,self::MAX_LEVEL)-1){
            $root=$node;
            self::$test[]=$root->data;
            $this->createTree($root->lchild);
            $this->createTree($root->rchild);
        }
    }

    //判斷二叉樹是否為空
    public function BiTreeEmpty(){
//        if($this->root){
//            return false;
//        }else{
//            return true;
//        }
        return $this->root==null;
    }

    //返回二叉樹的深度
    public function BiTreeDepth(){
       return $this->treeDepth($this->root);
    }
    private function treeDepth($root){
        //求左子樹的深度
        $arr=array();
        $root=$this->root;
        $level=0;
        $num=0;
        array_push($arr,$root);
        while(count($arr)!=0){
            $root=array_shift($arr);
            $num++;
            if($root->lchild){
                array_push($arr,$root->lchild);
            }
            if($root->rchild){
                array_push($arr,$root->rchild);
            }
        }
        while($num>pow(2,$level-1)-1){
            $level++;
        }
        $level--;
        return $level;
    }

    //返回二叉樹的根
    public function Root(){
        return $this->root==null ? 'Null':$this->root->data;
    }

    //返回給定元素的雙親
    //此處分別使用php內(nèi)部的array_push()和array_shift()這兩個函數(shù)模擬隊列

    /**
     * @param $elem
     * @return string
     * 返回給定元素的雙親
     * 思路：1.使用數(shù)組隊列來保存節(jié)點的指針
     *       2.將根節(jié)點從隊尾壓入數(shù)組隊列中
     *       3.然后取出隊首元素，使其左節(jié)點、右節(jié)點分別于給定的元素比較
     *       4.相等的就返回上一步中取出的隊首元素，否則，將此隊首元素的左右節(jié)點指針分別壓入隊尾
     *       5.重復(fù)第3步
     */
    public function Parent($elem){
        if($this->root){
            $arr=array();//此處數(shù)組是當隊列來使用的，用于存放樹（包括子樹）的根指針
            array_push($arr,$this->root);
            while(count($arr)!=0){
                $root=array_shift($arr);
                if($root->lchild && $root->lchild->data==$elem ||
                    $root->rchild && $root->rchild->data==$elem){

                    return $root->data;
                }else{
                    if($root->lchild){
                        array_push($arr,$root->lchild);
                    }
                    if($root->rchild){
                        array_push($arr,$root->rchild);
                    }
                }
            }
        }
        return false;
    }

    /**
     * @param $elem 要返回左孩子的元素
     * @return string
     * 思路：同上
     */
    public function LeftChild($elem){
        if($this->root){
            $arr=array();
            array_push($arr,$this->root);
            while(count($arr)!=0){
                $root=array_shift($arr);
                if($root->data==$elem && $root->lchild){
                    return $root->lchild->data;
                }
                if($root->lchild){
                    array_push($arr,$root->lchild);
                }
                if($root->rchild) {
                    array_push($arr, $root->rchild);
                }
            }
        }
        return false;
    }

    /**
     * @param $elem 要返回左孩子的元素
     * @return string
     * 思路：同上
     */
    public function RightChild($elem){
        if($this->root){
            $arr=array();
            array_push($arr,$this->root);
            while(count($arr)!=0){
                $root=array_shift($arr);
                if($root->data==$elem && $root->rchild){
                    return $root->rchild->data;
                }
                if($root->lchild){
                    array_push($arr,$root->lchild);
                }
                if($root->rchild){
                    array_push($arr,$root->rchild);
                }
            }
        }
        return false;
    }


    /**
     * @param $elem 要返回左兄弟的元素
     * @return string
     */
    public function LeftSibling($elem){
        $parent=$this->Parent($elem);
        $leftChild=$this->LeftChild($parent);
        $rightChild=$this->RightChild($elem);
        if($rightChild==$elem && $leftChild){
            return $leftChild;
        }
        return 'Error';
    }

    /**
     * @param $elem 要返回右兄弟的元素
     * @return string
     */
    public function RightSibling($elem){
        $parent=$this->Parent($elem);
        $leftChild=$this->LeftChild($parent);
        $rightChild=$this->RightChild($elem);
        if($leftChild==$elem && $rightChild){
            return $rightChild;
        }
        return 'Error';
    }

    /**
     * @param $data 要插入的數(shù)據(jù)
     * 思路：1.插入的數(shù)據(jù)比樹中的根(包括子樹)節(jié)點小時，就放在根節(jié)點的左子樹上；
     *       2.比根節(jié)點大時，插入到右子樹上；
     *  注意：因為插入的位置不是葉節(jié)點就是只有左(或右)子樹的節(jié)點，所以可以得知此遞歸的出口肯定是某個節(jié)點的左(或右)子樹指針為空的時候。當此節(jié)點的左(右)都不為空的時候，遞歸就會持續(xù)下去，直到為左(右)子樹有一邊或全部為空的節(jié)點出現(xiàn)為止。
     */
    public function Insert($data){
        $node = new BiNode($data);
        $this->insertNode($node,$this->root);
    }
    private function insertNode($node,&$root){
        if(!$root){
            $root=$node;
        }else{
            if($node->data > $root->data){
                $this->insertNode($node,$root->rchild);
            }else if($node->data < $root->data){
                $this->insertNode($node,$root->lchild);
            }else{
                return;
            }
        }
    }

    //非遞歸算法實現(xiàn)插入節(jié)點操作
    public function insert2($data){
        $node=new BiNode($data);
        if(!$this->root){
            $this->root=$node;
        }else {
            $arr = array();
            array_push($arr, $this->root);
            while (count($arr) != 0) {
                $root = array_shift($arr);
                //表示如果要插入的數(shù)據(jù)$node->data大于根節(jié)點的數(shù)據(jù)$root->data并且根節(jié)點的
                //左子樹為空的話，那么就將$node->data賦值給左子樹
                if ($node->data < $root->data && !$root->lchild) {
                    $root->lchild = $node;
                    break;
                    //此處為大于，思路與小于相似
                }else if($node->data > $root->data && !$root->rchild){
                    $root->rchild = $node;
                    break;
                }
                //以下兩個if語句，表示如果上面的兩個條件都不滿足的話，那么就將跟的左右節(jié)點分別要入隊列，繼續(xù)循環(huán)
                if($root->lchild){
                    array_push($arr,$root->lchild);
                }
                if($root->rchild){
                    array_push($arr,$root->rchild);
                }
            }
        }
    }

    /**
     * @param $elem 要刪除的那個節(jié)點的子樹
     * @param $LR 表示是要刪除左子樹還是右子樹
     */
    public function DeleteSubtree($elem,$LR){
        if($this->root){
            $arr=array();
            array_push($arr,$this->root);
            while(count($arr)!=0){
                $root=array_shift($arr);
                if($root->data==$elem && $LR==0){
                    $root->lchild=null;
                }
                if($root->data==$elem && $LR==1){
                    $root->rchild=null;
                }
                if($root->lchild){
                    array_push($arr,$root->lchild);
                }
                if($root->rchild){
                    array_push($arr,$root->rchild);
                }
            }
        }
    }

    /*
    以下是先序，中序，后序，層序的非遞歸實現(xiàn)算法
    除了層序遍歷使用了隊列外，其他的是利用棧來實現(xiàn)的
    思路: 1.輸出當前根節(jié)點
          2.將當前根節(jié)點的右孩子做壓棧處理
          3.將當前節(jié)點的右孩子作為新的根節(jié)點，如果為空的話，將棧頂元素彈出作為新的根節(jié)點。
          4.重復(fù)1,2,3
    */
    public function preOrderTraverse2(){
        $arr=array();
        $root=$this->root;
        $arrPre=array();
        while($root || count($arr)!=0){
            $arrPre[]=$root->data;
            if($root->rchild){
                $rootR=$this->rchild;
                array_push($arr,$rootR);
            }
            $root=$root->lchild;
            if(!$root){
                $root=array_pop($arr);
            }
        }
        return $arrPre;
    }

    /*
     * 思路：1.將根節(jié)點壓棧
     *       2.彈出棧頂元素作為新的根節(jié)點
     *       3.根據(jù)?！冗M后出的特性，先進根節(jié)點的右孩子做壓棧處理，再將其左孩子做壓棧處理；
     *       4.重復(fù)2,3
     * 注：此算法與上面的算法基本思想是相同的，只是細節(jié)處理上有所不同。
     */
    public function preOrderTraverse3(){
        $arr=array();
        $root=$this->root;
        array_push($arr,$root);
        while(count($arr)!=0){
            $root=array_pop($arr);
            $arrPre[]=$root->data;
            if($root->rchild){
                array_push($arr,$root->rchild);
            }
            if($root->lchild){
                array_push($arr,$root->lchild);
            }
        }
        return $arrPre;
    }

    //中序遍歷算法2
    /*
     * 思路：1.將根節(jié)點壓棧
     *       2.將根節(jié)點的左孩子作為新的根節(jié)點,對其進行遍歷
     *       3.如果左子樹遍歷完畢，就將棧中的左子樹結(jié)點彈出并輸出，然后將此彈出結(jié)點的右孩子作為新的根節(jié)點。
     *       4.重復(fù)1,2,3
     *  注：此處或許有人對while循環(huán)的判斷條件有所不理解。因為假如說我們只用$root是否為空來作為判斷條件的話，那么當我們遍歷完左子樹后，程序就結(jié)束了，顯然不是我們要的結(jié)果；假如我們只用棧$arr是否為空為判斷條件的話，那么循環(huán)根本無法進行。
     *
     */
    public function inOrderTraverse2(){
        $arr=array();
        $root=$this->root;
        while($root || count($arr)!=0){
            if($root){
                //根指針進棧，遍歷左子樹.此處之所以沒有在循環(huán)外先將整棵樹的根節(jié)點做壓棧處理，是因為，如果這樣做了，那么此處對左子樹的遍歷就會出現(xiàn)死循環(huán)，因為這是的判斷條件就是$root->lchild，而不是$root了，倘若還是$root那么棧中就會有兩個根(整棵樹)。
                array_push($arr,$root);
                $root=$root->lchild;
            }else{
                //根指針退棧，訪問根節(jié)點，遍歷右子樹
                $root=array_pop($arr);
                $arrIn[]=$root->data;
                $root=$root->rchild;
            }
        }
        return $arrIn;
    }

    //中序遍歷算法3
    /*
     * 思路：1.先進根做壓棧處理
     *       2.遍歷左子樹
     *       3.取出棧頂元素并將輸出的節(jié)點作為新的根節(jié)點
     *       4.將根節(jié)點的右孩子壓棧并重新作為新的根節(jié)點
     *       5.重復(fù)2，3，4
     * 注：此算法和上面的算法的整體思想是一樣的
     */
    public function inOrderTraverse3(){
        $arr = array();
        $root = $this->root;
        array_push($arr,$root);
        while (count($arr) != 0) {
            while($root){
                array_push($arr,$root->lchild);
                $root=$root->lchild;
            }
            array_pop($arr);
            if(count($arr)!=0){
                $root=array_pop($arr);
                $arrIn[]=$root->data;
                array_push($arr,$root->rchild);
                $root=$root->rchild;
            }
        }
        return $arrIn;
    }

    //因為先序是根左右，而后序是左右根，如果將后序反轉(zhuǎn)180度的話，那么順序就是根右左.根據(jù)遞歸轉(zhuǎn)換為非遞歸（棧）的方法——如果一個函數(shù)內(nèi)有多于一個的遞歸調(diào)用那么此時，棧的進入順序應(yīng)該與遞歸調(diào)用的順序相反。因為棧的特性是先進后出。
    //后序遍歷算法2
    public function postOrderTraver2(){
        $arr=array();
        $root=$this->root;
        array_push($arr,$root);
        while(count($arr)!=0){
            $root=array_pop($arr);
            $arrPost[]=$root->data;
            if($root->lchild){
                array_push($arr,$root->lchild);
            }
            if($root->rchild){
                array_push($arr,$root->rchild);
            }
        }
        return array_reverse($arrPost);
    }

    //層級遍歷算法2
    public function levelOrderTraverse2(){
        $arr=array();
        $root=$this->root;
        array_push($arr,$root);
        while(count($arr)!=0){
            $root=array_shift($arr);
            $arrLevel[]=$root->data;
            if($root->lchild){
                array_push($arr,$root->lchild);
            }
            if($root->rchild){
                array_push($arr,$root->rchild);
            }
        }
        return $arrLevel;
    }
    /*
     * 遞歸轉(zhuǎn)非遞歸算法小結(jié)：
     *  1.如果函數(shù)體內(nèi)只有一個遞歸調(diào)用，那么直接使用棧或隊列等轉(zhuǎn)換即可；
     *  2.如果有多個遞歸調(diào)用并且相鄰，比如先序和后序遍歷算法，那么轉(zhuǎn)為非遞歸算法時，先后順序要倒轉(zhuǎn)；
     *  3.如果有多個遞歸但不相鄰，比如中序遍歷，那么就直接按照原先的順序依次轉(zhuǎn)換即可。但如果里面依然有部分相鄰，那么就按小結(jié)2操作。
     *  4.轉(zhuǎn)換時，我們應(yīng)該將哪些數(shù)據(jù)放入棧中呢。根據(jù)函數(shù)調(diào)用的原理，在調(diào)用一個函數(shù)時，內(nèi)存中就會開辟一個?？臻g，里面保存了函數(shù)的實參，局部變量和函數(shù)調(diào)用時的返回地址等，而我們要放入棧中的就是實參和局部變量（此處的局部變量是指后序遞歸要用到的局部變量）。
     */

}