《数据结构课设哈夫曼二叉树》由会员分享，可在线阅读，更多相关《数据结构课设哈夫曼二叉树（6页珍藏版）》请在金锄头文库上搜索。
1、hufmantree.h/构造哈夫曼树并获得哈夫曼编码#include #include #include #include template struct TriNode /二叉树的三叉静态链表结点 T data; /数据域 int parent,left,right; /父母结点和左、右孩子结点下标;class HuffmanTree /哈夫曼树类private: int leafNum; /叶子结点个数 TriNode *huftree; /哈夫曼树的结点数组 char *hufcodes; /哈夫曼编码数组public: HuffmanTree(int weight, int n);
2、/构造指定权值集合的哈夫曼树 HuffmanTree();int deep(int i); void print(char table,char string);void printk(int i,char table); / 凹入输出private: void createHuffmanTree(int weight, int n); /创建指定权值集合的哈夫曼树 void getHuffmanCode(); /获得哈夫曼编码 ;void HuffmanTree:printk(int i,char table)if(i-1) printk(huftreei.left,table);for(i
3、nt j=0;j=deep(i);j+)cout ;couthuftreei.data;if(i=leafNum-1)couttablei;coutendl;printk(huftreei.right,table); /-凹入表示const Max_Weight=9999; /默认最大权值HuffmanTree:HuffmanTree(int weight, int n) /构造指定权值集合的哈夫曼树 /n个叶子结点 createHuffmanTree(weight, n); getHuffmanCode();void HuffmanTree:createHuffmanTree(int wei
4、ght, int n) /创建指定权值集合的哈夫曼树 leafNum = n; huftree = new TriNode2*n-1; /n个叶子结点的哈夫曼树共有2n-1个结点 int i; for (i=0; in; i+) /结点数组初始化有n个叶子结点 huftreei.data = weighti; huftreei.parent = huftreei.left = huftreei.right = -1; for (i=0; in-1; i+) /构造n-1个2度结点，每循环一次，构造一个2度结点 int min1, min2, x1, x2; min1 = min2 = Max_
5、Weight; /选择最小和次最小权值，初值为最大权值 x1 = x2 = -1; /记录两个无父母的最小权值结点下标 for (int j=0; jn+i; j+) /查找两个无父母的最小权值结点 if (huftreej.datamin1 & huftreej.parent=-1) min2 = min1; x2 = x1; min1 = huftreej.data; /min1记下最小权值 x1 = j; /x1记下最小权值结点的下标 else if (huftreej.datamin2 & huftreej.parent=-1)min2 = huftreej.data; /min2记下
6、次小权值x2 = j; /x2记下次小权值结点的下标huftreex1.parent = n+i; /将找出的两棵权值最小的子树合并为一棵子树huftreex2.parent = n+i;huftreen+i.data = huftreex1.data+huftreex2.data;huftreen+i.parent = -1;huftreen+i.left = x1;huftreen+i.right = x2; void HuffmanTree:getHuffmanCode() /获得当前哈夫曼树的哈夫曼编码 int n=leafNum; hufcodes = new char*n; /求n
7、个叶子结点的哈夫曼编码 for (int i=0; in; i+) char *code = new charn; /一个字符串表示一个编码 coden-1=0; int start=n-1; int child = i; int parent = huftreechild.parent; while (parent!=-1) /由叶结点向上直到根结点循环 start-; if (huftreeparent.left=child) codestart=0; /左孩子结点编码为0 else codestart=1; /右孩子结点编码为1 child = parent; parent = huft
8、reechild.parent; hufcodesi=code+start; /编码数组各元素存储由start开始的字符串 void HuffmanTree:print(char table,char string) ofstream fout;fout.open(code.dat,ios:out); coutn 哈夫曼编码：n; for (int i=0; ileafNum; i+)couttablei： hufcodesiendl; bool flag=false; cout哈夫曼编码：endl; for(int j=0;stringj!=0;j+) for(i=0;ileafNum;i+
9、) if(stringj=tablei) flag=true; else flag=false; if(flag) fouthufcodesi; couthufcodesi; fout.close();HuffmanTree:HuffmanTree() delete huftree; delete hufcodes;int HuffmanTree:deep(int i)int j=0;int parent = huftreei.parent;while(parent!=-1)j+;parent = huftreeparent.parent;return j;main.cpp#include #include HufmanTree.hint main()int i,j,n=0;int k=0,a=0;int weight10;char string50;char table26;cout输入字符串:string; for(i=0;stringi!=0;i+) n+;for(i=0;in;i+) int m=0; bool flag=true; for(int p=0;pk;p+)
