在學習圖之前，中間休息了兩天，感覺二叉樹需要消化一下。所以中間去溫習了下sql，推薦一本工具書《程序員的SQL金典》看名字不像一本好書，但是作為一個不錯的SQL工具書還是可以小小備忘一下。涵蓋內容不詳細但是挺廣，覆蓋多種主流數(shù)據(jù)庫

言歸正傳，以前知道折半查找，二叉樹的概念也是感覺挺有意思，二叉樹的實現(xiàn)有一個案例很不錯，代碼如下

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

class?BiNode{ ????public?$data; ????public?$lchild; ????public?$rchild; ????public?function?__construct($data){ ????????????$this->data?=?$data;//節(jié)點數(shù)據(jù) ????????????$this->lchild?=?null;//左子節(jié)點指針 ????????????$this->rchild?=?null;//右指針 ????} } class?LinkBiTree{ ????private?$root;?//根節(jié)點 ????????private?static?$count;????//結點總數(shù) ????const?MAX_LEVEL?=?2; ????? ????public?function?__construct(){ ????????$this->root?=?null; ????????self::$count?=?0; ????} ????public?function?ClearBiTree(){ ????????$this->clearTree($this->root); ????} ????/** ????*@param?$root?樹的根節(jié)點 ????* ????*/ ????public?function?clearTree($root){ ????????if($root){ ????????????if($root->lchild){ ????????????????$this->clearTree($root->lchild); ????????????} ????????????if($root->rchild){ ????????????????$this->clearTree($root->rchild); ????????????} ????????????unset($root); ????????????$root=null; ????????} ????} ????? ????? }??

其實我更加感興趣的就是赫夫曼樹，能夠給我?guī)砀杏X得才讓我激動，就是100以內猜七次肯定可以猜出來，這種感覺是很奇妙的，當年赫夫曼為了傳輸點卯，更改了數(shù)據(jù)的排列順序，形成了新的儲存序列和標識，是的竟成使用的字母快速找出來，節(jié)省了資源，很棒。

赫爾曼構造算法的實現(xiàn)

初始化HT

輸入初始n個葉子結點：置HT[1…n]的weight值

然后根據(jù)權值來重新安排葉子結點，可以先序可以中序可以后續(xù)也可以中序，只要距離根節(jié)點的搜索順序在前面就好

先序遞歸實現(xiàn)如下

1 2 3 4 5 6 7 8 9 10 11 12 13

public?function?PreOrderTraverse(){ $this->preTraverse($this->root); return?self::$preArr; } //還是遞歸調用,不對， private?function?preTraverse(){ if($root){ self::$preArr[]=$root->data; //這里可以把數(shù)據(jù)都存進去也可以做其他操作或者業(yè)務邏輯function() $this->preTraverse($root->lchild); $this->preTraverse($root->rchild); } }

中序遞歸實現(xiàn)如下

1 2 3 4 5 6 7 8 9 10 11 12

public?function?InOrderTraverse(){ $this->inTraverse($this->root); return?self::$inArr; } private?function?inTraverse(){ if($root){ $this->inTraverse($root->lchild); self::$inArr[]=$root->data; //這里可以把數(shù)據(jù)都存進去也可以做其他操作或者業(yè)務邏輯function() $this->inTraverse($root->rchild); } }

后續(xù)遞歸實現(xiàn)如下

1 2 3 4 5 6 7 8 9 10 11 12 13

public?function?PostOrderTraverse(){ ????????$this->postTraverse($this->root); ????????return?self::$postArr; ????} ????private?function?postTraverse(){ ????????if($root){ ????????????$this->postTraverse($root->lchild); ????????????self::$postArr[]=$root->data; ????????????//這里可以把數(shù)據(jù)都存進去也可以做其他操作或者業(yè)務邏輯function() ????????????? ????????????$this->postTraverse($root->rchild); ????????} ????}

層序遞歸實現(xiàn)如下

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

//我個人還是挺喜歡層序遍歷 ????public?function?LevelOrderTraverse(){ ????????for($i=1;$i<=$this->BiTreeDepth();$i++){ ????????????$this->LevelOrderTraverse($this->root,$i); ????????} ????????return?self::$levelArr; ????} ????private?function?leverTraverse($root,$level){ ????????if($root){ ????????????if($level==1){ ????????????????self::$levelArr[]=$root->data; ????????????} ????????????$this->LevelOrderTraverse($root->lchild,$level-1); ????????????$this->LevelOrderTraverse($root->rchild,$level-1); ????????} ????}

記錄一下。其實有時候在想，寫程序的同事，真的要做點其他的。但行好事，莫問前程

愿法界眾生，皆得安樂。

本文轉自 jackdongting 51CTO博客，原文鏈接:http://blog.51cto.com/10725691/1951446

總結

以上是生活随笔為你收集整理的php 二叉树 与赫夫曼树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。