php 二叉树与赫夫曼树

在学习图之前，中间休息了两天，感觉二叉树需要消化一下。所以中间去温习了下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); } 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;$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); } }

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

愿法界众生，皆得安乐。

php 二叉树 与赫夫曼树

PHP相关栏目本月热门文章

php 二叉树与赫夫曼树