PHP实现 Huffman 树 + simpleTest进行单元测试
最近工作不是很忙，又翻开大学的数据结构突然发现以前写过很多遍的算法已经变的只知道是怎么回事，而淡忘了它的实现，挺亏对以前教我们的"小妈妈"老师(当时她临产还坚持给我们上数据结构呵呵，我们给她的爱称)，看了下
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
页:
[1]