最近工作不是很忙,又翻开大学的数据结构突然发现以前写过很多遍的算法已经变的只知道是怎么回事,而淡忘了
它的实现,挺亏对以前教我们的"小妈妈"老师(当时她临产还坚持给我们上数据结构呵呵,我们给她的爱称),看了下
Huffman Binary Tree 的实现,在网络上找到关于PHP实现的资料也很少,因此尝试自己写写,居然写出来了
希望有高人看到 有错的地方指点一二
<?php
/*
* @Created on 2009-9-2
* @Author : xujf
* @Subject: Huffman Tree
*
* To change the template for this generated file go to
* Window - Preferences - PHPeclipse - PHP - Code Templates
*/
class BinaryTree
{
public function authSrcTreeType($srcTree)
{
if(gettype($srcTree) == 'Array'
|| gettype($srcTree) == 'array')
{
return true;
}
return false;
}
/**
* 判断数据长度
*/
public function checkSrcTreeCount($srcTree)
{
if(count($srcTree)>0)
{
return true;
}
return false;
}
/**
* 对原始数据进行排序
* @ type = Asc '<' || Desc '>'
*
*/
public function _sortAscSrcData($src, $type='')
{
for($i = 1; $i<count($src); $i++)
{
$tmp = $src[$i];
$j = $i - 1;
while($src[$j] > $tmp)
{
$src[$j+1] = $src[$j];
$src[$j] = $tmp;
$j--;
}
}
return $src;
}
/**
* 生成BinaryTree And IndexList
*/
public function createBinaryTreeIndex($srcTree)
{
$index = '';
$key = count($srcTree);
for($i=1; $i<count($srcTree)+1; $i++)
{
if($srcTree[$i])
{
if(!$index)
{
$state = 'INIT';
$left_node = $srcTree[$i];
$right_node = $srcTree[$i-1];
}
else
{
$state = 'Line';
if($srcTree[$key+1])
{
$key+=1;
}
$left_node = $srcTree[$key];
$right_node = $srcTree[$i];
}
$index = $right_node+$left_node;
$this->indexList[] = $index;
$this->tree[$index] = $this->_sortAscSrcData(
array($right_node, $left_node)
);
$this->root = $index;
unset($srcTree[$i]);
if($state == 'INIT')
{
unset($srcTree[$i-1]);
}
$srcTree[] = $right_node+$left_node;
}
}
}
/**
* 生成Huffman Tree
*/
public function showBinaryTree($treeData, $root='')
{
if(!$root)
{
echo '<br> ' . $this->root .'<br>';
echo ' '.$this->node.' \\<br>';
$root = $this->root;
}
else
{
echo '<br> '.$this->node.' \\<br>';
}
$num = 1;
foreach($treeData[$root] as $v)
{
echo ' ' .$v . ' ';
if($treeData[$v])
{
self::showBinaryTree($treeData, $v);
}
}
}
public $indexList = array(); //用来存放Huffman Tree 索引
public $srcTree;
protected $node = '/';
protected $root;
protected $node_ID = 1;
public $tree = array();
}
?>
单元测试脚本 :
<?php
/*
* Created on 2009-9-3
*
* To change the template for this generated file go to
* Window - Preferences - PHPeclipse - PHP - Code Templates
*/
//require_once('./simpletest/autorun.php');
require_once('./simpletest/reporter.php');
require_once('./simpletest/unit_tester.php');
require_once('binaryTree.php');
class TestBinaryTree extends UnitTestCase
{
public function TestBinaryTree()
{
$this->UnitTestCase('Test - BinaryTree');
}
/**
* 判断SrcTree必须是类型
*/
public function TestCheckSrcTreeIsArray()
{
//SrcTree 是Array 的情况下返回True
$bt = new BinaryTree();
$this->assertTrue($bt->authSrcTreeType($this->srcTree),'True');
//SrcTree 是String 的情况下返回String
$srcTreeString = 'My`s String';
$bt = new BinaryTree();
$this->assertFalse($bt->authSrcTreeType($srcTreeString),'False');
}
/**
* 判断SrcTree长度
*/
public function TestCheckSrcTreeCount()
{
// 判断SrcTree长度不为 0
$bt = new BinaryTree();
$this->assertTrue($bt->checkSrcTreeCount($this->srcTree), 'true');
}
/**
* 判断排序正确
*/
public function TestHuffmanTreeSort()
{
$bt = new BinaryTree($this->srcTree);
$resTree = $bt->_sortAscSrcData($this->srcTree);
$this->assertEqual($resTree, $this->nowTree);
}
/**
* 判断BinaryTree IndexList Equal
*/
public function TestBinaryTreeIndexList()
{
$bt = new BinaryTree();
if($state = $bt->authSrcTreeType($this->srcTree))
{
$state = $bt->checkSrcTreeCount($this->srcTree);
}
if($state)
{
//排序
$srcTree = $bt->_sortAscSrcData($this->srcTree);
//判断是否已经被排序
$this->assertEqual($srcTree, $this->nowTree);
//生成索引
$bt->createBinaryTreeIndex($srcTree);
// 判断索引列表
$this->assertEqual($bt->indexList, $this->nowindexList);
//判断获得的树列
$this->assertEqual($bt->tree, $this->nTree);
//显示BinaryTreeList
//$bt->showBinaryTree($bt->tree);
}
}
/**
* 判断获取正确的哈夫曼树的根
*/
public function TestHuffmanTreeRootNUM()
{
}
protected $srcTree = array(33, 3, 5 ,7, 9, 11);
protected $nowTree = array(3, 5, 7, 9, 11, 33);
protected $nowindexList = array(8, 15, 24, 35, 68);
protected $nTree = array(
'8' => array(3, 5),
'15'=> array(7, 8),
'24'=> array(9, 15),
'35'=> array(11, 24),
'68'=> array(33, 35),
);
}
$tbt = new TestBinaryTree();
$tbt->run(new HtmlReporter());
?>
显示结果
68
/ \
33 35
/ \
11 24
/ \
9 15
/ \
7 8
/ \
3 5
分享到:
相关推荐
非常适合大学数据结构课上使用。强烈推荐!~
C语言简单实现Huffman树
自己实现huffman树的代码,分享出来
用C++语言实现huffman树的源代码
哈弗曼树实现 Huffman实现 哈夫曼实现 c++实现 使用方法 getCode:一个map, int> 的对象,该对象表示对ascii文件的统计数据,一个map, pair, int> > 的对象,该对象是编码后各个字符的对应的编码以及该编码的长度 ...
Huffman编码+图第一次作业答案.ppt
用MFC实现huffman树的建立 用socket传输
huffman树以及Huffman编码huffman树以及Huffman编码 huffman树以及Huffman编码 huffman树以及Huffman编码
自写的Huffman算法,和其他不一样,希望有帮助
1、了解该树的应用实例,熟悉掌握 Huffman 树的构造方法及 Huffman 编码的应用, 2、了解 Huffman 树在通信、编码领域的应用过程 1、输入
Huffman树 及 Huffman编码 演示程序 以画图的方法形象的表示了树的构成,解决了普通控制台应用程序对树的结构表达不清的问题 编译器 VS2008
1.领域:matlab,huffman+卷积联合编译码算法 2.内容:数字通信matlab仿真,调制ASK和PSK,编译码为huffman+卷积联合编码,译码为huffman+viterbi联合译码 3.用处:用于huffman+卷积联合编译码算法编程学习 4.指向...
C语言实现的Huffman树和Huffman编码生成的程序
huffman编码 c语言实现过程 c语言
利用Huffman树实现对文件的无损压缩与解压,并且对Huffman树的创建也做了详细的说明与讲解,C语言实现的.....值得一看....
哈夫曼树C++构建代码,利用构建最小堆的方法
linux c下的huffmantree,自己写的,有用到的可以去看看。
用C写的一个简单的huffman树实现数据文件压缩
Huffman编码树通过MATLAB实现