二叉树两种存储结构应用

《二叉树两种存储结构应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验 实验四 二叉树两种存储结构的应用   计算机科学与技术系0901班日期：2011年5月5日  实验报告2009级0901班2011年5月5日实验类型：综合设计型实验地点：软件实验室三一             实验题目二叉树两种存储结构的应用二             需求分析本实验需要设计程序，输入叶子结点和权值，建立一颗哈弗曼树，并根据哈弗曼树进行编码和译码操作。键盘中输入或者从文件中读入哈弗曼树；键盘中输入或者从源文件中读入需要编码的源文，然后将源文根据哈弗曼树的权值，译码为二进制代码。最后实现凹入显示法显示哈弗曼树。三             概要

2、设计本程序由HaffmanTree.h、HaffmanTree.cpp、main.cpp三个文件构成。HaffmanTree.h中定义了哈弗曼树的储存结构体HaffmanNode，里面定义了weight、parent、lchild、rchild四个变量来描述哈弗曼树的储存结构。在HaffmanTree.h中还定义了一个名为HaffmanTree的类，里面定义的是建树、编码、译码和凹入显示哈弗曼树等函数，而相关的实现代码则在HaffmanTree.cpp中给出。main.cpp中主要是实现内部函数与用户界面的对接。voidCreateHuffmanTree();//*在内

3、存中建立哈夫曼树，存放在Node[]中。让用户从两种建立哈夫曼树的方法中选择：1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/voidCreateHuffmanTreeFromKeyboard();voidCreateHuffmanTreeFromFile();voidEncoder();//*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFi

4、le中。ToBeTran的内容可以用记事本等程序编辑产生。*/voidDecoder();//*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，得到的源文写入文件TextFile中，并同时输出到屏幕上。*/voidPrintCodeFile();//*将码文文件CodeFile显示在屏幕上*/voidPrintHuffmanTree();//*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上，同时写入文件TreePrintFile中*/voidPri

5、ntHuffmanTree_aoru(intT,intlayer=1);//*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/译码建立哈弗曼树从键盘输入从内存中读取哈弗曼树从键盘输入码文从内存中读取码文编码显示哈弗曼树退出四             详细设计建立哈弗曼树voidHuffmanTree::CreateHuffmanTreeFromKeyboard(){intNum;cout<<"请输入源码字符集个数：";cin>>Num;if(Num<=1){cout<<"无法建立少于2个叶子结点的哈夫曼树。";return;}LeafN

6、um=Num;Node=newHuffmanNode[2*Num-1];Info=newchar[2*Num-1];for(inti=0;i>Node[i].weight;//源文的字符权重存入Node[].weightNode[i].parent=-1;Node[i].lchild=-1;Node[i].r

7、child=-1;}for(i=Num;i<2*Num-1;i++){//循环建立哈夫曼树内部结点intpos1=-1,pos2=-1;intmax1=32767,max2=32767;for(intj=0;j