树和哈夫曼树实验报告
一．实验目的
练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码 二．实验环境
Microsoft visual c++ 三．实验问题描述
1.问题描述：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。
基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），并将此二叉树按照“树状形式”打印输出，然后对其进行遍历（先序、中序和后序），最后将遍历结果打印输出。在遍历算法中要求至少有一种遍历采用非递归方法。 测试数据：
ABCØØDEØGØØFØØØ（其中Ø表示空格字符） 输出结果为： 先序：ABCDEGF 先序：CBEGDFA 先序：CGEFDBA 2.问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 基本要求：(至少完成功能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;idata); 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>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
// 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数） void HuffmanTree::CreateHuffmanTree() {char Choose; cout>Choose; if(Choose==\'2\') { //键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard(); }//choose==\'2\' else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile(); } } 3.// 从键盘建立哈夫曼树函数
// 函数功能：从键盘建立哈夫曼树 //函数参数：无 //参数返回值：无
void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num; cout>Num; if (Num
cout>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
int pos1,pos2; int max1,max2; pos2=pos1=j; max2=max1=numeric_limits::max( ); //在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标
//pos2最后应指向权重第二小的根结点的下标 //max1存放当前找到的权重最小的根结点的权重 //max2存放当前找到的权重第二小的根结点的权重
for(int k=j-1;k>=0;k--) { if (Node[k].parent==-1){//如果是某棵子树的根结点
if (Node[k].weight
max2=max1; max1=Node[k].weight; pos2=pos1; pos1=k; } else if(Node[k].weight
max2=Node[k].weight; pos2=k; } }//if (Node[j].parent==-1) } //for //在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos
1、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
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
//把建立好的哈夫曼树写入文件hfmTree.dat char ch; cout>ch; if (ch!=\'y\'&&ch!=\'Y\') return; ofstream fop; fop.open(\"hfmTree.dat\",ios::out|ios::binary|ios::trunc); //打开文件
if(fop.fail()) { cout
for(int n=0;n
fop.write((char*)&Node[n],sizeof(Node[n])); flush(cout); } fop.close(); //关闭文件
cout
// 函数功能：从文件建立哈夫曼树 //函数参数：无 //参数返回值：无
void HuffmanTree::CreateHuffmanTreeFromFile(){ ifstream fip; fip.open(\"hfmTree.dat\",ios::binary|ios::in); if(fip.fail()) { cout
// 函数功能：为哈夫曼树编码 //函数参数：无 //参数返回值：无
void HuffmanTree::Encoder() { if(Node==NULL) { //内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile(); if (LeafNum
//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入 char Choose; cout>Choose; if(Choose==\'1\') { ifstream fip1(\"ToBeTran.txt\"); if(fip1.fail()) { cout
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
ofstream fop(\"CodeFile.dat\",ios::trunc); //打开码文存放文件 int k=0; while(SourceText[k]!=\'\\0\') //源文串中从第一个字符开始逐个编码 { int i; for(i=0;i
if(Node[i].sourcecode==SourceText[k]) { //将对应编码写入码文文件
fop=LeafNum) { cout
// 函数功能：对哈夫曼树进行译码 //函数参数：无 //参数返回值：无
void HuffmanTree::Decoder() {//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 if(Node==NULL) { CreateHuffmanTreeFromFile(); if (LeafNum
//将码文从文件CodeFile.dat中读入 CodeStr[] ifstream fip1(\"CodeFile.dat\"); if(fip1.fail()) { cout
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
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
fop
} i++; } fop.close();
cout
// 函数功能：从文件中输出哈夫曼树的码文 //函数参数：无 //参数返回值：无
void HuffmanTree::PrintCodeFile() { char ch; int i=1; ifstream fip(\"CodeFile.dat\"); ofstream fop(\"CodePrin.dat\"); if(fip.fail()) { cout
// 函数功能：从内存或文件中直接输出哈夫曼树 //函数参数：无 //参数返回值：无
void HuffmanTree::PrintHuffmanTree() { //如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 if(Node==NULL) { CreateHuffmanTreeFromFile(); if (LeafNum
