哈工大数据结构大作业哈夫曼树生成编码遍历.docx
《哈工大数据结构大作业哈夫曼树生成编码遍历.docx》由会员分享，可在线阅读，更多相关《哈工大数据结构大作业哈夫曼树生成编码遍历.docx（14页珍藏版）》请在冰点文库上搜索。
一、问题描述
1.用户输入字母及其对应的权值，生成哈夫曼树；
2.通过最优编码的算法实现，生成字母对应的最优0、1编码；
3.先序、中序、后序遍历哈夫曼树，并打印其权值。
二、方法思路
1.哈夫曼树算法的实现
§存储结构定义
#definen100/*叶子树*/
#definem2*（n）–1/*结点总数*/
typedefstruct{/*结点型*/
doubleweight;/*权值*/
intlchild;/*左孩子链*/
intrchild;/*右孩子链*/
intparent;/*双亲链*/优点？
}HTNODE;
typedefHTNODEHuffmanT[m];
/*huffman树的静态三叉链表表示*/
算法要点
1）初始化：
将T[0]，…T[m-1]共2n-1个结点的三个链域均置空（-1）,权值为0；
2）输入权值：
读入n个叶子的权值存于T的前n个单元
T[0]，…T[n],它们是n个独立的根结点上的权值；
3）合并：
对森林中的二元树进行n-1次合并，所产生的新结点
依次存放在T[i]（n<=i<=m-1）。
每次合并分两步：
（1）在当前森林中的二元树T[0]，…T[i-1]所有结点中选取权值
最小和次最小的两个根结点T[p1]和T[p2]作为合并对象，这
里0<=p1，p2<=i–1;
（2）将根为T[p1]和T[p2]的两株二元树作为左、右子树合并为一
株新二元树，新二元树的根结点为T[i]。
即
T[p1].parent=T[p2].parent=i,T[i].lchild=p1,T[i].rchild=p2，T[i].weight=T[p1].weight+T[p2].weight。
2.用huffman算法求字符集最优编码的算法：
1）使字符集中的每个字符对应一株只有叶结点的二叉树，叶的权值为对应字符的使用频率；
2）利用huffman算法来构造一株huffman树；
3）对huffman树上的每个结点，左支附以0，右支附以1（或者相反），则从根到叶的路上的0、1序列就是相应字符的编码
Huffman编码实现：
存储结构
typedefstruct{
charch;//存储字符
charbits[n+1];//字符编码位串
}CodeNode;
typedefCodeNodeHuffmanCode[n];
HuffmanCodeH;
3.二叉树遍历的递归定义
先根顺序遍历二叉树：
若二叉树非空则：
{
访问根结点；
先根顺序遍历左子树；
先根顺序遍历右子树；
}
中根顺序遍历二叉树：
若二叉树非空则：
{
中根顺序遍历左子树；
访问根结点；
中根顺序遍历右子树；
}
后根顺序遍历二叉树：
若二叉树非空则：
{后根顺序遍历左子树；
后根顺序遍历右子树；
访问根结点；
}；
三、主要数据结构及源程序代码及其注释
1.扩充二叉树：
内结点、外结点
（增长树）
2.哈夫曼树
3.Huffman编码实现
源程序代码及注释
#include"stdafx.h"
#include
#include
#include
#definen10
#definem2*（n）-1
typedefstruct//建立哈夫曼结点结构体
{
chardata;
floatweight;
intlchild;
intrchild;
intparent;
}htnode;
typedefstruct//建立哈夫曼编码结构体
{
charch;
charbits[n+1];
}htcode;
voidSelectMin（htnodeT[m],intnn,int&p1,int&p2）//选择哈夫曼树所有结点中权值最小的两个根结点
{
inti,j;
for（i=0;i<=nn;i++）
{
if（T[i].parent==-1）
{
p1=i;
break;
}
}
for（j=i+1;j<=nn;j++）
{
if（T[j].parent==-1）
{
p2=j;
break;
}
}
for（i=0;i<=nn;i++）
{
if（（T[p1].weight>T[i].weight）&&（T[i].parent==-1）
&&（p2!
=i））
p1=i;
}
for（j=0;j<=nn;j++）
{
if（（T[p2].weight>T[j].weight）&&（T[j].parent==-1）
&&（p1!
=j））
p2=j;
}
}
voidCreatHT（htnodeT[m]）//建立哈夫曼树
{
inti,p1,p2;
for（i=0;i {
T[i].parent=T[i].lchild=T[i].rchild=-1;//赋初值
}
for（i=n;i {
SelectMin（T,i-1,p1,p2）;
T[p1].parent=T[p2].parent=i;
if（T[p1].weight T[i].lchild=p1;
T[i].rchild=p2;
}
else{
T[i].lchild=p2;
T[i].rchild=p1;
}
T[i].weight=T[p1].weight+T[p2].weight;
}
}
voidHuffmanEncoding（htnodeT[m],htcodeC[n]）//哈夫曼编码
{
intc,p,i;
charcd[n+1];
intstart;
cd[n]='\0';//结束表示
for（i=0;i {
C[i].ch=T[i].data;
start=n;
c=i;
while（（p=T[c].parent）>=0）
{
start=start-1;
if（T[p].lchild==c）
{
cd[start]='0';
}
else
{
cd[start]='1';
}
c=p;
}
strcpy（C[i].bits,&cd[start]）;
}
}
voidpreorder（htnodeT[],inti）//先序遍历哈夫曼树：
递归的办法
{
printf（"%f",T[i].weight）;
if（T[i].lchild!
=-1）
{
preorder（T,T[i].lchild）;
preorder（T,T[i].rchild）;
}
}
voidinorder（htnodeT[],inti）//中序遍历哈夫曼树
{
if（T[i].lchild!
=-1）
{
inorder（T,T[i].lchild）;
printf（"%f",T[i].weight）;
inorder（T,T[i].rchild）;
}
else{
printf（"%f",T[i].weight）;//防止左儿子为空，程序退出
}
}
voidpostorder（htnodeT[],inti）//后序遍历哈夫曼树
{
if（T[i].lchild!
=-1）
{
postorder（T,T[i].lchild）;
postorder（T,T[i].rchild）;
printf（"%f",T[i].weight）;
}
else{
printf（"%f",T[i].weight）;//防止左儿子为空，程序退出
}
}
voidmain（）
{
inti;
intj;
j=m-1;
htnodeT[m];
htcodeC[n];
htnode*b;
printf（"Input10elementsandweights:
"）;
for（i=0;i {
printf（"InputNO.%delement:
\n",i）;
scanf（"%c",&T[i].data）;
printf（"InputtheweightofNO.%delement:
\n",i）;
scanf（"%f",&T[i].weight）;
}
CreatHT（T）;//建立哈夫曼树
HuffmanEncoding（T,C）;//建立哈夫曼编码
printf（"OutputHuffmancoding:
\n"）;
for（i=0;i {
printf（"%c:
",C[i].ch）;
printf（"%s\n",C[i].bits）;
}
printf（"OutputHaffmanTressinpreorderway:
\n"）;
preorder（T,j）;//先序遍历哈夫曼树
printf（"\n"）;
printf（"OutputHaffmanTressininorderway:
\n"）;//中序遍历哈夫曼树
inorder（T,j）;
printf（"OutputHaffmanTressinpostorderway:
\n"）;//后序遍历哈夫曼树
postorder（T,j）;
while
（1）;//运行结果停止在当前画面
}
四、运行结果
#include"stdafx.h"
#include
#include
#include
#definen10
#definem2*（n）-1
typedefstruct//建立哈夫曼结点结构体
{
chardata;
floatweight;
intlchild;
intrchild;
intparent;
}htnode;
typedefstruct//建立哈夫曼编码结构体
{
charch;
charbits[n+1];
}htcode;
voidSelectMin（htnodeT[m],intnn,int&p1,int&p2）//选择哈夫曼树所有结点中权值最小的两个根结点
{
inti,j;
for（i=0;i<=nn;i++）
{
if（T[i].parent==-1）
{
p1=i;
break;
}
}
for（j=i+1;j<=nn;j++）
{
if（T[j].parent==-1）
{
p2=j;
break;
}
}
for（i=0;i<=nn;i++）
{
if（（T[p1].weight>T[i].weight）&&（T[i].parent==-1）
&&（p2!
=i））
p1=i;
}
for（j=0;j<=nn;j++）
{
if（（T[p2].weight>T[j].weight）&&（T[j].parent==-1）
&&（p1!
=j））
p2=j;
}
}
voidCreatHT（htnodeT[m]）//建立哈夫曼树
{
inti,p1,p2;
for（i=0;i {
T[i].parent=T[i].lchild=T[i].rchild=-1;//赋初值
}
for（i=n;i {
SelectMin（T,i-1,p1,p2）;
T[p1].parent=T[p2].parent=i;
if（T[p1].weight T[i].lchild=p1;
T[i].rchild=p2;
}
else{
T[i].lchild=p2;
T[i].rchild=p1;
}
T[i].weight=T[p1].weight+T[p2].weight;
}
}
voidHuffmanEncoding（htnodeT[m],htcodeC[n]）//哈夫曼编码
{
intc,p,i;
charcd[n+1];
intstart;
cd[n]='\0';//结束表示
for（i=0;i {
C[i].ch=T[i].data;
start=n;
c=i;
while（（p=T[c].parent）>=0）
{
start=start-1;
if（T[p].lchild==c）
{
cd[start]='0';
}
else
{
cd[start]='1';
}
c=p;
}
strcpy（C[i].bits,&cd[start]）;
}
}
voidpreorder（htnodeT[],inti）//先序遍历哈夫曼树：
递归的办法
{
printf（"%f",T[i].weight）;
if（T[i].lchild!
=-1）
{
preorder（T,T[i].lchild）;
preorder（T,T[i].rchild）;
}
}
voidinorder（htnodeT[],inti）//中序遍历哈夫曼树
{
if（T[i].lchild!
=-1）
{
inorder（T,T[i].lchild）;
printf（"%f",T[i].weight）;
inorder（T,T[i].rchild）;
}
else{
printf（"%f",T[i].weight）;//防止左儿子为空，程序退出
}
}
voidpostorder（htnodeT[],inti）//后序遍历哈夫曼树
{
if（T[i].lchild!
=-1）
{
postorder（T,T[i].lchild）;
postorder（T,T[i].rchild）;
printf（"%f",T[i].weight）;
}
else{
printf（"%f",T[i].weight）;//防止左儿子为空，程序退出
}
}
voidmain（）
{
inti;
intj;
j=m-1;
htnodeT[m];
htcodeC[n];
htnode*b;
printf（"Input10elementsandweights:
"）;
for（i=0;i {
printf（"InputNO.%delement:
\n",i）;
scanf（"%c",&T[i].data）;
printf（"InputtheweightofNO.%delement:
\n",i）;
scanf（"%f",&T[i].weight）;
}
CreatHT（T）;//建立哈夫曼树
HuffmanEncoding（T,C）;//建立哈夫曼编码
printf（"OutputHuffmancoding:
\n"）;
for（i=0;i {
printf（"%c:
",C[i].ch）;
printf（"%s\n",C[i].bits）;
}
printf（"OutputHaffmanTressinpreorderway:
\n"）;
preorder（T,j）;//先序遍历哈夫曼树
printf（"\n"）;
printf（"OutputHaffmanTressininorderway:
\n"）;//中序遍历哈夫曼树
inorder（T,j）;
printf（"OutputHaffmanTressinpostorderway:
\n"）;//后序遍历哈夫曼树
postorder（T,j）;
while
（1）;//运行结果停止在当前画面
}
升级会员 