实验三二叉树的基本运算.doc

中原工学院 数据结构实验报告软件 111-臧丽实验三 二叉树的基本运算一、实验目的与实验内容1.实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。2.实验内容建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；(选做)4. 将二叉树每个结点的左右子树交换位置。（选做）二、程序设计1.总体设计int n=0; /全局变量typedef struct BiTNode /二叉树节点定义char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void CreateBiTree(BiTree &T); /创建二叉树int Visit(char e); /打印函数int PreOrderTraverse(BiTree T); /先序遍历二叉树int InOrderTraverse(BiTree T); / 中序遍历二叉树 int PostOrderTraverse(BiTree T); / 后序遍历二叉树void LevelOrderTraverse(BiTree T); /层次遍历二叉树int Nodesum(BiTree &T); /二叉树节点总数int BiTreeDepth(BiTree T ); / 返回二叉树的深度void LeafCount(BiTree T); /统计叶子数并输出叶子结点typedef struct QNode /队列节点定义BiTree bt;struct QNode *next;QNode,*QueuePtr; struct LinkQueue /队列类型定义QueuePtr front; /队头指针QueuePtr rear; /队尾指针;void InitQueue(LinkQueue &Q); / 构造一个空队列 Q int EmptyQueue(LinkQueue &Q); /判断队列是否空void EnQueue(LinkQueue &Q,BiTree &e );/ 进队void DeQueue(LinkQueue &Q,BiTree &e );/出队void DestroyQueue(LinkQueue *Q); /销毁队列2详细设计l void CreateBiTree(BiTree &T)函数是用来先序建立二叉树ch= if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(1);T-data=ch;CreateBiTree(T-lchild); CreateBiTree(T-rchild);T=NULL;图表 1l void LevelOrderTraverse(BiTree T)是用来层次遍历二叉树。在函数中，开辟一个树结点指针数组，用来存放遍历到的元素地址，且使B0=T，用来存放树根if(Bi-lchild)Bj=Bi-lchild;j+; if(Bi-rchild) Bj=Bi-rchild;j+; i+ilchild); h2=BiTreeDepth(T-rchild);if(h1h2)return h1+1;elsereturn h2+1;return 0图表 33，调试及问题解决二叉树涉及到队列的基本操作，还需要先序，中序遍历，后序遍历，层次遍历，涉及的到的知识面广，需要了解各个方面，还要对二叉树的逻辑结构进行详细的了解并掌握。初步完编程的工作时，在输入二叉树的发现只能输入一个字符，而且程序不再进行，最后是自己的不小心将语句char a; scanf(%c,&a);中的%c写为%d导致的。在编写元素入栈和出栈的时候，程序报如下的错误：语法有错误。，经过检查原来是定义的时候的类型使用错/测试代码int main()printf(*1.先序建立一个二叉树*n);printf(*2.先序遍历二叉树 *n);printf(*3.中序遍历二叉树 *n);printf(*4.后序遍历二叉树 *n);printf(*5.层次遍历二叉树 *n);printf(*6.二叉树总结点数 *n);printf(*7.二叉树深度 *n);printf(*8.统计叶子数并输出叶子结点*n);printf(*其他键退出 *n);printf(*请选择你的功能 *n);int a;BiTree T;while(1)scanf(%d,&a);switch(a)case 1:scanf(%c,&a);CreateBiTree (T);break; case 2:printf(先序遍历二叉树:);PreOrderTraverse (T);break;case 3:printf(中序遍历二叉树:);InOrderTraverse (T);break;case 4:printf(后序遍历二叉树:);PostOrderTraverse (T);break;case 5:printf(层次遍历二叉树:);LevelOrderTraverse(T);break; case 6:printf(二叉树的总结点:);Nodesum(T);printf(%dn,n);break;case 7:printf(二叉树的深度:);printf(%dn,BiTreeDepth(T);break;case 8:printf(二叉树的叶子节点:);LeafCount(T); printf(n);default:exit(0);return 0;运行时会出现窗口如图表四图表 4当选择1来建立二叉树，输入如：abcdegf（其中表示空格字符），就此建立一个二叉树，当一次输入2,3,4,5时，对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；运行如图表5所示图表 5在上面的基础上，依次输入6,7,8时，出现图表6，二叉树的深度，结点数目，叶结点数目依次显示出来图表 6三源代码#include#include#includehead.hvoid CreateBiTree(BiTree &T) /先序建立二叉树char ch;scanf(%c,&ch);if (ch= ) T=NULL; else if (!(T=(BiTNode *)malloc(sizeof(BiTNode)exit(1);T-data=ch;CreateBiTree(T-lchild); CreateBiTree(T-rchild); int Visit(char e)printf(%c ,e);return 0;int PreOrderTraverse(BiTree T)/先序遍历二叉树if(T) printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); return 0;int InOrderTraverse(BiTree T) / 中序遍历二叉树 if(T)InOrderTraverse(T-lchild);printf(%c,T-data); InOrderTraverse(T-rchild); return 0; int PostOrderTraverse(BiTree T) /后序遍历二叉树if(T) PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);printf(%c,T-data); return 0;void LevelOrderTraverse(BiTree T)/层次遍历二叉树BiTNode *B100;/树结点指针数组，用于存放遍历到的元素地址if(T=NULL)printf(空的二叉树n);B0=T; /存入树根int i;int j=1; /j为总结点for(i=0;ilchild) /如果有左孩子，存入地址，j加1 Bj=Bi-lchild;j+; if(Bi-rchild) /如果有右孩子，存入地址，j加1 Bj=Bi-rchild;j+; for(i=0;idata);int Nodesum(BiTree &T) /二叉树节点总数if(T)n+;Nodesum(T-lchild);Nodesum(T-rchild);return n;int BiTreeDepth(BiTree T) /二叉树深度 int h1,h2; if(T=NULL)return 0; else h1=BiTreeDepth(T-lchild); h2=BiTreeDepth(T-rchild); if(h1h2)return h1+1;elsereturn h2+1; void LeafCount(BiTree T) /统计叶子数并输出叶子结点int count=0;if(T) if(T-lchild=NULL&T-rchild=NULL) count+;printf(%c,T-data); LeafCount(T-lchild);LeafCount(T-rchild);void InitQueue(LinkQueue &Q) /构造一个空队列 Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(1); / 存储空间分配失败Q.front-next=NULL; int EmptyQueue(LinkQueue &Q) /判断队列是否空if(Q.front=Q.rear)return 1;elsereturn 0;void EnQueue(LinkQueue &Q,BiTree &e )/ 进队QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(1); p-bt=e; p-next=NULL;Q.rear-next=p; Q.rear=p; void DeQueue(LinkQueue &Q,BiTree &e )/出队if(Q.front=Q.rear) exit(0); QueuePtr p=Q.front-next; e=p-bt; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); void DestroyQueue(LinkQueue *Q) /销毁队列 while (Q-front) Q-rear=Q-front-next;free(Q-front);Q-front=Q-rear;实验四 哈夫曼树与哈夫曼编码一、实验目的与实验内容1.实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。2.实验内容1问题描述已知n个字符在原文中出现的频率，求它们的哈夫曼编码。2.基本要求1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。（具体算法可参见教材P147的算法6.12）2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。3.选作内容3. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符0和1确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。4. 打印Huffman树。二、程序设计1.总体设计typedef structint weight;/权值 int parent; /双亲 int LChild; /左孩子 int RChild;/右孩子HTNode, *HuffmanTree;/动态分配数组存储哈夫曼树typedef char *HuffmanCode;/动态分配数组存储哈夫曼编码表void InitHuffmanTree(HuffmanTree ht, int w, int n);/初始化哈夫曼树void CrtHuffmanTree(HuffmanTree ht, int n); /构造哈夫曼树 void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n);/从叶子到根逆向编码void select(HuffmanTree HT,int n,int & s1,int &s2); /选择两个最小的根数s1,s2,按左小右大的规则(s1s2)void PrintHuffmanTree(HuffmanTree ht); /打印哈夫曼树的状态(Weight Parent Lchild Rchild)void PrintHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n);/打印哈夫曼编码方案int i=1i=nhti.weight= wi;hti.parent = 0; hti.LChild = 0; hti.RChild = 0;2.详细设计l void InitHuffmanTree(HuffmanTree ht, int w, int n) 函数用来初始化哈夫曼树falsei+int m = 2*n-1; i=n+1i=mfalsehti.weight=0;hti.parent=0;hti.LChild = 0; hti.RChild = 0;i+图表 7l void CrtHuffmanTree(HuffmanTree ht, int n)函数用来创建哈夫曼树i+int i=n+1i=mselect(ht, i-1, s1, s2); hti.weight = hts1.weight + hts2.weight; hts1.parent = i; hts2.parent = i; hti.LChild = s1; hti.RChild = s2;false图表 8int i=1l void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n) 函数用来从叶子到根逆向求每个字符的哈弗曼编码，在此函数中用for循环语句，while循环语句，if判断语句。用malloc分配求编码的工作空间，然后用for循环语句逐个字符求哈弗曼编码，且是从叶子到根逆向求编码lfalsei=nstart=n-1;c=I;p=hti.parent;while(p!=0) -start; if (htp.LChild = c) chstart = 0; else chstart = 1; c = p; p = htp.parent; c = p; p = htp.parent;hci=(char*)malloc(n-start)*sizeof(char); strcpy(hci, &chstart); i+图表 9l void select(HuffmanTree HT,int n,int & s1,int &s2)函数是用来选择两个最小的根数s1,s2,按左小右大的规则(s1s2)，且parent节点为0.i+int i=1i=nif(!HTi.parent)s1=i; break;for(i+;i=n;i+)if(!HTi.parent)s2=i;break;if(HTs1.weight-HTs2.weight)int temp;temp=s1;s1=s2;s2=temp;for(i=1;i=n;i+)if(!HTi.parent)if(HTi.weightHTs1.weight)s2=s1;s1=i;else if(HTi.weightHTs2.weight&i!=s1) s2=i;false图表 103.调试及问题解决在此次试验中需要掌握树的逻辑结构,哈夫曼树的定义及生成算法,哈夫曼编码的方法. 在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是若没有定义所引用的相关头文件，必定调试不通过；通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。 这次课程设计，我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存数据，对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏，我的程序有了更高的质量。u 运行窗口1即图表11为哈夫曼树的初始状态图表 11u 运行窗口2即图表12为哈夫曼树的终态图表 12u 窗口3即图表13为哈夫曼编码方案图表 13u 测试函数int main(void) HTNode htM+1;char * hcN+1; int wN+1 = 5,29,7,8,14,23,3,11; InitHuffmanTree(ht, w, N); /调用哈弗曼初始化函数printf( 哈夫曼树的初态n);PrintHuffmanTree(ht); /调用哈弗曼树打印函数CrtHuffmanTree(ht,N);printf( 哈夫曼树的终态n);PrintHuffmanTree(ht); CrtHuffmanCode(ht, hc, N); PrintHuffmanCode(ht, hc, N); return 0; 三源代码#include#include #include #includehead.h #define N 8/N为叶节点个数 #define M 2*N-1void InitHuffmanTree(HuffmanTree ht, int w, int n) /初始化哈夫曼树 for (int i=1; i=n; i+) /1n单元存放叶节点,初始化 hti.weight = wi; hti.parent = 0; hti.LChild = 0; hti.RChild = 0; int m = 2*n-1; for (i=n+1; i=m; i+) /n+1m单元存放非叶节点,初始化 hti.weight = 0; hti.parent = 0; hti.LChild = 0; hti.RChild = 0; void CrtHuffmanTree(HuffmanTree ht, int n) /创建哈夫曼树int s1, s2, m; m = 2*n-1; /n+1m单元存放叶节点 /*创建非叶节点,建哈夫曼树*/ for (int i=n+1; i=m; i+) select(ht, i-1, s1, s2); /筛选权值之和最小的2个树 hti.weight = hts1.weight + hts2.weight; hts1.parent = i; hts2.parent = i;hti.LChild = s1; hti.RChild = s2; void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n) /从叶子到根逆向求每个字符的哈弗曼编码 char *ch; int start; int c,p; ch = (char*)malloc(n+1)*sizeof(char); /分配求编码的工作空间 chn-1 = 0;/编码结束符 for(int i=1; i=n; i+) /逐个字符求哈弗曼编码 start=n-1;/编码结束位置 c=i; p=hti.parent; while(p!=0)/从叶子到根逆向求编码 -start; if (htp.LChild = c) chstart = 0; /左分支标0 else chstart = 1; /右分支标1 c = p; p = htp.parent; /向上倒推 hci=(char*)ma