利用PHP實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之二叉樹（小白系列文章六）

Cympros 發(fā)布于2019-06-28 13:56 / 3456人閱讀

摘要：回來更新一波，最近刷劍指，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運(yùn)用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學(xué)了一些樹的知識，發(fā)現(xiàn)也用不上，我想說的是，讀一本書體現(xiàn)不了這本書

回來更新一波，最近刷《劍指offer》，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運(yùn)用好多啊～

/**
*    PHP二叉樹算法
*    Created on 2017-5-6
*   Update  on 2017-8-10
*    Author     entner
*    Email     [email protected]
*/

引子

????很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎；還有很多人學(xué)了一些樹的知識，發(fā)現(xiàn)也用不上，我想說的是，讀一本書體現(xiàn)不了這本書的價(jià)值，要多讀幾本才會把你和別人的差別體現(xiàn)出來。
????二叉樹是嚴(yán)格定義的，有很好的對稱性和比較高的數(shù)據(jù)關(guān)聯(lián)度，對數(shù)據(jù)的存儲和計(jì)算，有很好的演示作用，比如完全二叉樹：

????當(dāng)然，二叉樹更適合鏈表存儲，效率更高，總的來說，以二叉樹為基礎(chǔ)我們可以衍生出許多神奇的運(yùn)用，舉幾個常用的場景為我說的話正言：

編譯器表達(dá)式處理

快速查找與排序

文件壓縮

文件系統(tǒng)管理

游戲場景劃分、監(jiān)測、渲染

 我承認(rèn)，上面好多東西你并不會直接接觸，但是，我們關(guān)鍵是去學(xué)習(xí)一種思維和設(shè)計(jì)，退一萬步也可以增加一點(diǎn)見識：）

一、二叉樹抽象數(shù)據(jù)類型操作條目

關(guān)于書的操作太多了，我只列一些常用的(這些都是?？嫉闹R點(diǎn))，有興趣的相信也有技能去淘到“好貨”

 -InitTree    構(gòu)造空樹
 -PreTra    返回樹中某結(jié)點(diǎn)的值
 -InTra        給樹中某結(jié)點(diǎn)賦值為value
 -LevelTra     返回某非根結(jié)點(diǎn)的雙親，否則返回空
 -LeftChild  返回某非葉結(jié)點(diǎn)的最左孩子，否則返回空

二、默寫二叉樹常用數(shù)據(jù)結(jié)構(gòu)

默寫會讓你記憶更深刻，同時(shí)也會鍛煉抽象的邏輯思維，一邊看不懂，就多看幾遍，再查一查相關(guān)資料，應(yīng)該問題不大，你甚至可以找張紙默寫一下。

/**     
*InitTree 初始化樹
*    
*
    Typedef int TElementType //構(gòu)造一個數(shù)據(jù)類型
    Typedef Struct Tree{    //構(gòu)造二叉樹抽象數(shù)據(jù)類型
        TElementType data;    //聲明一個數(shù)組，先構(gòu)建一個樹
        Struct Tree *leftChild;    //左孩子節(jié)點(diǎn)
        Struct Tree *rightChild;   //右孩子節(jié)點(diǎn)
    }Tree;
*／

/**
 * Value     獲取樹的結(jié)點(diǎn)(前序遍歷)
 * Return   返回獲取的結(jié)點(diǎn)值
     Status Value（Tree *T，int e）{
        if(T == null){
            return error;
        }
        e = T->Value(T->leftChild);
        e = T->Value(T->rightChild);
        return e;
     }
 */

/**
 * Assign     給樹中某結(jié)點(diǎn)賦值為v(前序遍歷)
 * Return   返回賦值后的結(jié)點(diǎn)值
     Status Assign（Tree *T，int e, TElementType v）{
        if(T == null){
            return error;
        }
        e = T->Assign(T->leftChild);
        e = T->Assign(T->rightChilg);
        e = v;
        return e;
     }
 */

三、二叉樹結(jié)構(gòu)基本實(shí)現(xiàn)

/**
*    PHP二叉樹算法
*    Created on 2017-8-7
*    Author     entner
*    Email     [email protected]
*/

/*
    假設(shè)我構(gòu)造一顆如下的二叉樹
            A
        B       C
      #   D   #   # 
        #   #
*/

error_reporting(E_ALL ^ E_WARNING);



Class BinaryTree{

    
    public $lChild;
    public $rChild;
    public $value;

    /*    初始化構(gòu)造空樹    */
    public function __construct($data = null){
        $this->value = $data;
    }



    /**
     * TODO:構(gòu)建二叉樹
     * @param $root object 二叉樹
     */
    public function preOrderCreateBT(&$root){

        
        while(!is_null($elem = array_shift($this->value))){
            $root = "";
            if($elem == null){    #判斷：當(dāng)數(shù)組為空時(shí)    
                return $root;
            }else if($elem == "#"){    #判斷：當(dāng)數(shù)組為無效單元時(shí)，該節(jié)點(diǎn)是虛節(jié)點(diǎn)(無孩子節(jié)點(diǎn))，退出當(dāng)前遞歸，執(zhí)行下一個遞歸
                $root->value = "#";
                return ;
            }else{
                $root->value = $elem;
                $this->preOrderCreateBT($root->lChild);
                $this->preOrderCreateBT($root->rChild);
            }
        }
        
        
        return $root;
    }


    /**
     * TODO:先序遍歷二叉樹
     * @param $tree object 二叉樹
     * @param $temp array  二叉樹輸出節(jié)點(diǎn)存儲數(shù)組
     */
    public function printBTPreOrder($tree,&$temp){
        if($tree != null){
            $temp[] = $tree->data;
            $this->printBTPreOrder($tree->lChild,$temp);
            $this->printBTPreOrder($tree->rChild,$temp);
        }else{
            return ;
        }
        return $temp;
    }

    /**
     * TODO:中序遍歷二叉樹
     * @param $tree object 二叉樹
     * @param $temp array  二叉樹輸出節(jié)點(diǎn)存儲數(shù)組
     */
    public function printBTInOrder($tree,&$temp){
        if($tree != null){
            $this->printBTInOrder($tree->lChild,$temp);
            $temp[] = $tree->data;
            $this->printBTInOrder($tree->rChild,$temp);
        }else{
            return;
        }
        return $temp;
    }

    /**
     * TODO:后序遍歷二叉樹
     * @param $tree object 二叉樹
     * @param $temp array  二叉樹輸出節(jié)點(diǎn)存儲數(shù)組
     */
    public function printBTPosOrder($tree,&$temp){
        if($tree != null){
            $this->printBTPosOrder($tree->lChild,$temp);
            $this->printBTPosOrder($tree->rChild,$temp);
            $temp[] = $tree->data;
            
        }else{
            return;
        }
        return $temp;
    }

    /**
     * TODO:層序遍歷二叉樹（需要將書中節(jié)點(diǎn)放入隊(duì)中）
     * 
     */
    function PrintFromTopToBottom(&$root)
{
    // write code here

    $queueVal = array();
       $queue = array();
    if($root == null){
        return $queueVal;    #注意當(dāng)二叉樹為空樹時(shí)，應(yīng)該返回空數(shù)組
    }
   
    array_push($queue,$root);
    
    while($queue){
        $node = array_shift($queue);
        array_push($queueVal,$node->value);
        if($node->lChild != null){
            array_push($queue,$node->lChild);
        }
        if($node->rChild != null){
            array_push($queue,$node->rChild);
        }
         
    }
    return $queueVal;
}


    /**
     * TODO:樹的深度
     * 
     */
    public function treeDeepth(&$root){
        if($root == null){
            return 0;
        }
        
        if($root != null){
            
            $ld = $this->treeDeepth($root->lChild) + 1;
            $rd = $this->treeDeepth($root->rChild) + 1;    

        }
        $max = max($ld,$rd);

        return $max;
    }

}
$node = array(
        0=>"A",
        1=>"B",
        2=>"#",
        3=>"D",
        4=>"#",
        5=>"#",
        6=>"C",
        7=>"#",
        8=>"#",
    );


$object = new BinaryTree($node);
$tree = $object->preOrderCreateBT();
echo "";
print_r($tree);
echo $object->treeDeepth($tree) . "
";
print_r($object->PrintFromTopToBottom($tree));

以下為效果圖：
分別是構(gòu)造樹的結(jié)構(gòu)、樹的深度、層序遍歷輸出
![圖片描述][3]

四、二叉排序樹
/**
*FindBitTree      二叉樹查找
*@param T BItTree 代指二叉樹及其元素結(jié)點(diǎn)
*@param key int   樹中某結(jié)點(diǎn)
*@param f   point 指向該結(jié)點(diǎn)父結(jié)點(diǎn)
*@param p   point 指向該元素結(jié)點(diǎn)或空
*@param return bool true|false
   status SearchBST(BitTree T,int key,BitTree f = null,BitTree p){
        if(!T){
            p = f;
            return false;
        }
        if(key == T->data){
            p = T；//其實(shí)就是根結(jié)點(diǎn)
            return true；
        }else if(key data){
            SearchBST(T->lChild,int key,T,p);
        }else if(key >T->data){
            SearchBST(T->rChild,int key,T,p);
        }
   }
*/

/**
InsertBitTree      二叉樹插入 
*【如果當(dāng)前樹中沒有key元素，則插入，插入的結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)】
*@param T BItTree 代指二叉樹及其元素結(jié)點(diǎn)
*@param key int   樹中某結(jié)點(diǎn)
*@param return bool true|false
   status InsertBST(BitTree T，int key){
        if(SearchBST(T,key,NULL,&p) == false){
            s->data = key;
            s->lChild = s->rChild = NULL;
            if(!p){
                T= s;
            }else if(key < p->data){
                p->lChild = s;
            }else{
                p->rChild = s;
            }
          return true;
        }
        return false;
   }
*/
五、樹應(yīng)用實(shí)現(xiàn)-無限極分類（引用&遞歸）
$items = array(
    1 => array("id" => 1, "pid" => 0, "name" => "江西省"),
    2 => array("id" => 2, "pid" => 0, "name" => "黑龍江省"),
    3 => array("id" => 3, "pid" => 1, "name" => "南昌市"),
    4 => array("id" => 4, "pid" => 2, "name" => "哈爾濱市"),
    5 => array("id" => 5, "pid" => 2, "name" => "雞西市"),
    6 => array("id" => 6, "pid" => 4, "name" => "香坊區(qū)"),
    7 => array("id" => 7, "pid" => 4, "name" => "南崗區(qū)"),
    8 => array("id" => 8, "pid" => 6, "name" => "和興路"),
    9 => array("id" => 9, "pid" => 7, "name" => "西大直街"),
    10 => array("id" => 10, "pid" => 8, "name" => "東北林業(yè)大學(xué)"),
    11 => array("id" => 11, "pid" => 9, "name" => "哈爾濱工業(yè)大學(xué)"),
    12 => array("id" => 12, "pid" => 8, "name" => "哈爾濱師范大學(xué)"),
    13 => array("id" => 13, "pid" => 1, "name" => "贛州市"),
    14 => array("id" => 14, "pid" => 13, "name" => "贛縣"),
    15 => array("id" => 15, "pid" => 13, "name" => "于都縣"),
    16 => array("id" => 16, "pid" => 14, "name" => "茅店鎮(zhèn)"),
    17 => array("id" => 17, "pid" => 14, "name" => "大田鄉(xiāng)"),
    18 => array("id" => 18, "pid" => 16, "name" => "義源村"),
    19 => array("id" => 19, "pid" => 16, "name" => "上壩村"),
);

/**
*TODO:通過引用方式實(shí)現(xiàn)無限極分類
*    
*/
function tree_Classify1($items){
    $tree=array();
    $packData=array();
    foreach ($items as  $data) {
        $packData[$data["id"]] = $data;
    }
    foreach ($packData as $key =>$val){     
        if($val["pid"]==0){//代表跟節(jié)點(diǎn)       
            $tree[]=& $packData[$key];
        }else{
            //找到其父類
            $packData[$val["pid"]]["son"][]=& $packData[$key];
        }
    }
    return $tree;
}

/**
*TODO:通過遞歸方式實(shí)現(xiàn)無限極分類
*      
*/
function tree_Classify2($items,$child="_child",$root = 0){
    $tree=array();
    foreach($items as $key=> $val){

        if($val["pid"]==0){
            //獲取當(dāng)前$pid所有子類 
                unset($items[$key]);
                if(! empty($items)){
                    $child=make_tree1($items,$child,$val["id"]);
                    if(!empty($child)){
                        $val["_child"]=$child;
                    }                   
                }              
                $tree[]=$val; 
        }
    }   
    return $tree;
}

echo "";
print_r(make_tree1($items,$child="_child",$root=0));
``


  [1]: /img/bV7ljv
  [2]: /img/bV7ljz

云服務(wù)器 GPU云服務(wù)器實(shí)現(xiàn)二叉樹二叉樹的存儲結(jié)構(gòu) 二叉樹 php 二叉樹 php

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/25964.html

發(fā)表評論

登陸后可評論

0條評論

Cympros

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow實(shí)現(xiàn)lstm

閱讀 2382·2023-04-26 00:01
Owned-Networks：便宜VPS，1核/1G/30G SSD/1T/1Gbps/KVM/可選

閱讀 832·2021-10-27 14:13
??在爬完一周的朋友圈后，我發(fā)現(xiàn)了.......驚人??秘密

閱讀 1882·2021-09-02 15:11
H5移動端調(diào)試—weinre

閱讀 3415·2019-08-29 12:52
總結(jié)開發(fā)過程踩到的坑（五）（小程序篇）

閱讀 561·2019-08-26 12:00
JAVASCRIPT FUNCTIONS

閱讀 2597·2019-08-26 10:57
javascript代理模式

閱讀 3438·2019-08-26 10:32
了解Webpack嗎？

閱讀 2873·2019-08-23 18:29

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

利用PHP實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之二叉樹（小白系列文章六）

相關(guān)文章

**利用PHP實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之二叉樹（小白系列文章五）**

**【數(shù)據(jù)結(jié)構(gòu)初階之二叉樹】：二叉樹相關(guān)的性質(zhì)和經(jīng)典的習(xí)題（用C語言實(shí)現(xiàn)，附圖詳解）**

**學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹**

PHPer面試必看：分門別類帶你擼《劍指Offer》之二叉樹

數(shù)據(jù)結(jié)構(gòu)之二叉樹（java版）

發(fā)表評論

0條評論

Cympros

男|高級講師

TA的文章

tensorflow實(shí)現(xiàn)lstm

Owned-Networks：便宜VPS，1核/1G/30G SSD/1T/1Gbps/KVM/可選

??在爬完一周的朋友圈后，我發(fā)現(xiàn)了.......驚人??秘密

H5移動端調(diào)試—weinre

總結(jié)開發(fā)過程踩到的坑（五）（小程序篇）

JAVASCRIPT FUNCTIONS

javascript代理模式

了解Webpack嗎？

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

利用PHP實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)之二叉樹（小白系列文章六）

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！