数据结构二叉树遍历实验报告

..问题一：二叉树遍历1.问题描述设输入该二叉树的前序序列为：ABC##DE#G##F##HI##J#K##（#代表空子树）请编程完成下列任务：⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列；⑵按层次遍历的方法来输出该二叉树按层次遍历的序列；⑶求该二叉树的高度。2.设计描述（1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。（2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。（3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。3．源程序12345678#includestdio.h#includestdlib.h#includemalloc.h#defineElemTypecharstructBTreeNode{ElemTypedata;structBTreeNode*left;structBTreeNode*right;..910111213141516171819202122232425262728293031323334353637383940414243444546};voidCreateBTree(structBTreeNode**T){charch;scanf_s(\n%c,&ch);if(ch=='#')*T=NULL;else{(*T)=malloc(sizeof(structBTreeNode));(*T)-data=ch;CreateBTree(&((*T)-left));CreateBTree(&((*T)-right));}}voidPreorder(structBTreeNode*T){if(T!=NULL){printf(%c,T-data);Preorder(T-left);Preorder(T-right);}}voidInorder(structBTreeNode*T){if(T!=NULL){Inorder(T-left);printf(%c,T-data);Inorder(T-right);}}voidPostorder(structBTreeNode*T){if(T!=NULL){Postorder(T-left);Postorder(T-right);printf(%c,T-data);}}voidLevelorder(structBTreeNode*BT)..4748495051525354555657585960616263646566676869707172737475767778798081828384{structBTreeNode*p;structBTreeNode*q[30];intfront=0,rear=0;if(BT!=NULL){rear=(rear+1)%30;q[rear]=BT;}while(front!=rear){front=(front+1)%30;p=q[front];printf(%c,p-data);if(p-left!=NULL){rear=(rear+1)%30;q[rear]=p-left;}if(p-right!=NULL){rear=(rear+1)%30;q[rear]=p-right;}}}intgetHeight(structBTreeNode*T){intlh,rh;if(T==NULL)return0;lh=getHeight(T-left);rh=getHeight(T-right);returnlhrh?lh+1:rh+1;}voidmain(void){structBTreeNode*T;CreateBTree(&T);printf(前序序列：\n);Preorder(T);printf(\n);printf(中序序列：\n);..85868788899091929394Inorder(T);printf(\n);printf(后序序列：\n);Postorder(T);printf(\n);printf(层次遍历序列：\n);Levelorder(T);printf(\n);printf(二叉树高度：%d\n,getHeight(T));}4.运行结果问题二：哈夫曼编码、译码系统1.问题描述对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件（选做）。从文件中读入给定的一篇英文短文（文件为ASCII编码，扩展名为txt）；统计并输出不同字符在文章中出现的频率（空格、换行、标点等不按字符处理）；根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；..将文本文件利用哈夫曼树进行编码，存储成编码文件（编码文件后缀名.huf）进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。（选做）2.设计描述（1）统计并输出不同字符在文章中出现的频率，通过建立两个数组chs和chs_freq来实现，chs存储文件中出现过的字符，chs_freq（初始化为全0）存储对应字符在文件中出现的频数，当扫描一个字符时，先与chs中已有字符进行比较，若数组中存在该字符，则将该字符对应频数加1，否则则将该字符加入数组，并频数加1。（2）根据字符频率构造哈夫曼树，即将chs_freq数组作为权值数组，建立哈夫曼树，为了方便后续操作，为结构体BtreeNode添加一个新的成员变量symbol，建立二叉树时用以存储对应权值的字符。（3）通过最优二叉树（哈夫曼树）输出每个字符的哈夫曼编码，是利用递归实现的，访问非叶子节点时，分别向左右子树递归调用，并将分支上的01编码保存到数组a对应元素中，向下一层len++。访问到非叶子节点时输出其保存在数组中的编码序列，并将其保存至哈夫曼编码文件orde.code。（4）将文本文件利用哈夫曼树进行编码：每从文本文件中读取一个字符，则在哈夫曼编码文件order.code查找该字符，查找到后将该字符对应哈夫曼编码写入编码后文件order.huf。并将order.code文件指针重新指向开头，准备对下一个字符进行操作。3．源程序123456789#includestdio.h#includestdlib.htypedefintElemType;structBTreeNode{ElemTypedata;structBTreeNode*left;structBTreeNode*right;charsymbol;};..1011121314151617181920212223242526272829303132333435363738394041424344454647484950515253voidCountChar(FILE*fp,char*chs,int*ch_freq){intnum=0;inti,tmp;charch=fgetc(fp);while(ch!=EOF){if((ch64&&ch91)||(ch96&&ch123)){for(tmp=0;tmp=num;tmp++){if(ch==chs[tmp]){ch_freq[tmp]++;break;}if(tmp==num){chs[num]=ch;ch_freq[num]++;num++;break;}}}ch=fgetc(fp);}chs[num]='\0';for(i=0;inum;i++)printf(%c%d\n,chs[i],ch_freq[i]);}structBTreeNode*CreateHuffman(ElemTypea[],intn,charss[]){inti,j;structBTreeNode**b,*q;q=malloc(sizeof(structBTreeNode));b=malloc(n*sizeof(structBTreeNode*));for(i=0;in;i++){b[i]=malloc(sizeof(structBTreeNode));b[i]-data=a[i];b[i]-left=b[i]-right=NULL;b[i]-symbol=ss[i];}for(i=1;in;i++){intk1=-1,k2;for(j=0;jn;j++){if(b[j]!=NULL&&k1==-1){k1=j;continue;}if(b[j]!=NULL){k2=j;break;}}for(j=k2;jn;j++){if(b[j]!=NULL){if(b[j]-datab[k1]-data){k2=k1;k1=j;}elseif(b[j]-datab[k2]-data)k2=j;}}q=malloc(sizeof(structBTreeNode));q-data=b[k1]-data+b[k2]-data;q-left=b[k1];q-right=b[k2];b[k1]=q;b[k2]=NULL;}..5455565758596061626364656667686970717273747576777879808182838485868788899091929394959697free(b);returnq;};voidHuffCoding(structBTreeNode*FBT,intlen){staticinta[50];chartmp;FILE*fp;inti;if(len==0)fp=fopen(order.code,w);if((fp=fopen(order.code,a))==NULL){printf(文件打开失败！\n);exit(1);}if(FBT!=NULL){if(FBT-left==NULL&&FBT-right==NULL){printf(%c霍夫曼编码为：,FBT-symbol);fputc(FBT-symbol,fp);fputc('\t',fp);for(i=0;ilen;i++){printf(%d,a[i]);tmp=a[i]+48;fputc(tmp,fp);}printf(\n);fputc('\n',fp);}else{a[len]=0;HuffCoding(FBT-left,len+1);a[len]=1;HuffCoding(FBT-right,len+1);}}fclose(fp);}voidTransCode(FILE*src){FILE*fp1,*fp2;charch1,ch2;if((fp1=fopen(order.code,r))==NULL){printf(文件打开失败！\n);exit(1);}if((fp2=fopen(order.huf,w))==NULL){printf(文件打开失败！\n);exit(1);}fseek(src,0L,SEEK_SET);ch1=fgetc(src);ch2=fgetc(fp1);while(ch1!=EOF){if((ch164&&ch191)||(ch196&&ch1