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

1、一、 问题描述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 Huff

2、manT m ;/* huffman树的静态三叉链表表示*/ 算法要点1)初始化：将T0，Tm-1共2n-1个结点的三个链域均置空( -1 ),权值为0；2)输入权值：读入n 个叶子的权值存于T的前n 个单元T0，Tn, 它们是n 个独立的根结点上的权值；3)合并：对森林中的二元树进行n-1次合并，所产生的新结点依次存放在Ti(n=i=m-1)。每次合并分两步：(1) 在当前森林中的二元树T 0，Ti-1所有结点中选取权值最小和次最小的两个根结点Tp1和Tp2作为合并对象，这里0= p1，p2= i 1;(2) 将根为Tp1和Tp2的两株二元树作为左、右子树合并为一株新二元树，新二元树的根结点

3、为Ti。即Tp1.parent =Tp2.parent = i ,Ti.lchild= p1, Ti.rchild=p2， Ti.weight =Tp1.weight + Tp2.weight。 2. 用huffman算法求字符集最优编码的算法：1) 使字符集中的每个字符对应一株只有叶结点的二叉树，叶的权值为对应字符的使用频率；2) 利用huffman算法来构造一株huffman树；3) 对huffman树上的每个结点，左支附以0，右支附以1（或者相反），则从根到叶的路上的0、1序列就是相应字符的编码 Huffman编码实现： 存储结构typedef structchar ch; /存储字符c

4、har bitsn+1; /字符编码位串CodeNode;typedef CodeNode HuffmanCoden;HuffmanCode H; 3. 二叉树遍历的递归定义先根顺序遍历二叉树：若二叉树非空则： 访问根结点；先根顺序遍历左子树；先根顺序遍历右子树； 中根顺序遍历二叉树：若二叉树非空则： 中根顺序遍历左子树； 访问根结点； 中根顺序遍历右子树； 后根顺序遍历二叉树： 若二叉树非空则： 后根顺序遍历左子树； 后根顺序遍历右子树； 访问根结点； ；三、主要数据结构及源程序代码及其注释1.扩充二叉树：内结点、外结点（增长树）2. 哈夫曼树3. Huffman编码实现源程序代码及注释#i

5、nclude stdafx.h#include #include #include#define n 10#define m 2*(n)-1typedef struct/建立哈夫曼结点结构体 char data; float weight; int lchild; int rchild; int parent;htnode;typedef struct/建立哈夫曼编码结构体 char ch; char bitsn+1;htcode;void SelectMin(htnode Tm,int nn,int&p1,int&p2)/选择哈夫曼树所有结点中权值最小的两个根结点 int i,j; for(

6、i=0;i=nn;i+) if(Ti.parent=-1) p1=i; break; for(j=i+1;j=nn;j+) if(Tj.parent=-1) p2=j; break; for(i=0;iTi.weight)&(Ti.parent=-1) &(p2!=i) p1=i; for(j=0;jTj.weight)&(Tj.parent=-1) &(p1!=j) p2=j; void CreatHT(htnode Tm)/建立哈夫曼树 int i,p1,p2; for(i=0;im;i+) Ti.parent=Ti.lchild=Ti.rchild=-1;/赋初值 for(i=n;im;

7、i+) SelectMin(T,i-1,p1,p2); Tp1.parent=Tp2.parent=i; if(Tp1.weightTp2.weight) Ti.lchild=p1; Ti.rchild=p2; else Ti.lchild=p2; Ti.rchild=p1; Ti.weight=Tp1.weight+Tp2.weight;void HuffmanEncoding(htnode Tm,htcode Cn)/哈夫曼编码 int c,p,i; char cdn+1; int start; cdn=0;/结束表示 for(i=0;i=0) start=start-1; if(Tp.l

8、child=c) cdstart=0; else cdstart=1; c=p; strcpy(Ci.bits,&cdstart);void preorder(htnode T,int i)/先序遍历哈夫曼树：递归的办法 printf(%f,Ti.weight);if(Ti.lchild!=-1) preorder(T,Ti.lchild); preorder(T,Ti.rchild); void inorder(htnode T,int i)/中序遍历哈夫曼树 if(Ti.lchild!=-1) inorder(T,Ti.lchild); printf(%f,Ti.weight); inor

9、der(T,Ti.rchild); else printf(%f,Ti.weight);/防止左儿子为空，程序退出void postorder(htnode T,int i)/后序遍历哈夫曼树 if(Ti.lchild!=-1) postorder(T,Ti.lchild); postorder(T,Ti.rchild); printf(%f,Ti.weight); else printf(%f,Ti.weight);/防止左儿子为空，程序退出 void main()int i;int j;j=m-1;htnode Tm;htcode Cn;htnode *b;printf(Input 10

10、elements and weights:);for (i=0;in;i+)/用户输入字母及对应的权值 printf(Input NO.%d element:n,i); scanf( %c,&Ti.data); printf(Input the weight of NO.%d element:n,i); scanf( %f,&Ti.weight);CreatHT(T);/建立哈夫曼树HuffmanEncoding(T,C);/建立哈夫曼编码printf(Output Huffman coding:n);for (i=0;in;i+)printf(%c:,Ci.ch);printf(%sn,Ci

11、.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 #include #include

12、#define n 10#define m 2*(n)-1typedef struct/建立哈夫曼结点结构体 char data; float weight; int lchild; int rchild; int parent;htnode;typedef struct/建立哈夫曼编码结构体 char ch; char bitsn+1;htcode;void SelectMin(htnode Tm,int nn,int&p1,int&p2)/选择哈夫曼树所有结点中权值最小的两个根结点 int i,j; for(i=0;i=nn;i+) if(Ti.parent=-1) p1=i; break

13、; for(j=i+1;j=nn;j+) if(Tj.parent=-1) p2=j; break; for(i=0;iTi.weight)&(Ti.parent=-1) &(p2!=i) p1=i; for(j=0;jTj.weight)&(Tj.parent=-1) &(p1!=j) p2=j; void CreatHT(htnode Tm)/建立哈夫曼树 int i,p1,p2; for(i=0;im;i+) Ti.parent=Ti.lchild=Ti.rchild=-1;/赋初值 for(i=n;im;i+) SelectMin(T,i-1,p1,p2); Tp1.parent=Tp

14、2.parent=i; if(Tp1.weightTp2.weight) Ti.lchild=p1; Ti.rchild=p2; else Ti.lchild=p2; Ti.rchild=p1; Ti.weight=Tp1.weight+Tp2.weight;void HuffmanEncoding(htnode Tm,htcode Cn)/哈夫曼编码 int c,p,i; char cdn+1; int start; cdn=0;/结束表示 for(i=0;i=0) start=start-1; if(Tp.lchild=c) cdstart=0; else cdstart=1; c=p;

15、strcpy(Ci.bits,&cdstart);void preorder(htnode T,int i)/先序遍历哈夫曼树：递归的办法 printf(%f,Ti.weight);if(Ti.lchild!=-1) preorder(T,Ti.lchild); preorder(T,Ti.rchild); void inorder(htnode T,int i)/中序遍历哈夫曼树 if(Ti.lchild!=-1) inorder(T,Ti.lchild); printf(%f,Ti.weight); inorder(T,Ti.rchild); else printf(%f,Ti.weigh

16、t);/防止左儿子为空，程序退出void postorder(htnode T,int i)/后序遍历哈夫曼树 if(Ti.lchild!=-1) postorder(T,Ti.lchild); postorder(T,Ti.rchild); printf(%f,Ti.weight); else printf(%f,Ti.weight);/防止左儿子为空，程序退出 void main()int i;int j;j=m-1;htnode Tm;htcode Cn;htnode *b;printf(Input 10 elements and weights:);for (i=0;in;i+)/用户

17、输入字母及对应的权值 printf(Input NO.%d element:n,i); scanf( %c,&Ti.data); printf(Input the weight of NO.%d element:n,i); scanf( %f,&Ti.weight);CreatHT(T);/建立哈夫曼树HuffmanEncoding(T,C);/建立哈夫曼编码printf(Output Huffman coding:n);for (i=0;in;i+)printf(%c:,Ci.ch);printf(%sn,Ci.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);/运行结果停止在当前画面