php 二叉树 与赫夫曼树

cheun

　　在学习图之前，中间休息了两天，感觉二叉树需要消化一下。所以中间去温习了下sql，推荐一本工具书《程序员的SQL金典》看名字不像一本好书，但是作为一个不错的SQL工具书还是可以小小备忘一下。涵盖内容不详细但是挺广，覆盖多种主流数据库
　　

　　言归正传，以前知道折半查找，二叉树的概念也是感觉挺有意思，二叉树的实现有一个案例很不错，代码如下
class BiNode{
public $data;
public $lchild;
public $rchild;
public function __construct($data){
$this->data = $data;//节点数据
$this->lchild = null;//左子节点指针
$this->rchild = null;//右指针
}
}
class LinkBiTree{
private $root; //根节点
        private static $count;//结点总数
const MAX_LEVEL = 2;
public function __construct(){
$this->root = null;
self::$count = 0;
}
public function ClearBiTree(){
$this->clearTree($this->root);
}
/**
*@param $root 树的根节点
*
*/
public function clearTree($root){
if($root){
if($root->lchild){
$this->clearTree($root->lchild);
}
if($root->rchild){
$this->clearTree($root->rchild);
}
unset($root);
$root=null;
}
}
}　　其实我更加感兴趣的就是赫夫曼树，能够给我带来感觉得才让我激动，就是100以内猜七次肯定可以猜出来，这种感觉是很奇妙的，当年赫夫曼为了传输点卯，更改了数据的排列顺序，形成了新的储存序列和标识，是的竟成使用的字母快速找出来，节省了资源，很棒。
　　

赫尔曼构造算法的实现
初始化HT
输入初始n个叶子结点：置HT[1…n]的weight值
　　然后根据权值来重新安排叶子结点，可以先序可以中序可以后续也可以中序，只要距离根节点的搜索顺序在前面就好

• 　　先序递归实现如下
  　　
  
  
• public function PreOrderTraverse(){
  $this->preTraverse($this->root);
  return self::$preArr;
  }
  //还是递归调用,不对，
  private function preTraverse(){
  if($root){
  self::$preArr[]=$root->data;
  //这里可以把数据都存进去也可以做其他操作或者业务逻辑function()
  $this->preTraverse($root->lchild);
  $this->preTraverse($root->rchild);
  }
  }
  
• 　　中序递归实现如下
  
• public function InOrderTraverse(){
  $this->inTraverse($this->root);
  return self::$inArr;
  }
  private function inTraverse(){
  if($root){
  $this->inTraverse($root->lchild);
  self::$inArr[]=$root->data;
  //这里可以把数据都存进去也可以做其他操作或者业务逻辑function()
  $this->inTraverse($root->rchild);
  }
  }
  
• 　　后续递归实现如下
  
• public function PostOrderTraverse(){
  $this->postTraverse($this->root);
  return self::$postArr;
  }
  private function postTraverse(){
  if($root){
  $this->postTraverse($root->lchild);
  self::$postArr[]=$root->data;
  //这里可以把数据都存进去也可以做其他操作或者业务逻辑function()
  $this->postTraverse($root->rchild);
  }
  }
  
• 　　层序递归实现如下
  
• //我个人还是挺喜欢层序遍历
  public function LevelOrderTraverse(){
  for($i=1;$iBiTreeDepth();$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);
  }
  }
  

　　记录一下。其实有时候在想，写程序的同事，真的要做点其他的。但行好事，莫问前程
　　

　　愿法界众生，皆得安乐。