数据结构实验二

1、精选优质文档-倾情为你奉上实 验 报 告（ 2016 / 2017 学年 第 一 学期）课程名称数据结构 A实验名称二叉树的基本操作及哈夫曼编码译码系统的实现专心-专注-专业实 验 报 告实验名称二叉树的基本操作及哈夫曼编码译码系统的实现指导教师实验类型验证实验学时2+2实验时间一、 实验目的和要求目的：创建一棵二叉树，实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。哈夫曼编码/译码系统。要求：能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存。二、实验环境(实验设备)PC计算机，Windows 7操作系统，IDE: Codeblocks 16.01编译

2、器: GNU GCC Compiler三、实验原理及内容程序一：二叉树的创建以及基本运算本程序一共包含两个类，一个是BTNode 结点类，定义了三个数据成员，分别是该结点元素数值和指向左右子树的指针，定义了三个重载的构造函数。，声明Btree类是BTNode的友元，Visit函数是BTNode的友元函数。本程序另一个类是Btree 二叉树类，包含一个数据成员（指向根节点的指针root）和一组运算，包括先序，中序，后序，层次遍历，构造二叉树，拆分二叉树，判断是否空，计算结点数，释放二叉树占用空间等。类UML图：实 验 报 告核心模块代码:1. 二叉树的创建创建一个二叉树要新申请一个结点，左右子树

3、分别指向参数的两个二叉树，结点元素赋值为参数值。要先判断左右子树是不是同一个树以及当前调用对象是不是一个空二叉树。最后要将引用参数中root指针赋值为NULL，反正指针共享同一个空间造成混乱。代码：template <class T>void BTree<T>:MakeTree(const T &e, BTree<T>& left, BTree<T>& right) if(root|&left=&right) return; root=new BTNode<T>(e,left.root,righ

4、t.root); left.root=right.root=NULL;cout<<"here in BTree<T>:MakeTree"<<endl;2. 二叉树的拆分将一个二叉树拆分成两个二叉树，首先要判断参数中二叉树是不是空，是不是同一个二叉树，以及当前对象二叉树是不是空。然后将引用参数的root指针赋值为当前对象的左右子树。最后delete当前对象root指向的结点，并将root赋值为NULL，防止指针指向的空间被共享。代码：template <class T>void BTree<T>:BreakTree(

5、T &e,BTree<T>&left, BTree<T>& right)cout<<"here in BTree<T>:BreakTree."<<endl;if(left.root|right.root|!root|&left=&right) return ;e=root->element;left.root=root->lchild;right.root=root->rchild;delete root;root=NULL;3. 二叉树的遍历二叉树的先序遍

6、历重载有两个函数，分别是面向用户的PreOrder(void (*Visit)(BTNode<T>* u)函数和私有函数PreOrder(void (*Visit)(BTNode<T>*u), BTNode<T>*t)。前者调用后者进行递归，完成遍历。先序遍历中。先访问当前结点的element域，在分别调用PreOrder递归访问左右子树，如果当前指针t为空，则达到递归边界返回。中序遍历和后序遍历只在Visit访问element出现的位置有区别，其他一样。先序遍历代码：template <class T>void BTree<T>:P

7、reOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)if(t) Visit(t); PreOrder(Visit,t->lchild); PreOrder(Visit,t->rchild);中序遍历代码：template <class T>void BTree<T>:InOrder (void (*Visit)(BTNode<T>* u),BTNode<T>* t)if (t)InOrder(Visit,t->lchild);Visit(t); InOrder

8、(Visit,t->rchild);后序遍历代码：template <class T>void BTree<T>:PostOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t)if (t) PostOrder(Visit,t->lchild); PostOrder(Visit,t->rchild); Visit(t);算法分析：结点数是n个，如果不考虑系统栈的消耗，由于回溯，每个结点最多访问2次，所以时间复杂度是O（n）。4. 二叉树的层次遍历实现二叉树的层次遍历，定义一个临时的队列（队列

9、中元素是指向结点的指针），首先将根节点入队列，当对列不为空的时候：取队首元素，输出队首元素，将队首元素的左右结点入队列，删除队首元素。如此循环直到队列为空。代码：template <class T>void BTree<T>:CenOrder(void (*Visit)(BTNode<T>* u),BTNode<T>* t) if(t=NULL) return; queue<BTNode<T>* > s;/需在头文件加入#include <queue> s.push(t); BTNode<T> *p

10、; while(s.empty()=0) p=s.front(); Visit(p); if(p->lchild!=NULL) s.push(p->lchild); if(p->rchild!=NULL) s.push(p->rchild); s.pop(); 算法分析：While循环中每次都要pop()一个元素，结点数为n个，最终n个元素都要加入队列，出队列，while循环执行n次，所以时间复杂度是O（n）。空间复杂度分析：队列s中最坏的情况是每次出去一个加入两个，最多时候有n/2个元素，所以空间复杂度是O(n)。5. 求二叉树的镜像二叉树通过面向用户的Exch函数调

11、用Change函数进行递归，完成二叉树的反转。对于每一个结点。交换左右子树指针的值，是左子树指向原右子树，右子树指针指向原左子树，并进入到下一次递归。代码：template <class T>void BTree<T>:Change(BTNode<T> *t) if(t) Change(t->lchild); Change(t->rchild); BTNode<T> *p; p=t->lchild; t->lchild=t->rchild; t->rchild=p; 算法分析：相当于进行了一次遍历，每一个结点访

12、问有限次，所以时间复杂度是O（n）。6. 计算二叉树结点数目二叉树结点数=左子树结点数+右子树结点数+1。其中1是当前结点。根据这个公式编写递归程序。注意递归边界p=NULL返回0.代码：template <class T>int BTree<T>:CountNode(BTNode<T> *p) if(p=NULL) return 0; else return CountNode(p->lchild)+CountNode(p->rchild)+1;算法分析：设一共n个结点，对每个结点由于回溯最多访问两次，所以时间复杂度是O（n）。7. 计算二叉树

13、的高度二叉树的高度等于所有叶子中路径长度最大的叶子的路径长度。调用递归即可完成算法。代码：int GetHeight() return GetHeight(root);template <class T>int BTree<T>:GetHeight(BTNode<T>* t)if(!t)return 0; /若为空节点，则返回0if(!t->lchild)&&(!t->rchild) return 1; /若为叶子节点，则返回1int lHeight=GetHeight(t->lchild);int rHeight=GetH

14、eight(t->rchild);return (lHeight>rHeight?lHeight:rHeight)+1; 算法分析：递归过程中，每个结点都要进入，从下到上累计最大高度，时间复杂度是O（n）；8. 计算二叉树叶子总数如果当前结点是叶子，则返回1，如果不是叶子，则返回左子树叶子和右子树叶子之和。代码：int GetLeaf() return GetLeaf(root);template<class T>int BTree<T>:GetLeaf(BTNode<T> *t)if(!t)return 0;int tmp=0; if(t-&g

15、t;lchild!=NULL) tmp+=GetLeaf(t->lchild); if(t->rchild!=NULL) tmp+=GetLeaf(t->rchild); if(t->lchild=NULL&&t->rchild=NULL) return 1; return tmp;算法复杂度是O（n）。9.释放二叉树占用的内存空间由于二叉树所有结点都是动态申请的，所以程序最后要编写析构函数释放动态内存空间。由于析构函数没有参数，所以在析构函数调用另一个Delete函数完成这个任务。Delete函数中首先判断当前指针参数是不是空，如果空返回（由于多

16、个二叉树对象可能有父子关系，父亲析构后再析构儿子，不判断可能会造成内存无法访问的错误）。然后调用递归先进入叶子结点，删除叶子结点，再一层一层从下往上进行释放空间。代码：BTree() Delete();void Delete() Delete(root); root=NULL; cout<<"释放空间完成"<<endl;template <class T>void BTree<T>:Delete(BTNode<T>* p) if(p=NULL) return; if(p->lchild!=NULL) Dele

17、te(p->lchild); if(p->rchild!=NULL) Delete(p->rchild); delete p;算法分析：每个结点遍历删除一次，时间复杂度是O(n)。实 验 报 告程序测试：运行结果：结果分析：正确实 验 报 告程序二：哈夫曼编码译码系统的实现程序自定义了4个类分别是BTNode类，BinaryTree类HfmTree类,PrioQueue类，类图如下：BTNode类中定义v用来标识当前节点是双亲的左孩子（0）还是右孩子（1），*lChild,*rChild,*parent,用来指向孩子和双亲,value字符用来存放当前结点代表的字符，也可能为空

18、，code数组用来存放当前结点的01编码。并定义了四组重载的构造函数。BinaryTree类中数据成员定义了一个root指针，成员函数包括二叉树构造，先序，中序，后序，层次遍历二叉树，二叉树的清空释放。HfmTree类继承了BinaryTree类，新增了weight数据用来表示当前根节点权值，并把它作为关键字，成员函数新增了为weight的存取，root的置空，CreateCode（）函数对当前哈夫曼树每一个结点产生代码，并存放在每个结点的code数组中。getcode()函数将当前哈夫曼树所有叶子的字符所对应的代码一一打印。FindV（char value）函数找到参数字符对应结点的地址，并

19、返回。CodeToArticle()函数将字符串转换成相应的01代码，GetParents()函数将所有结点的parent赋值为双亲地址。CodeToArticle（）将输入的01代码或者文件中的01代码译码成字符串。程序通过main函数中的switch语句跳转到相应的功能函数中，执行相应的任务。程序定义了一个 哈夫曼树对象Hfm 来实现哈夫曼树中相应的操作，一个w数组保存建树时权值，一个s数组保存建树时字符串。核心功能代码：1. buildtree()函数构建二叉树：函数首先根据提示读入字符串和对应的权值，保存到全局变量s和w中，然后调用CreateHfmTree（）函数创建哈夫曼树，再调用

20、Hfm.GetParents()完成哈夫曼树中结点parent指针赋值，再调用Hfm.CreateCode()完成哈夫曼树中结点code数组来计算结点对应的01编码序列。（1） CreateHfmTree（w,s,num）函数 （B选项）函数定义了一个优先权队列pq，首先将每一个字符和都建成一个哈夫曼树，加入到pq队列中，然后每次取出weight最小的两个哈夫曼树，将他们权值相加建立成新的哈夫曼树，并加入到pq队列中，重复上述操作（n-1）次直到队列剩下一个元素就是建好的哈夫曼树，并返回。代码：template<class T>HfmTree<T> CreateHfmT

21、ree(T w,char s,int n) /构造哈夫曼树int i;PrioQueue<HfmTree<T> > pq(n);HfmTree<T> x, y, z, zero;for(i = 0; i < n; i+)z.MakeTree(wi, si, x ,y);z.putW(wi);pq.Append(z);z.SetNull();for(i = 1; i < n; i+)pq.Serve(x);pq.Serve(y);z.MakeTree(x.getW() + y.getW(),'0', x, y);z.putW(x.g

22、etW() + y.getW();pq.Append(z);z.SetNull();pq.Serve(z);return z;算法分析：将每一个结点建立成树要n次操作，合并树要n-1次操作，一共2*n-1次操作，时间复杂度是O(n)。pq队列最多的时候有n个只包含一个结点的哈夫曼树，空间复杂度是O(n)。（2） GetParents（）函数完成parent指针赋值调用递归，如果为空返回，如果当前结点有左孩子，则将左孩子结点的parent赋值为当前结点地址，右孩子同理，然后递归到下一层左孩子和右孩子中。代码：template<class T>void HfmTree<T>

23、:GetParents(BTNode<T> * t) if(!t) return;if(t->lChild!=NULL) t->lChild->parent=t; if(t->rChild!=NULL) t->rChild->parent=t; GetParents(t->lChild); GetParents(t->rChild);算法分析：由于每个结点都要遍历一遍，所以时间复杂度是O(n)（3） CreateCode（）函数BTNode类结点中有个数据成员为vector<int> code 数组，用来存放每一个结点的0

24、1编码，当前结点的左孩子编码比当前结点编码后面多一个0，当前结点右孩子编码比当前结点后面多一个1。根据这个调用递归。当前结点是左孩子还是右孩子已经在maketree时用v标识好了。代码：template<class T>void HfmTree<T>:CreateCode(BTNode<T>* t) if(t=NULL) return ; if(t->parent) for(int i=0;i<t->parent->code.size();i+) t->code.push_back(t->parent->codei)

25、; t->code.push_back(t->v); CreateCode(t->lChild); CreateCode(t->rChild);算法分析：对每个结点都要递归遍历到，每个结点赋值平局情况是n/2次，所以时间复杂度是O(n2)。除了根节点，每个结点都有一个code数组（vector）,平均每个结点code长度是n/2，所以空间复杂度是O(n2)。2. BianLi()函数对当前哈夫曼树进行遍历（T选项）先序，中序，后序，层次遍历算法本报告上面一个程序已经有了，这个地方就不在阐述了。3. Hfm.getcode()函数输出当前编码方案（E选项）调用递归，如果当

26、前递归到的结点是叶子，则首先打印出叶子代表的字符，然后打印出叶子节点的code数组。如果递归到的结点是空，则返回。如果是中间的结点，则递归的下一层左孩子和右孩子。代码：template<class T>void HfmTree<T>:getcode(BTNode<T>* t) if(t=NULL) return; if(t->lChild=NULL)&&(t->rChild=NULL) cout<<t->value<<":" for(int i=0;i<t->code.

27、size();i+) cout<<t->codei; cout<<endl; getcode(t->lChild); getcode(t->rChild);4. ArticleToCode()函数对字符串进行编码(C选项)定义一个string类对象ss用来读取需要翻译的字符串。用for循环，对ss中每一个字符，调用哈夫曼中的FindV（）寻找字符的地址并赋值到p指针，然后打印出p中的code数组。最后写入到文件即可。代码:void ArticleToCode() /Cofstream foutt("textfile.txt");if

28、(!foutt)cout<<"Cannot open textfile.txt!"<<endl;return ;ofstream foutc("codefile.txt");if(!foutc)cout<<"Cannot open codefile.txt!"<<endl;return ;cout<<"Please input the article that you want to code: (end with Enter)"<<endl;

29、getchar();string ss;getline(cin,ss);foutt<<ss;for(int i=0;i<ss.size();i+) BTNode<int> *p=Hfm.FindV(ssi); if(p=NULL) printf("未找到字符 %c n",ssi); continue; for(int j=0;j<p->code.size();j+) printf("%d",p->codej); char cc=p->codej+'0' foutc<<cc;

30、 cout<<endl<<endl; cout<<"Encoding complete."<<endl<<endl;foutt.close();foutc.close();算法分析：对每一个字符都要调用FinV（）函数进行查找，查找的平均情况是找n/2个结点，FindV的时间复杂度是O(n)，字符有n个，综上，时间复杂度是O(n2)。5. CodeToArticle()函数 进行译码 (D选项)定义一个string类ccs用来保存需要进行译码的字符串，如果要输入01进行译码，则ccs用cin读取，如果要对文件译码，

31、则ccs从文件读取。将指针p指向哈夫曼树root，对ccs中字符，如果是0则进入左孩子，如果是1就进入右孩子，如果当前结点是叶子，就将结点代表的字符打印并写入到文件，并将p重置到root继续上述操作。代码：template<class T>void HfmTree<T>:CodeToArticle() CodeToArticle(this->root);template<class T>void HfmTree<T>:CodeToArticle(BTNode<T>* t) ofstream foutr("resultf

32、ile.txt");if(!foutr)cout<<"Cannot open resultfile.txt!"<<endl;return ;char c;ifstream foutc("codefile.txt");if(!foutc)cout<<"Cannot open codefile.txt!"<<endl;return ;cout<<"请输入选项:"<<endl<<"1. 输入01代码进行译码"

33、<<endl<<"2. 对codefile.txt文件中01代码进行译码"<<endl;int choice; string ccs; cin>>choice; if(choice=2) foutc>>ccs; else if(choice=1) cout<<"输入代码,无空格，回车结束"<<endl; string cc; getchar(); cin>>ccs; else return; int i=0; while(i<ccs.size() BTN

34、ode<int> *p=t; while(p->lChild!=NULL|p->rChild!=NULL) if(ccsi='0') p=p->lChild; else p=p->rChild; i+; printf("%c ",p->value); foutr<<(p->value); cout<<endl<<endl;算法分析:对每一个01字符只要进行一次操作(进入孩子或者打印)，所以时间复杂度是O(n).6. Print()打印文件内容（P选项）定义一个string类对

35、象ss，将文件流输入到ss中，然后输出ss中内容即可.代码：void Print() ifstream foutt("textfile.txt");if(!foutt)cout<<"Cannot open textfile.txt!"<<endl;return ;cout<<endl<<"-textfile.txt-"<<endl;string ss;while(foutt>>ss) cout<<ss<<" " cout<<endl<<"-"<<endl;foutt.close();ifstream foutc("codefile.txt");if(!foutc)cout<<"Cannot open codefile