哈工大数据结构大作业——哈夫曼树生成、编码、遍历.doc

一、 问题描述
1. 用户输入字母及其对应的权值，生成哈夫曼树；
2. 通过最优编码的算法实现，生成字母对应的最优0、1编码；
3. 先序、中序、后序遍历哈夫曼树，并打印其权值。

二、 方法思路
1.哈夫曼树算法的实现
§存储结构定义
#define n 100 /* 叶子树*/
#define m 2*(n) –1 /* 结点总数*/
typedef struct { /* 结点型*/
double weight ; /* 权值*/
int lchild ; /* 左孩子链*/
int rchild ; /* 右孩子链*/
int parent; /* 双亲链*/ 优点？
}HTNODE ;
typedef HTNODE HuffmanT[ 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编码实现：
存储结构
typedef struct{
char ch; //存储字符
char bits[n+1]; //字符编码位串
}CodeNode;
typedef CodeNode HuffmanCode[n];
HuffmanCode H;
3. 二叉树遍历的递归定义
先根顺序遍历二叉树：
若二叉树非空则：
{
访问根结点；
先根顺序遍历左子树；
先根顺序遍历右子树；
}
中根顺序遍历二叉树：
若二叉树非空则：
{
中根顺序遍历左子树；
访问根结点；
中根顺序遍历右子树；
}
后根顺序遍历二叉树：
若二叉树非空则：
{ 后根顺序遍历左子树；
后根顺序遍历右子树；
访问根结点；
} ；
三、主要数据结构及源程序代码及其注释
1.扩充二叉树：内结点、外结点
（增长树）

2. 哈夫曼树

3. Huffman编码实现

源程序代码及注释
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include<stdlib.h>
#define n 10
#define m 2*(n)-1
typedef struct//建立哈夫曼结点结构体
{
char data;
float weight;
int lchild;
int rchild;
int parent;
}htnode;
typedef struct//建立哈夫曼编码结构体
{
char ch;
char bits[n+1];
}htcode;
void SelectMin(htnode T[m],int nn,int&p1,int&p2)//选择哈夫曼树所有结点中权值最小的两个根结点
{
int i,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;
}
}
void CreatHT(htnode T[m])//建立哈夫曼树
{
int i,p1,p2;
for(i=0;i<m;i++)
{
T[i].parent=T[i].lchild=T[i].rchild=-1;//赋初值
}
for(i=n;i<m;i++)
{
SelectMin(T,i-1,p1,p2);
T[p1].parent=T[p2].parent=i;
if(T[p1].weight<T[p2].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;
}
}
void HuffmanEncoding(htnode T[m],htcode C[n])//哈夫曼编码
{
int c,p,i;
char cd[n+1];
int start;
cd[n]='\0';//结束表示
for(i=0;i<n;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]);
}
}

void preorder(htnode T[],int i)//先序遍历哈夫曼树：递归的办法
{
printf("%f",T[i].weight);
if(T[i].lchild!=-1)
{

preorder(T,T[i].lchild);
preorder(T,T[i].rchild);
}
}

void inorder(htnode T[],int i)//中序遍历哈夫曼树
{
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);//防止左儿子为空，程序退出
}
}
void postorder(htnode T[],int i)//后序遍历哈夫曼树
{
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);//防止左儿子为空，程序退出
}
}
void main()
{
int i;
int j;
j=m-1;
htnode T[m];
htcode C[n];
htnode *b;
printf("Input 10 elements and weights:");
for (i=0;i<n;i++)//用户输入字母及对应的权值
{
printf("Input NO.%d element:\n",i);
scanf(" %c",&T[i].data);
printf("Input the weight of NO.%d element:\n",i);
scanf(" %f",&T[i].weight);
}
CreatHT(T);//建立哈夫曼树
HuffmanEncoding(T,C);//建立哈夫曼编码
printf("Output Huffman coding:\n");
for (i=0;i<n;i++)
{
printf("%c:",C[i].ch);
printf("%s\n",C[i].bits);
}

printf("Output Haffman Tress in preorder way:\n");
preorder(T,j);//先序遍历哈夫曼树
printf("\n");
printf("Output Haffman Tress in inorder way:\n");//中序遍历哈夫曼树
inorder(T,j);
printf("Output Haffman Tress in postorder way:\n");//后序遍历哈夫曼树
postorder(T,j);

while(1);//运行结果停止在当前画面

}
四、运行结果

#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include<stdlib.h>
#define n 10
#define m 2*(n)-1
typedef struct//建立哈夫曼结点结构体
{
char data;
float weight;
int lchild;
int rchild;
int parent;
}htnode;
typedef struct//建立哈夫曼编码结构体
{
char ch;
char bits[n+1];
}htcode;
void SelectMin(htnode T[m],int nn,int&p1,int&p2)//选择哈夫曼树所有结点中权值最小的两个根结点
{
int i,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;
}
}
void CreatHT(htnode T[m])//建立哈夫曼树
{
int i,p1,p2;
for(i=0;i<m;i++)
{
T[i].parent=T[i].lchild=T[i].rchild=-1;//赋初值
}
for(i=n;i<m;i++)
{
SelectMin(T,i-1,p1,p2);
T[p1].parent=T[p2].parent=i;
if(T[p1].weight<T[p2].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;
}
}
void HuffmanEncoding(htnode T[m],htcode C[n])//哈夫曼编码
{
int c,p,i;
char cd[n+1];
int start;
cd[n]='\0';//结束表示
for(i=0;i<n;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]);
}
}

void preorder(htnode T[],int i)//先序遍历哈夫曼树：递归的办法
{
printf("%f",T[i].weight);
if(T[i].lchild!=-1)
{

preorder(T,T[i].lchild);
preorder(T,T[i].rchild);
}
}

void inorder(htnode T[],int i)//中序遍历哈夫曼树
{
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);//防止左儿子为空，程序退出
}
}
void postorder(htnode T[],int i)//后序遍历哈夫曼树
{
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);//防止左儿子为空，程序退出
}
}
void main()
{
int i;
int j;
j=m-1;
htnode T[m];
htcode C[n];
htnode *b;
printf("Input 10 elements and weights:");
for (i=0;i<n;i++)//用户输入字母及对应的权值
{
printf("Input NO.%d element:\n",i);
scanf(" %c",&T[i].data);
printf("Input the weight of NO.%d element:\n",i);
scanf(" %f",&T[i].weight);
}
CreatHT(T);//建立哈夫曼树
HuffmanEncoding(T,C);//建立哈夫曼编码
printf("Output Huffman coding:\n");
for (i=0;i<n;i++)
{
printf("%c:",C[i].ch);
printf("%s\n",C[i].bits);
}

printf("Output Haffman Tress in preorder way:\n");
preorder(T,j);//先序遍历哈夫曼树
printf("\n");
printf("Output Haffman Tress in inorder way:\n");//中序遍历哈夫曼树
inorder(T,j);
printf("Output Haffman Tress in postorder way:\n");//后序遍历哈夫曼树
postorder(T,j);

while(1);//运行结果停止在当前画面

}