《数据结构二叉树遍历实验报告》由会员分享，可在线阅读，更多相关《数据结构二叉树遍历实验报告（10页珍藏版）》请在金锄头文库上搜索。
1、问题一：二叉树遍历之马矢奏春创作1.时间：二0二一年七月二十九日2问题描述设输入该二叉树的前序序列为：ABC#DE#G#F#HI#J#K#（#代表空子树）请编程完成下列任务：请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列；按条理遍历的方法来输出该二叉树按条理遍历的序列；求该二叉树的高度.3.设计描述（1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定例律排列成一个线性队列.二叉（子）树是一种递归界说的结构，包括三个部份：根结点（N）、左子树（L）、右子树（R）.根据这三个部份的访问次第对二叉树的遍历进行分类，总共有6种遍历方案：NLRLNRLRNN
2、RLRNL和LNR.研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性左子树和右子树的遍历可互换，即NLR与NRLLNR与RNLLRN与RLN,分别相类似，因而只需研究NLRLNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”.采纳递归方式就可以容易的实现二叉树的遍历，算法简单且直观.(2) 另外,二叉树的条理遍历即依照二叉树的条理结构进行遍历,依照从上到下，同一层从左到右的次第访问各节点.遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队,当队列结束时算法结束.(3) 计算二叉树
3、高度也是利用递归来实现：若一颗二叉树为空则它的深度为0,否则深度即是左右子树的最年夜深度加一.3.源法式1#inelude2#inelude3#include4#defineElemTypechar5struetBTreeNode6ElemTypedata;7struetBTreeNode*left;8struetBTreeNode*right;9；10voidCreateBTree(structBTreeNode*T)1112ehareh;13scanf_s(n%e,&eh);14if(eh=#)*T=NULL;15else16(*T)=malloc(sizeof(structBTreeNo
4、de);17(*T)-data=eh;18CreateBTree(&(*T)-left);19CreateBTree(&(*T)-right);202122voidPreorder(struetBTreeNode*T)232425262728293031323334353637383940414243444546474849505152535455565758596061if(T!=NULL)printf(%c,T-data);Preorder(T-left);Preorder(T-right);voidInorder(structBTreeNode*T)if(T!=NULL)Inorder(
5、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)structBTreeNode*p;structBTreeNode*q30;intfront=0,rear=0;if(BT!=NULL)rear=(rear+1)%30;qrear=BT;while(front!=rear)front=(front+
6、1)%30;p=qfront;printf(%c,p-data);if(p-left!=NULL)rear=(rear+1)%30;qrear=p_left;if(p-right!=NULL)rear=(rear+1)%30;qrear=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);pri
7、ntf(前序序列：n);Preorder(T);printf(n”);printf(中序序列：n);Inorder(T);printf(n”);printf(后序序列：n);Postorder(T);printf(n”);printf(条理遍历序列：n);Levelorder(T);printf(n”);printf(二叉树高度：%dn,getHeight(T);6263646566676869707172737475767778798081828384858687888990919293944.运行结果问题二：哈夫曼编码、译码系统1问题描述对一个ASCII编码的文本文件中的字符进行哈夫曼编码
8、，生成编码文件；反过来，可将编码文件译码还原为一个文本文件（选做）.?从文件中读入给定的一篇英文短文（文件为ASCII编码,扩展名为txt）；?统计并输出分歧字符在文章中呈现的频率（空格、换行、标点等不按字符处置）；?根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；?将文本文件利用哈夫曼树进行编码，存储成编码文件（编码文件后缀名.huf）?进行译码，将huf文件译码为ASCII编码的txt文件,与原txt文件进行比力（选做）2.设计描述（1）统计并输出分歧字符在文章中呈现的频率，通过建立两个时间：二0二一年七月二十九日数组chs和chs_freq来实现，chs存储文件中呈现过的字符,ch
9、s_freq（初始化为全0）存储对应字符在文件中呈现的频数，当扫描一个字符时，先与chs中已有字符进行比力若数组中存在该字符，则将该字符对应频数加1,否则则将该字符加入数组，并频数加1.根据字符频率构造哈夫曼树，即将chs_freq数组作为权值数组，建立哈夫曼树，为了方便后续把持，为结构体BtreeNode添加一个新的成员变量symbol,建立二叉树时用以存储对应权值的字符.（3）通过最优二叉树（哈夫曼树）输出每个字符的哈夫曼编码，是利用递归实现的，访问非叶子节点时，分别向左右子树递归调用，并将分支上的01编码保管到数组a对应元素中向下一层len+.访问到非叶子节点时输出其保管在数组中的编码序
10、列，并将其保管至哈夫曼编码文件orde.code.（4）将文本文件利用哈夫曼树进行编码：每从文本文件中读取一个字符，则在哈夫曼编码文件order.code查找该字符，查找到后将该字符对应哈夫曼编码写入编码后文件order.huf.并将order.code文件指针重新指向开头，准备对下一个字符进行把持.3.源法式1#include2#include3typedefintElemType;4structBTreeNode时间：二二O二一年七月二十九日567891011121314151617181920212223242526272829303132333435363738394041424344
11、45464748ElemTypedata;structBTreeNode*left;structBTreeNode*right;charsymbol;voidCountChar(FILE*fp,char*chs,int*ch_freq)intnum=0;inti,tmp;charch=fgetc(fp);while(ch!=EOF)if(ch64&ch96&ch123)for(tmp=0;tmp=num;tmp+)if(ch=chstmp)ch_freqtmp+;break;if(tmp=num)chsnum=ch;ch_freqnum+;num+;break;ch=fgetc(fp);chs
12、num=0;for(i=0;inum;i+)printf(%c%dn,chsi,ch_freqi);structBTreeNode*CreateHuffman(ElemTypea,intn,charss)inti,j;structBTreeNode*b,*q;q=malloc(sizeof(structBTreeNode);b=malloc(n*sizeof(structBTreeNode*);for(i=0;idata=ai;bi-left=bi-right=NULL;bi-symbolfor(i=1;in;i+)intk1=-1,k2;for(j=0;jn;j+)if(bj!=NULL&k
13、1=-1)k1=j;continue;if(bj!=NULL)k2=j;break;for(j=k2;jdatadata)k2=k1;k1=j;elseif(bj-datadata)k2=j;4950515253545556575859606162636465666768697071727374757677787980818283848586878889909192q=malloc(sizeof(structBTreeNode);q-data=bk1-data+bk2-data;q-left=bk1;q-right=bk2;bk1=q;bk2=NULL;free(b);returnq;void
14、HuffCoding(structBTreeNode*FBT,intlen)staticinta50;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,ai);tmp=ai+48;fputc(tmp,fp);printf(n);fputc(n,fp);else
