㈠ 1用递归实现二叉树的先序、中序、后序三种遍历。2哈夫曼树问题
//在吗？ 我给你。另外我有自己的实验报告。//里面有递归遍历，有迭代遍历。可以写文件，可以压缩编码。可以读文件。//你不需要什么功能的话就删去相应的函数就行了。//希望加分。#include<iostream>#include<fstream>#include<iomanip>#include<string>using namespace std;const int maxlen = 10000; //结点最大数目const int maxlen2 = 260; //字符最大数目，叶节点最大数目const int maxchar = 260; //字符最大数目#define INTMAX 10000000; //大数，大于任意一个权值struct CharSet //程序初始化时保存字符和结点的结构体。{char ch;int weight;};struct HaffNode //哈夫曼树结点结构{int weight,parent,lchild,rchild;char ch;HaffNode() {weight=0; parent=lchild=rchild=-1; ch='\n';}};struct HaffCode //哈夫曼树字符编码信息结构{unsigned int bit; //通过位运算，用一个无符号整形来表示一串二进制编码。int startb; //记录偏移量。int weight;char ch;HaffCode() { bit=0; startb = -1; weight=0; ch='\n';}HaffCode& operator=(HaffCode & obj) //重载赋值符号{bit=obj.bit; startb=obj.startb; ch=obj.ch; weight=obj.weight;return *this;}};class HaffmanSystem{private:CharSet cs[maxlen/2]; //保存初始化时的字符和权值信息。HaffNode hn[maxlen]; //保存哈夫曼树结点信息。HaffCode hc[maxlen/2]; //保存哈夫曼树字符编码信息。HaffCode hc2[maxchar]; //索引散列。考虑到字符数少，以字符的十进制数作为下标保存和索引字符编码信息，时间为O(1);int head; //根结点的数组下标。int n;int leafnum; //叶节点个数，字符个数。public:HaffmanSystem() {n=head=leafnum=0;}void Haffman(); //哈夫曼树生成函数。void InitisLization(); //初始化，调用Haffman();void Encoding(); //对文件"ToBeTran"进行编码。void Decoding(); //对文件"CodeFile"译码。void Print(); //印代码至屏幕。static void TreePrinting(int pos,int i,int child_flag,HaffmanSystem * p,ofstream & fop);void TreePrinting(); //输出哈夫曼树图形到屏幕和文件，其中要调用静态实例函数完成递归功能。void TreeFromFile(); //从文件中获取哈夫曼树。};void HaffmanSystem::InitisLization(){cout<<"字符集大小n,（去掉空格）："<<endl; //读入字符和权值信息。cin>>n;for(int i=0;i<n;i++){cout<<"第"<<i+1<<"个字符和权值，用空格隔开：";cin>>cs[i].ch>>cs[i].weight;}cout<<"最后输入空格的权值(小于等于0表示空格不存在): "<<endl; //对空格特殊处理。cin>>cs[n].weight;cs[n].ch=' ';if(cs[n].weight>0) n++;this->Haffman(); //调用哈夫曼树生成函数。}//哈夫曼树生成函数。void HaffmanSystem::Haffman(){leafnum=n;int i,j,m1,m2,k1,k2;for(i=0;i<n;i++) {hn[i].weight = cs[i].weight; hn[i].ch = hc[i].ch = cs[i].ch;}for(i=0;i<n-1;i++) //n-1个分支节点；{m1=m2=INTMAX; k1=k2=0;for(j=0;j<n+i;j++){if(m1>hn[j].weight && hn[j].parent==-1){m2 = m1; k2 = k1;m1 = hn[j].weight ; k1 = j;}else if(m2>hn[j].weight && hn[j].parent==-1){m2 = hn[j].weight; k2 = j;}}hn[k1].parent = n+i; hn[k2].parent = n+i;hn[n+i].weight = hn[k1].weight+hn[k2].weight;hn[n+i].lchild = k1; hn[n+i].rchild = k2;head = n+i;}int child,parent;for(i=0;i<n;i++){hc[i].weight = hn[i].weight;child = i;parent = hn[child].parent;while(parent != -1){if(hn[parent].lchild == child){++hc[i].startb;}else if(hn[parent].rchild == child){hc[i].bit = hc[i].bit|(1<<++hc[i].startb);}child = parent;parent = hn[child].parent;}hc2[hc[i].ch]=hc[i];}char choice='N';cout<<"是否保存当前哈夫曼树进hfmTree.dat中？"<<endl;cin>>choice;if(choice=='y'||choice=='Y') //把生成的哈弗曼树保存在文件hfmTree.dat中。{ofstream fop;fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);if(!fop) {cout<<"打开文件错误，保存失败"<<endl; return ;}fop.write((char*)&leafnum,sizeof(leafnum));for(i=0;i<2*leafnum-1;i++){fop.write((char*)&hn[i],sizeof(hn[i]));}for(i=0;i<maxchar;i++){fop.write((char*)&hc2[i],sizeof(hc2[i]));}fop.close();cout<<"保存成功！"<<endl;}}//编码函数。void HaffmanSystem::Encoding(){if(leafnum==0) { TreeFromFile(); }char ch;int i,num=0,bitTemp, startTemp=-1, temp2=0;ifstream fip2("ToBeTran.txt",ios::in);if(!fip2){ cout<<"无法打开指定文件【ToBeTran.txt】！"<<endl; return ;}while(fip2.get(ch)) { num++;}fip2.close();ofstream fop1("CodeFile.dat",ios::out|ios::trunc|ios::binary);if(!fop1){ cout<<"无法打开指定文件【CodeFile.dat】！"<<endl; return ;}ofstream fop2("CodePrin.txt",ios::out|ios::trunc);if(!fop2){ cout<<"无法打开指定文件【CodePrin.txt】！"<<endl; return ;}ifstream fip1("ToBeTran.txt",ios::in);if(!fip1){ cout<<"无法打开指定文件【ToBeTran.txt】！"<<endl; return ;}fop1.write((char*)& num,sizeof(num)); //先写入字符数量。char bitBuf=0; //用一个字符空间来缓冲二进制数据，每凑满八位就写入编码文件。cout<<"\n待编码文件【ToBeTran.txt】: ";for(i=7;;i–){if(i==-1){//用一个字符空间bitBuf来缓冲二进制数据，每凑满八位就写入编码文件。fop1.write((char*)& bitBuf,sizeof(bitBuf));i=7; bitBuf=0;//初始字符，使之为二进制“00000000”;}if(startTemp<0){ if(num–<=0) break;fip1.get(ch);cout<<ch;bitTemp = hc2[ch-0].bit;startTemp = hc2[ch-0].startb;}//位运算，确定某位上是0还是1。temp2 = (1 & bitTemp>>startTemp–);if(temp2) fop2<<"1";else fop2<<"0";bitBuf = bitBuf | temp2<<i;//还是位运算，把0或1与原字符相与得到新的编码信息。如00010000 | 1<<7 =10010000.}fop1.write((char*)& bitBuf,sizeof(bitBuf)); //把最后的一段写入文件。fip1.close();fop1.close(); //关闭文件流。fop2.close();cout<<"\n\n编码成功！"<<endl;}//译码函数。void HaffmanSystem::Decoding(){if(leafnum==0) { TreeFromFile();}ofstream fop("TextFile.txt",ios::out|ios::trunc);if(!fop) {cout<<"无法打开指定文件[TextFile.txt]"<<endl; return ;}ifstream fip("CodeFile.dat",ios::in);if(!fip) {cout<<"无法打开指定文件[CodeFile.dat]"<<endl; return ;}char ch,bitBuf;int num,bitTemp=-1, startTemp=-1;int FLAG=0,parent=head;fip.read((char*)& num,sizeof(num));cout<<"译码结果： ";for(int i=-1;num>0;i–){if(i==-1){fip.read((char*)& bitBuf,sizeof(bitBuf));i=7;}//译码和编码一样，同样飘逸的位运算处理，可以节省时间和空间。FLAG=(1<<i)&bitBuf;if(FLAG==0) //0向左{ parent = hn[parent].lchild;}else //1向右{parent = hn[parent].rchild;}//自顶向下搜索，碰到叶节点就是所求结点字符。if(hn[parent].lchild==-1 && hn[parent].rchild==-1){ch=hn[parent].ch;cout<<ch;fop <<ch;parent = head;num–;}}cout<<endl;fip.close();fop.close();cout<<"译码成功！"<<endl;}//打印编码函数。void HaffmanSystem::Print(){ifstream fip("CodePrin.txt",ios::in);if(!fip) {cout<<"无法打开指定文件[CodePrin.txt]"<<endl; return ;}int j =0;char ch;cout<<"字符形式编码文件【CodePrin.txt】: ";while(fip>>ch){if(j%50==0) cout<<endl; //50个字符换行。j++;cout<<ch;}cout<<endl;fip.close();}//输出哈夫曼树到屏幕和文件TreePrint.txtvoid HaffmanSystem::TreePrinting(){if(leafnum==0) { TreeFromFile();}ofstream fop("TreePtint.txt",ios::out|ios::trunc);if(!fop) {cout<<"无法打开指定文件【TreePtint.txt】！"<<endl; return;}cout<<"逆时针90度直观输出二叉树(括号里面是权值)：\n"<<endl;fop <<"逆时针90度直观输出二叉树(括号里面是权值)：\n"<<endl;TreePrinting(head,1,2,this,fop); //fop传递一个文件流，用于在递归的各个层次对同一文件输出。cout<<endl;fop.close();}//输出函数，静态实现，方便递归调用。void HaffmanSystem::TreePrinting(int pos,int i,int child_flag,HaffmanSystem * p,ofstream & fop){ //模仿课本输出二叉树。if(pos>=0 && pos<=p->head){TreePrinting(p->hn[pos].rchild,i+1,1,p,fop);for(int j=0; j<4*(i-1); j++) {cout<<" "; fop<<" ";}if(child_flag==-1) {cout<<"\\"; fop<<"\\";}else if(child_flag== 1) {cout<<"/"; fop<<"/";}if(p->hn[pos].ch=='\n') {cout<<"–NULL"<<endl; fop<<"–NULL"<<endl;}else { cout<<"–"<<p->hn[pos].ch<<"("<<p->hn[pos].weight<<")"<<endl;fop<<"–"<<p->hn[pos].ch<<"("<<p->hn[pos].weight<<")"<<endl;}TreePrinting(p->hn[pos].lchild,i+1,-1,p,fop);}}void HaffmanSystem::TreeFromFile(){int i;cout<<"哈夫曼树不在内存中，尝试从文件中读入哈夫曼树…"<<endl;ifstream file;file.open("hfmTree.dat",ios::in|ios::binary);if(!file) {cout<<"无法打开指定文件【hfmTree.dat】！"<<endl; return ;}if(file.eof()) {cout<<"哈夫曼树文件空，请初始化！"<<endl; return ;}file.read((char*)&leafnum,sizeof(leafnum));head=leafnum*2-2;for(i=0;i<2*leafnum-1;i++){file.read((char*)&hn[i],sizeof(hn[i]));}for(i=0;i<=maxchar;i++){file.read((char*)&hc2[i],sizeof(hc2[i]));}file.close();}//主函数.int main(){HaffmanSystem * T = new HaffmanSystem();char choice = 'Y';while(choice!='0'){cout<<"——————————————————————————-"<<endl;cout<<std::left<<setw(12)<<" 1–初始化"<<setw(12)<<"2–编码 "<<setw(12)<<"3–译码 "<<setw(17)<<"4–印代码文件 "<<setw(15)<<"5–印哈夫曼树 "<<"0–退出"<<endl;cout<<"——————————————————————————-"<<endl;cout<<std::right<<setw(40)<<"操作： ";cin>>choice;switch(choice){case '0': { cout<<"系统已经退出"<<endl; return 0;}case '1': { T->InitisLization(); break;}case '2': { T->Encoding(); break;}case '3': { T->Decoding(); break;}case '4': { T->Print(); break;}case '5': { T->TreePrinting(); break;}default :break;}}return 0;}
㈡ 怎样将建立好的哈夫曼树保存在文件中
哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为 WPL=(W1*L1+W2*L2+W3*L3+…+Wn*Ln)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）一、对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,…,Ti,…,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构： struct tree{float weight; /*权值*/union{char leaf; /*叶结点信息字符*/struct tree *left; /*树的左结点*/};struct tree *right; /*树的右结点*/};struct forest{ /*F集合，以链表形式表示*/struct tree *ti; /* F中的树*/struct forest *next; /* 下一个结点*/};例：若字母A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为bb 或ca，因为b的编码是c的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为 1，当然你也可以反过来规定。这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符 0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为 0–2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。
㈢ 对一篇文章进行哈夫曼编码，生成哈夫曼树之后，怎样将编码以二进制的形式写入到文件中，而不是以字符
当你把哈夫曼树构造成功后 对于每一个字符都可以用 0 1来表示，你可以让每八个0 1组合转换成十进制，然后在把这个数值付给一个字符 ，这样就等于用2进制存储了 把八个0 1组合压缩成了一个字节，即二进制写入文件了！
㈣ 终端读入字符集大小为n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfm
和n个权值，建立赫夫曼树，并将它存于文件hfmTree中（2学时）。实验性质:设计性说明：通过该算法的设计和程序实现，掌握表示赫夫曼树和建立赫夫曼树的方法，理解赫夫曼编码的应用。
㈤ 我们有个数据结构的哈夫曼编码解码的课程设计，你能帮帮我吗
树和哈夫曼树实验报告一．实验目的练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码二．实验环境 Microsoft visual c++三．实验问题描述1. 问题描述：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），并将此二叉树按照“树状形式”打印输出，然后对其进行遍历（先序、中序和后序），最后将遍历结果打印输出。在遍历算法中要求至少有一种遍历采用非递归方法。测试数据：ABCØØDEØGØØFØØØ（其中Ø表示空格字符）输出结果为：先序：ABCDEGF先序：CBEGDFA先序：CGEFDBA2. 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。基本要求：(至少完成功能1-2）一个完整的系统应具有以下功能：I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。基本要求：E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。D：译码（Decoding )。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据：设权值w=（5，29，7，8，14，23，3，11），n=8。 按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为： 5：0001，29：11，7：1110，8：1111 14：110，23：01，3：0000，11：001用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。四．实验主要程序流实验题目一主要程序：1．void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是#当前树根置为空，否则申请一个新节点//{ char ch; ch=getchar(); if(ch=='.')*bt=NULL; else { *bt=(BitTree)malloc(sizeof(BitNode)); (*bt)->data=ch; CreatBiTree(&((*bt)->LChild)); CreatBiTree(&((*bt)->RChild)); }}2．void Visit(char ch)//访问根节点{ printf("%c ",ch);}3．void PreOrder(BitTree root){ if (root!=NULL) { Visit(root ->data); PreOrder(root ->LChild); PreOrder(root ->RChild); }}4． void InOrder(BitTree root) { if (root!=NULL) { InOrder(root ->LChild); Visit(root ->data); InOrder(root ->RChild); }}5．int PostTreeDepth(BitTree bt) //后序遍历求二叉树的高度递归算法//{ int hl,hr,max; if(bt!=NULL) { hl=PostTreeDepth(bt->LChild); //求左子树的深度 hr=PostTreeDepth(bt->RChild); //求右子树的深度 max=hl>hr?hl:hr; //得到左、右子树深度较大者 return(max+1); //返回树的深度 } else return(0); //如果是空树，则返回0}6．void PrintTree(BitTree Boot,int nLayer) //按竖向树状打印的二叉树 //{ int i; if(Boot==NULL) return; PrintTree(Boot->RChild,nLayer+1); for(i=0;i<nLayer;i++) printf(" "); printf("%c\n",Boot->data); PrintTree(Boot->LChild,nLayer+1);}7．void main(){ BitTree T; int h; int layer; int treeleaf; layer=0; printf("请输入二叉树中的元素(以扩展先序遍历序列输入,其中.代表空子树):\n"); CreatBiTree(&T); printf("先序遍历序列为:"); PreOrder(T); printf("\n中序遍历序列为:"); InOrder(T); printf("\n后序遍历序列为:"); PostOrder(T); h=PostTreeDepth(T); printf("\此二叉树的深度为:%d\n",h); printf("此二叉树的横向显示为：\n"); PrintTree(T,layer);}实验二主要程序流：1．int main(){HuffmanTree huftree; char Choose; while(1){ cout<<"\n**********************欢迎使用哈夫曼编码/译码系统**********************\n"; cout<<"*您可以进行以下操作: *\n";cout<<"*1.建立哈夫曼树 *\n"; cout<<"*2.编码(源文已在文件ToBeTra中，或键盘输入) *\n"; cout<<"* 3.译码(码文已在文件CodeFile中) *\n"; cout<<"* 4.显示码文 *\n"; cout<<"* 5.显示哈夫曼树 *\n"; cout<<"* 6.退出 *\n"; cout<<"***********************************************************************\n"; cout<<"请选择一个操作:"; cin>>Choose; switch(Choose) { case '1': huftree.CreateHuffmanTree(); break; case '2': huftree.Encoder(); break; case '3': huftree.Decoder(); break; case '4': huftree.PrintCodeFile(); break; case '5': huftree.PrintHuffmanTree(); break; case '6': cout<<"\n**********************感谢使用本系统!*******************\n\n"; system("pause"); return 0; }//switch }//while}//main2．// 建立哈夫曼树函数// 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数）void HuffmanTree::CreateHuffmanTree() {char Choose; cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？"; cin>>Choose; if(Choose=='2') { //键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard(); }//choose=='2' else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile(); }}3. // 从键盘建立哈夫曼树函数// 函数功能：从键盘建立哈夫曼树//函数参数：无//参数返回值：无void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num; cout<<"\n请输入源码字符集个数："; cin>>Num; if (Num<=1) { cout<<"无法建立少于2个叶子结点的哈夫曼树。\n\n"; return; } LeafNum=Num; Node=new HuffmanNode[2*Num-1]; for(int i=0;i<Num;i++) {//读入哈夫曼树的叶子结点信息 cout<<"请输入第"<<i+1<<"个字符值"; getchar(); Node[i].sourcecode=getchar(); //源文的字符存入字符数组Info[] getchar(); cout<<"请输入该字符的权值或频度"; cin>>Node[i].weight; //源文的字符权重存入Node[].weight Node[i].parent=-1; Node[i].lchild=-1; Node[i].rchild=-1; Node[i].code="\0"; }for(int j=Num;j<2*Num-1;j++) {//循环建立哈夫曼树内部结点 int pos1,pos2; int max1,max2; pos2=pos1=j; max2=max1=numeric_limits<int>::max( ); //在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标 //pos2最后应指向权重第二小的根结点的下标 //max1存放当前找到的权重最小的根结点的权重 //max2存放当前找到的权重第二小的根结点的权重 for(int k=j-1;k>=0;k–) { if (Node[k].parent==-1){//如果是某棵子树的根结点 if (Node[k].weight<max1){ //发现比当前最大值还大的权重 max2=max1; max1=Node[k].weight; pos2=pos1; pos1=k; } else if(Node[k].weight<max2){ //发现比当前次大值还大的次大权重 max2=Node[k].weight; pos2=k; } }//if (Node[j].parent==-1) } //for //在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos1、pos2所指向的结点 Node[pos1].parent=j; Node[pos2].parent=j; Node[j].lchild=pos1; Node[j].rchild=pos2; Node[j].parent=-1; Node[j].weight=Node[pos1].weight+Node[pos2].weight; } //for //产生所有叶子结点中字符的编码 for (int m=0;m<Num;m++) { //产生Node[i].sourcecode的编码，存入Node[i].code中 int j=m; int j1; while(Node[j].parent!=-1) { //从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code[] j1=Node[j].parent; if(Node[j1].lchild==j) Node[m].code.insert(0,"0"); else Node[m].code.insert(0,"1"); j=j1; }} cout<<"哈夫曼树已成功构造完成。\n";//把建立好的哈夫曼树写入文件hfmTree.dat char ch; cout<<"是否要替换原来的哈夫曼树文件(Y/N):"; cin>>ch; if (ch!='y'&&ch!='Y') return; ofstream fop; fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打开文件 if(fop.fail()) { cout<<"\n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。\n"; return; } fop.write((char*)&Num,sizeof(Num)); //先写入哈夫曼树的叶子结点个数 for(int n=0;n<2*Num-1;n++) { //最后写入哈夫曼树的各个结点（存储在Node[]中） fop.write((char*)&Node[n],sizeof(Node[n])); flush(cout); } fop.close(); //关闭文件 cout<<"\n哈夫曼树已成功写入hfmTree.dat文件。\n";}4. // 从文件建立哈夫曼树函数// 函数功能：从文件建立哈夫曼树//函数参数：无//参数返回值：无void HuffmanTree::CreateHuffmanTreeFromFile(){ ifstream fip; fip.open("hfmTree.dat",ios::binary|ios::in); if(fip.fail()) { cout<<"哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。\n"; return; } fip.read((char*)&LeafNum,sizeof(LeafNum)); if (LeafNum<=1) { cout<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。\n"; fip.close(); return; } Node=new HuffmanNode[2*LeafNum-1]; for(int i=0;i<2*LeafNum-1;i++) fip.read((char*)&Node[i],sizeof(Node[i])); fip.close(); cout<<"哈夫曼树已从文件成功构造完成。\n";}5. // 编码函数// 函数功能：为哈夫曼树编码//函数参数：无//参数返回值：无void HuffmanTree::Encoder(){ if(Node==NULL) { //内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile(); if (LeafNum<=1) { cout<<"内存无哈夫曼树。操作撤销。\n\n"; return; } }//if char *SourceText; //字符串数组，用于存放源文 //让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入 char Choose; cout<<"你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？"; cin>>Choose; if(Choose=='1') { ifstream fip1("ToBeTran.txt"); if(fip1.fail()) { cout<<"源文文件打开失败!无法继续执行。\n"; return; } char ch; int k=0; while(fip1.get(ch)) k++; //第一次读文件只统计文件中有多少个字符，将字符数存入k fip1.close(); SourceText=new char[k+1]; //申请存放源文的字符数组空间 ifstream fip2("ToBeTran.txt"); //第二次读源文文件，把内容写入SourceText[] k=0; while(fip2.get(ch)) SourceText[k++]=ch; fip2.close(); SourceText[k]='\0'; } else { //从键盘输入源文 string SourceBuff; cin.ignore(); cout<<"请输入需要编码的源文(可输入任意长，按回车键结束):\n"; getline(cin,SourceBuff,'\n'); int k=0; while(SourceBuff[k]!='\0') k++; SourceText=new char[k+1]; k=0; while(SourceBuff[k]!='\0') { SourceText[k]=SourceBuff[k]; k++; } SourceText[k]='\0'; } cout<<"需编码的源文为："; cout<<SourceText<<endl; //开始译码 ofstream fop("CodeFile.dat",ios::trunc); //打开码文存放文件 int k=0; while(SourceText[k]!='\0') //源文串中从第一个字符开始逐个编码 { int i; for(i=0;i<LeafNum;i++){ //找到当前要编码的源文的字符在哈夫曼树Node[]中的下标 if(Node[i].sourcecode==SourceText[k]) { //将对应编码写入码文文件 fop<<Node[i].code; break; }; } if (i>=LeafNum) { cout<<"源文中存在不可编码的字符。无法继续执行。\n"<<endl; fop.close(); return; } k++; //源文串中的字符后移一个 } fop.close(); cout<<"已完成编码，码文已写入文件CodeFile.dat中。\n\n";}6. // 译码函数// 函数功能：对哈夫曼树进行译码//函数参数：无//参数返回值：无void HuffmanTree::Decoder(){//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 if(Node==NULL) { CreateHuffmanTreeFromFile(); if (LeafNum<=1) { cout<<"内存无哈夫曼树。操作撤销。\n\n"; return; } }//将码文从文件CodeFile.dat中读入 CodeStr[] ifstream fip1("CodeFile.dat"); if(fip1.fail()) { cout<<"没有码文，无法译码。\n"; return; }char* CodeStr; int k=0; char ch; while(fip1.get(ch)){ k++; } fip1.close(); CodeStr=new char[k+1]; ifstream fip2("CodeFile.dat"); k=0; while(fip2.get(ch)) CodeStr[k++]=ch; fip2.close(); CodeStr[k]='\0';cout<<"经译码得到的源文为："; ofstream fop("TextFile.dat"); int j=LeafNum*2-1-1; //j指向哈夫曼树的根 int i=0; //码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子 while(CodeStr[i]!='\0') { //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符 if(CodeStr[i]=='0') j=Node[j].lchild; else j=Node[j].rchild; if(Node[j].rchild==-1) { //因为哈夫曼树没有度为1的结点，所以此条件等同于Node[j]为叶结点 cout<<Node[j].sourcecode; //屏幕输出译出的一个源文字符 fop<<Node[j].sourcecode; j=LeafNum*2-1-1; //j再指向哈夫曼树的根 } i++; } fop.close(); cout<<"\n译码成功且已存到文件TextFile.dat中。\n\n";}7. // 输出码文函数// 函数功能：从文件中输出哈夫曼树的码文//函数参数：无//参数返回值：无void HuffmanTree::PrintCodeFile(){ char ch; int i=1; ifstream fip("CodeFile.dat"); ofstream fop("CodePrin.dat"); if(fip.fail()) {cout<<"没有码文文件，无法显示码文文件内容。\n"; return; } while(fip.get(ch)) {cout<<ch; fop<<ch; if(i==50) { cout<<endl; fop<<endl; i=0; } i++; } cout<<endl; fop<<endl; fip.close(); fop.close(); }8. // 输出函数// 函数功能：从内存或文件中直接输出哈夫曼树//函数参数：无//参数返回值：无void HuffmanTree::PrintHuffmanTree(){ //如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 if(Node==NULL) { CreateHuffmanTreeFromFile(); if (LeafNum<=1) { cout<<"内存无哈夫曼树。操作撤销。\n\n"; return; }} ofstream fop("TreePrint.dat",ios_base::trunc); fop.close(); PrintHuffmanTree_aoru(2*LeafNum-1-1); return;}
㈥ C语言 哈夫曼树以文件形式保存是什么意思一棵树怎么能保存在文件里
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。至于如何保存一棵二叉树，一般知道了前序遍历和中序遍历或者后序遍历和中序遍历就可以知道一棵树具体是样子了。你可以考虑使用这种方法。就是在文件中提供两种遍历方法，其中必须要有一种是中序遍历。
㈦ C语言哈夫曼数的问题
#include <stdlib.h>#include <string.h>///////////////////////////////////////////////////////////////////////////////*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/typedef struct{ int weight; char ch; //增加一个域用于存放该节点的字符 int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char **HuffmanCode; //指向赫夫曼编码的指针///////////////////////////////////////////////////////////////////////////////*本程序用到的函数原型*/void welcome(); //打印操作选择界面void HuffmanCoding(HuffmanTree &,char *,int *,int);//建立赫夫曼树的算法void select(HuffmanTree HT,int j,int *s1,int *s2); //从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点void Init(); //输入n个字符及其对应的权值，根据权值建立哈夫曼树void Coding(); //编码void Decoding(); //译码void Print_code(); //打印译码好的代码文件void Print_tree(); //以凹凸表形式打印哈夫曼树int Read_tree(HuffmanTree &); //从文件中读入赫夫曼树void find(HuffmanTree &HT,char *code,char *text,int i,int m);//译码时根据01字符串寻找相应叶子节点的递归算法void Convert_tree(unsigned char T[100][100],int s,int *i,int j);//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; //全局变量，指向存放赫夫曼树的存储空间int n=0; //全局变量，存放赫夫曼树叶子结点的数目int main(){char select;while(1){ welcome(); scanf("%c",&select); switch(select) { case 'i': case 'I':Init();break; case 'c': case 'C':Coding();break; case 'd': case 'D':Decoding();break; case 'p': case 'P':Print_code();break; case 't': case 'T':Print_tree();break; case 'e': case 'E':exit(1); default :printf("Input error!\n"); } getchar();}return 0;}void welcome() //打印操作选择界面{printf("*—————————————————–*\n");printf("| What do you want to do? |\n");printf("|—————————————————–|\n"); printf("| |\n");printf("| I————————–Init the Huffman tree. |\n");printf("| C————————–Code your file. |\n");printf("| D————————–Decode the code. |\n");printf("| P————————–Print the codefile. |\n");printf("| T————————–Print the Huffman tree. |\n"); printf("| |\n"); printf("*—————————————————–*\n");}///////////////////////////////////////////////////////////////////////////////////////*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/void Init() {FILE *fp;int i,n,w[52]; //w数组存放n个字符的权值char character[52]; //存放n个字符printf("\n输入字符个数 n:");scanf("%d",&n); //输入字符集大小printf("输入%d个字符及其对应的权值:\n",n);for (i=0;i<n;i++){ char b=getchar(); scanf("%c",&character[i]); scanf("%d",&w[i]); //输入n个字符和对应的权值} HuffmanCoding(HT,character,w,n); //建立赫夫曼树if((fp=fopen("hfmtree.txt","w"))==NULL) printf("Open file hfmtree.txt error!\n");for (i=1;i<=2*n-1;i++){ if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中 printf("File write error!\n");}printf("\n建立赫夫曼树成功，已将其存于文件hfmtree.txt中\n");fclose(fp);}/////////////////////////////////////////////////////////////////////////////////////////建立赫夫曼树的算法///////////////////////////////////////////////////////////void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n){int m,i,s1,s2;HuffmanTree p;if(n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,++character,++w)for(;i<=m;++i,++p) for(i=n+1;i<=m;++i){ select(HT,i-1,&s1,&s2); HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;}}////////////////////////////////////////////////////////////////////////////////*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/void select(HuffmanTree HT,int j,int *s1,int *s2){int i;//找weight最小的结点for (i=1;i<=j;i++) if (HT[i].parent==0) for (;i<=j;i++) if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight)) *s1=i; HT[*s1].parent=1;//找weight次小的结点for (i=1;i<=j;i++) if (HT[i].parent==0) for (;i<=j;i++) if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight)) *s2=i;}////////////////////////////////////////////////////////////////////////////////*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/void Coding() {FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 /////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中{HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;++i){ start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[–start]='0'; else cd[–start]='1'; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]);}free(cd);}/////////////////////////////////////////////////////////////////////////////////////if((fp=fopen("tobetrans.txt","rb"))==NULL) printf("Open file tobetrans.txt error!\n");if((fw=fopen("codefile.txt","wb+"))==NULL) printf("Open file codefile.txt error!\n");char temp;fscanf(fp,"%c",&temp); //从文件读入第一个字符while(!feof(fp)){ for(i=1;i<=n;i++) if(HT[i].ch==temp) break; //在赫夫曼树中查找字符所在的位置 for(int r=0;HC[i][r]!='\0';r++) //将字符对应的编码存入文件 fputc(HC[i][r],fw); fscanf(fp,"%c",&temp); //从文件读入下一个字符}fclose(fw);fclose(fp);printf("\n对文件hfmtree.txt编码成功,结果已存入codefile.txt中。\n\n");}//////////////////////////////////////////////////////////////////////////*将文件codefile中的代码进行译码，结果存入文件textfile中*/void Decoding() {FILE *fp,*fw;int m,i;char *code,*text,*p; if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数if((fp=fopen("codefile.txt","rb"))==NULL) printf("Open file codefile.txt error!\n"); if((fw=fopen("textfile.txt","wb+"))==NULL) printf("Open file textfile.txt error!\n");code=(char *)malloc(sizeof(char));fscanf(fp,"%c",code); //从文件读入一个字符for(i=1;!feof(fp);i++){ code=(char *)realloc(code,(i+1)*sizeof(char)); //增加空间 fscanf(fp,"%c",&code[i]); //从文件读入下一个字符 }code[i-1]='\0';/////////到此codefile.txt文件中的字符已全部读入，存放在code数组中 text=(char *)malloc(100*sizeof(char));p=text; m=2*n-1;if(*code=='0') find(HT,code,text,HT[m].lchild,m); //从根节点的左子树去找else find(HT,code,text,HT[m].rchild,m); //从根节点的右子树去找 for(i=0;p[i]!='\0';i++) //把译码好的字符存入文件textfile.txt中 fputc(p[i],fw);fclose(fp);fclose(fw);printf("\n对codefile.txt文件译码成功，结果已存入textfile.txt文件。\n\n");}///////////////////////////////////////////////////////////////////////////////////////////////////////*将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。*/void Print_code(){FILE *fp,*fw;char temp;int i; if((fp=fopen("codefile.txt","rb"))==NULL) printf("Open file codefile.txt error!\n");if((fw=fopen("codeprint.txt","wb+"))==NULL) printf("Open file codeprint.txt error!\n");printf("\n文件codefi1e以紧凑格式显示如下:\n");fscanf(fp,"%c",&temp); //从文件读入一个字符for (i=1;!feof(fp);i++){ printf("%c",temp); if(i%50==0) printf("\n"); fputc(temp,fw); //将该字符存入文件codeprint.txt中 fscanf(fp,"%c",&temp); //从文件读入一个字符}printf("\n\n此字符形式的编码已写入文件codeprint.txt中.\n\n");fclose(fp);fclose(fw);}///////////////////////////////////////////////////////////////////////////////////////////////////*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/void Print_tree(){unsigned char T[100][100];int i,j,m=0;FILE *fp;if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数Convert_tree(T,0,&m,2*n-1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中if((fp=fopen("treeprint.txt","wb+"))==NULL) printf("Open file treeprint.txt error!\n"); printf("\n以凹凸表形式打印已建好的赫夫曼树：\n");for(i=1;i<=2*n-1;i++){ for (j=0;T[i][j]!=0;j++) { if(T[i][j]==' ') else } printf("\n");}fclose(fp);printf("\n此字符形式的哈夫曼树已写入文件treeprint.txt中.\n\n");}///////////////////////////////////////////////////////////////////////////////////*从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数*/int Read_tree(HuffmanTree &HT) {FILE *fp;int i,n;HT=(HuffmanTree)malloc(sizeof(HTNode)); if((fp=fopen("hfmtree.txt","r"))==NULL) printf("Open file hfmtree.txt error!\n");for (i=1;!feof(fp);i++){ HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); //增加空间 fread(&HT[i],sizeof(HTNode),1,fp); //读入一个节点信息}fclose(fp);n=(i-1)/2;return n;}/////////////////////////////////////////////////////////////////*译码时根据01字符串寻找相应叶子节点的递归算法*/void find(HuffmanTree &HT,char *code,char *text,int i,int m){if(*code!='\0') //若译码未结束{ code++; if(HT[i].lchild==0&&HT[i].rchild==0) //若找到叶子节点 { *text=HT[i].ch; //将叶子节点的字符存入text中 text++; if((*code=='0')) find(HT,code,text,HT[m].lchild,m); //继续从根节点的左子树找 else find(HT,code,text,HT[m].rchild,m); //继续从根节点的右子树找 } else //如果不是叶子节点 if(*code=='0') find(HT,code,text,HT[i].lchild,m); //从该节点的左子树去找 else find(HT,code,text,HT[i].rchild,m); //从该节点的右子树去找}else *text='\0'; //译码结束}/////////////////////////////////////////////////////////////////////////*将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/void Convert_tree(unsigned char T[100][100],int s,int *i,int j){int k,l;l=++(*i);for(k=0;k<s;k++) T[l][k]=' ';T[l][k]=HT[j].weight;if(HT[j].lchild) Convert_tree(T,s+1,i,HT[j].lchild);if(HT[j].rchild) Convert_tree(T,s+1,i,HT[j].rchild); T[l][++k]='\0';}为了您的安全，请只打开来源可靠的网址打开网站 取消来自: 另外,团IDC网上有许多产品团购,便宜有口碑
