php 二叉樹 與赫夫曼樹

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

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

class BiNode{
	public $data;
	public $lchild;
	public $rchild;
	public function __construct($data){
			$this->data = $data;//節(jié)點(diǎn)數(shù)據(jù)
			$this->lchild = null;//左子節(jié)點(diǎn)指針
			$this->rchild = null;//右指針
	}
}
class LinkBiTree{
	private $root; //根節(jié)點(diǎn)
        private static $count;	//結(jié)點(diǎn)總數(shù)
	const MAX_LEVEL = 2;
	
	public function __construct(){
		$this->root = null;
		self::$count = 0;	
	}

	public function ClearBiTree(){
		$this->clearTree($this->root);
	}

	/**
	*@param $root 樹的根節(jié)點(diǎn)
	*
	*/

	public function clearTree($root){
		if($root){
			if($root->lchild){
				$this->clearTree($root->lchild);
			}
			if($root->rchild){
				$this->clearTree($root->rchild);
			}
			unset($root);
			$root=null;
		}
	}
	
	
}	

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

赫爾曼構(gòu)造算法的實(shí)現(xiàn)

初始化HT

輸入初始n個葉子結(jié)點(diǎn)：置HT[1…n]的weight值

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

1. 先序遞歸實(shí)現(xiàn)如下

   
   

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

3. 中序遞歸實(shí)現(xiàn)如下

4. 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ù)都存進(jìn)去也可以做其他操作或者業(yè)務(wù)邏輯function()
   $this->inTraverse($root->rchild);
   }
   }

5. 后續(xù)遞歸實(shí)現(xiàn)如下

6. 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ù)都存進(jìn)去也可以做其他操作或者業(yè)務(wù)邏輯function()
   			
   			$this->postTraverse($root->rchild);
   		}
   	}

7. 層序遞歸實(shí)現(xiàn)如下

8. //我個人還是挺喜歡層序遍歷
   	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);
   		}
   	}

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

愿法界眾生，皆得安樂。