數據結構之完全二叉樹——順序存儲結構（php代碼實現）

<?php
/**
 * 二叉樹的順序結構的實現比較適合實現完全二叉樹和滿二叉樹。
 * 我們可以使用數組來存儲二叉樹每個結點的數據元素，使用數組
 * 下標表示結點之間的關系，根據完全（滿）二叉樹的定義，結點間的關系如下：
 *      1.第i層上，結點序號范圍是pow(2,i-1)-1——pow(2,i)-2；
 *      2.k層的完全(滿)二叉樹最多有pow(2,k)-1個結點；
 *      3.序號為i的結點，其雙親節點的序號為(i+1)/2-1；
 *      4.序號為i的節點，其左右孩子的序號分別為2i+1和2i+2
 *      5.除了根節點，序號為奇數的節點是其雙親的左孩子，它的右兄弟是它的序號加1；
 *      6.除了根節點，序號為偶數的節點是其雙親的右孩子，它的左兄弟是它的序號減1；
 *
 */
class SqBiTree{
    public $SqArr; //用于存儲完全二叉樹節點數據元素，數據元素之間的關系用數組下標表示
    public $root; //表示完全二叉樹的根節點
    /**
     * @var int
     */
    public $length;//表示完全二叉樹當前幾點的個數
    public static $preArr;
    public static $inArr;
    public static $postArr;

    /**
     * @param $arr
     * 初始化
     */
    public function __construct($arr=array()){
        $this->SqArr=$arr;
        $this->root=$this->SqArr[0];
        $this->length=count($this->SqArr);
    }

    /**
     * @return bool
     * 判斷完全二叉樹是否為空
     */
    public function BiTreeEmpty(){
        if(!$this->root){ //如果為null，0，‘’，false等都是表示空樹
            return true;
        }else{
            return false;
        }
    }

    /**
     * @return int|string
     * 思路：1.如果樹的節點總個數大于最大層數上一層的節點個數，并且小于等于最大層的個數，則即可找出最大層數.
     */
    public function BiTreeDepth(){
        $i=1; //$i表示樹的層數
        while($i){
            //此判斷是根據上面關系2.k層的節點數最多為pow(2,k)-1
            if($this->length>pow(2,$i-1)-1 && $this->length<=pow(2,$i)-1){

                return $i;
            }
            $i++;
        }
        return 'ERROR';
    }

    /**
     * @param $level 表示要返回的節點在第幾層
     * @param $pos 表示要返回的節點在此層的位置,$pos的值是大于等于1的整合素
     * @return string 表示如果輸入的層數大于最大層數，就返回Error
     * 思路：1.如果$level大于樹的最大深度并且$pos小于1，則返回錯誤
     *       2.如果返回元素的下標序號<=當前層的最大下標序號，則說明存在應用元素
     */
    public function Value($level,$pos){
        if($level>$this->BiTreeDepth() && $pos<1){
            return 'Error';
        }
        $elmpos=pow(2,$level-1)-2+$pos;//表示要返回的元素的下標
        if($elmpos<=pow(2,$level)-2){
            return $this->SqArr[$elmpos];
        }
        return 'Error';
    }

    /**
     * @param $level
     * @param $pos
     * @param $value
     * @return string
     * 給第幾層，第幾個位置的節點賦予新值
     * 思路：同上
     */
    public function Assign($level,$pos,$value){
        if($level>$this->BiTreeDepth() && $pos<1 && !$value){
            return 'Error';
        }
        $elmpos=pow(2,$level-1)-2+$pos;//表示要返回的元素的下標
        if($elmpos<=pow(2,$level)-2){
            $this->SqArr[$elmpos]=$value;
        }
    }


    /**
     * @param $elem 表示給定要找雙親的元素
     * 返回給定元素的雙親
     * 思路：1.找出$elem元素所在的下標；
     *       2.根據子節點與雙親節點之間的關系(最上面的第3條)，返回此元素(除了根節點)的雙親節點;
     */
    public function Parent($elem){
        //因為下標為0的節點為根節點，所以要從1開始計算
        for($i=1;$i<$this->length;$i++){
            if($this->SqArr[$i]==$elem){
                return $this->SqArr[($i+1)/2-1];
            }
        }
        return 'Error';
    }

    /**
     * @param $elem
     * @return string
     * 返回給定元素的左孩子
     * 思路：1.找出$elem元素所在的下標；
     *       2.根據最上面的4條，得出左孩子的下標為2*$i+1。但2*$i+1必須小于$this->length,否則就過界了
     */
    public function LeftChild($elem){
        for($i=0;$i<$this->length;$i++){
            if($this->SqArr[$i]==$elem && $i*2+1<$this->length){
                return $this->SqArr[$i*2+1];
            }
        }
        return 'Error';
    }

    /**
     * @param $elem
     * @return string
     * 返回給定元素的右孩子
     * 思路：1.找出$elem元素所在的下標；
     *       2.根據最上面的4條，得出右孩子的下標為2*$i+2。但2*$i+2必須小于$this->length,否則就過界了
     */
    public function RightChild($elem){
        for($i=0;$i<$this->length;$i++){
            if($this->SqArr[$i]==$elem && $i*2+2<$this->length){
                return $this->SqArr[$i*2+2];
            }
        }
        return 'Error';
    }

    /**
     * @param $elem
     * @return string
     * 返回給定元素的左兄弟
     * 思路：1.找出$elem元素所在的下標；
     *       2.根據最上面的6條，得出左孩子的下標為$i-1，并且$i對2取余必須為0
     *
     */
    public function LeftSibling($elem){
        for($i=0;$i<$this->length;$i++){
            if($this->SqArr[$i]==$elem && $i%2==0){
                return $this->SqArr[$i-1];
            }
        }
        return 'Error';
    }

    /**
     * @param $elem
     * @return string
     * 返回給定元素的右兄弟
     * 思路：1.找出$elem元素所在的下標；
     *       2.根據最上面的5條，得出右孩子的下標為$i+1，并且$i對2取余必須為1.并且$i+1必須小于$this->length,否則就會出界.
     *
     */
    public function RightSibling($elem){
        for($i=0;$i<$this->length;$i++){
            if($this->SqArr[$i]==$elem && $i%2 && $i+1<$this->length){
                return $this->SqArr[$i+1];
            }
        }
        return 'Error';
    }


    /**
     * 先序遍歷
     * 注：此處之所以使用兩個方法來完成是因為this->SqArr本身就是一棵樹
     *      在類中無法給自己傳遞參數，只能間接調用。
     */
    public function preTraverse(){
        if(!$this->root){
            return 'Error';
        }
       $this->PreOrderTraverse($this->SqArr[0],0);
        return self::$preArr;
    }
    public function PreOrderTraverse($root,$id){
        if(!$root){
            return 'Error';
        }
        self::$preArr[]=$root;
        if($id*2+1<$this->length && $root){
            $this->PreOrderTraverse($this->SqArr[$id*2+1],$id*2+1);
        }
        if($id*2+2<$this->length && $root){
            $this->PreOrderTraverse($this->SqArr[$id*2+2],$id*2+2);
        }
    }

    //中序遍歷
    public function inTraverse(){
        if(!$this->root){
            return 'Error';
        }
        $this->InOrderTraverse($this->SqArr[0],0);
        return self::$inArr;
    }
    public function InOrderTraverse($root,$id){
        if(!$root){
            return 'Error';
        }
        if($id*2+1<$this->length && $root){
            $this->InOrderTraverse($this->SqArr[$id * 2 + 1], $id * 2 + 1);
        }
        self::$inArr[]=$root;
        if($id*2+2<$this->length && $root){
            $this->InOrderTraverse($this->SqArr[$id * 2 + 2], $id * 2 + 2);
        }
    }

    //后序遍歷
    public function postTraverse(){
        if(!$this->root){
            return 'Error';
        }
        $this->PostOrderTraverse($this->SqArr[0],0);
        return self::$postArr;
    }
    public function PostOrderTraverse($root,$id){
        if(!$root){
            return 'Error';
        }
        if($id*2+1<$this->length && $root){
            $this->PostOrderTraverse($this->SqArr[$id * 2 + 1], $id * 2 + 1);
        }
        if($id*2+2<$this->length && $root){
            $this->PostOrderTraverse($this->SqArr[$id * 2 + 2], $id * 2 + 2);
        }
        self::$postArr[]=$root;
    }

    //層序遍歷
    public function LevelOrderTraverse(){
        for($i=0;$i<$this->length;$i++){
            $arr[]=$this->SqArr[$i];
        }
        return $arr;
    }
}