Question

1用递归实现二叉树的先序、中序、后序三种遍历。2哈夫曼树问题

1通过调试为下面的二叉树建立二叉链表，并用递归实现二叉树的先序、中序、后序三种遍历。
2[基本要求]：
A：从终端读入字符集大小为n，及n个字符和n个权值，建立哈夫曼树，进行编码并且输出。并将它存于文件hfmtree中。
B：利用已建好的哈夫曼编码文件hfmtree，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。
[测试数据] 用下表中给出的字符集和频度的实际统计数据建立哈夫曼树：
字符 A B C D E F G H I J K L M N
频度 64 13 22 32 103 21 15 47 57 1 5 32 20 57
字符 O P Q R S T U V W X Y Z 空格
频度 63 15 1 48 51 80 23 8 18 1 16 1 168
并实现以下报文的译码和输出：“THIS PROGRAM IS MY FAVORITE”。

Answer 1

//在吗？ 我给你。另外我有自己的实验报告。
//里面有递归遍历，有迭代遍历。可以写文件，可以压缩编码。可以读文件。
//你不需要什么功能的话就删去相应的函数就行了。
//希望加分。
#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.txt
void 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;
}

Answer 2

民安国泰逢盛世 风调雨顺颂华年 横批：民泰国安

Answer 3

一干二净除旧习 五讲四美树新风 横批：辞旧迎春