文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 哈夫曼树的图形化算法设计
侵权投诉

哈夫曼树的图形化算法设计

一种可视化哈夫曼树的方法

第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; //存放对应完全二叉树的序

上一页第2页

你可能喜欢

热门文档

相关文档

  • 哈夫曼树图形化算法

    2008 文章编号 :1672 - 6197 ( 2008) 06 - 0108 - 03 哈夫曼树的图形化算法设计孙学琛 , 李新洁 ( 山东理工大学 理学院 , 山东 淄博 255049 ) 摘 要 ...

  • 哈弗曼编码,C实现二叉树的图形化输出,已经界面

    哈弗曼编码,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、掌握贪心算法的一般设计方法。 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email