一种可视化哈夫曼树的方法
第6期 孙学琛,等:哈夫曼树的图形化算法设计
109
其存储结构及编码工作空间如图1所示.
weight12336
lchild00013
rchild00024
parent4455
Pointp; //存放每个结点相应的绘图坐标}HTnode,*HuffmanTree;Point结构的定义为:typedefstruct{
doublex; //横坐标
doubley; //纵坐标
}Point;
哈夫曼树的图形化算法基本步骤如下:1)将哈夫曼树的结点映射到完全二叉树上,为每个结点编号存入id域中,即根节点为1,其左子树为2,右子树为3,依次向下直到叶子结点.
2)对每个叶子结点,用公式id=
2
算id域的值,这样会将id的数值映射为[1,2)之间,显然对于每个叶子结点其id值是不同的,若想让结点不重合,就需要确定结点自左向右出现的次序(即结点在遍历时叶子结点出现的相对次序),每个叶子结点的id的大小就决定了它出现的顺序.
3)根据步骤2中计算的id值从小到大为每个结点的p.x域赋值,即根据叶子结点在横坐标上出现的次序为其分配横坐标的坐标值.
4)根据叶子结点的横坐标确定其双亲结点的横坐标.
5)根据 log2id 的值确定结点所在的层次,继而确定结点的纵坐标,这里叶子结点的值已经改变,故不能用上述方法确定,只需在其双亲结点的纵坐标上加上偏移h即可.
6)画结点、连线、标注符号和权值.
7)对应于以上步骤,以下是哈夫曼树的图形化算法的具体实现(C语言描述):
HuffmanDrawing(HuffmanTree&HT,intn){//step1
HT[2*n-1].id=1;
for(i=2*n-1;i>n;i--){
HT[HT[i].lchild].id=2*HT[i].id;HT[HT[i].rchild].id=2*HT[i].id+1;}
//step2
for(i=n;i>0;i--)
HT[i].id=HT[i].id/
pow(2,log(HT[i].id)/log(2));
//step3
for(i=1;i<n+1;i++){
,;
图1 传统哈夫曼编码的编码空间

对给定的权值,进行哈夫曼编码是一件非常容易的事情,我们关心的是是否可以在进行哈夫曼编码的同时画出哈夫曼树,以便于更直观的观察其性征.哈夫曼树的树形结构决定了它并不能像线性表那样直观的表达.在最坏情况下,一棵n阶的哈夫曼树要有2n-1个结点,而仅最下面一层就会有2n-1个结点,简单的自顶而下的绘图方式是最容易想到的,但如果简单用自顶向下的方式而不加任何差错控制绘图的话,结点和路径很有可能会交叉重合.在实际应用中,虽然上述情况是极少出现的,但是有些情况下即使结点总数很少,交叉重合有时也是不可避免的,一些常见的交叉重合情况如图2所示.
log2id
计
(a)理想情况 (b)自顶向下,结点重合 (c)自底向上,路径交叉
图2 不同方法画哈夫曼树的一些交叉重合的情况
2 问题的解决
我们提出的这种算法是建立在传统哈夫曼编码算法的基础上,利用其编码后工作空间中的结果进行绘制哈夫曼树,其根本思想是:自底而上,从叶子结点画起,向上推出上一层结点的位置,直到根结点.为此对哈夫曼树的存储结构做一些改进,改进后的存储结构如图3所示,C语言描述如下(粗体表示对数据域的改进):
weight
lchild
rchild
parent
id
p
图3 改进后的哈夫曼树的存储结构
typedefstruct{
unsignedintweight;
unsignedintparent,lchild,rchild;//以下为新增数据域
doubleid; //存放对应完全二叉树的序
2008 文章编号 :1672 - 6197 ( 2008) 06 - 0108 - 03 哈夫曼树的图形化算法设计孙学琛 , 李新洁 ( 山东理工大学 理学院 , 山东 淄博 255049 ) 摘 要 ...
哈弗曼编码,C实现二叉树的图形化输出,已经界面_IT/...( 报告 题目:哈夫曼编码 译码器 题目:哈夫曼编码/...算法设计前面已经提到,这个程序我基本上全都做了,...
哈夫曼树的结构算法 12 利用哈夫曼编码进行信息通讯...实现提示: 1、用户界面可以设计为“菜单”方式:显示...*初始化函数,输入 n 个字符及其对应的权值,根据...
图形化输出哈夫曼树、哈夫曼编码 压缩、解压和比较 压缩、解压和比较 本人负责压缩...哈夫曼树。 算法设计: 算法设计: 之前其他组员已经完成了哈夫曼树的构建和哈...
计算机应用技术系课程设计报告书 数据结构与算法 课程设计报告书 题目: 班级: ...{ 初始化; 构造哈夫曼树; 求哈夫曼编码; 哈夫曼编码输出; } (2)哈夫曼...
数据结构课程设计模——哈夫曼编码译码器_IT/计算机_...打印哈夫曼树 初始化算法: 2.3.1 初始化算法: ...打印出来的图形与 教科书上的常见哈夫曼树略有不同...
(2)设计包含的几个方面:① 哈夫曼树的建立 哈夫曼树的建立由哈夫曼算法的...//初始化 int //初始化 HTNode ht[M]; HCode hcd[N]; for (i=0;i<...
组 计算机算法设计与分析 课 教师评定 学号 2007102×× 姓名 121 实验日期 哈夫曼编码问题 1、 、 实验目的: 实验目的:根据最优二叉树构造哈夫曼编码 利用哈...
程序核心代码及主要设计 1.哈夫曼树节点的数据类型定义: 代码: typedef struct ...及图形界面 10 11 12 6.实验总结(实验结果分析、实验心得体会) 1、算法结果...
1BF 李煌峰 实验结 果 一、实验目的 1、根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; 2、编程实现哈夫曼编译码器; 3、掌握贪心算法的一般设计方法。 ...
热门文档