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

数据结构二叉树遍历实验报告-精品--精品--精品-数据结构二叉树遍历实验报告全文共13页，当前为第7页。问题一：数据结构二叉树遍历实验报告全文共13页，当前为第7页。问题描述设输入该二叉树的前序序列为：ABC##DE#G##F##HI##J#K##（#代表空子树）请编程完成下列任务：请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列；按层次遍历的方法来输出该二叉树按层次遍历的序列；求该二叉树的高度。设计描述（1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。数据结构二叉树遍历实验报告全文共13页，当前为第1页。（2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树数据结构二叉树遍历实验报告全文共13页，当前为第1页。（3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。数据结构二叉树遍历实验报告全文共13页，当前为第2页。3数据结构二叉树遍历实验报告全文共13页，当前为第2页。12345678910111213141516171819202122232425262728293031323334353637数据结构二叉树遍历实验报告全文共13页，当前为第3页。数据结构二叉树遍历实验报告全文共13页，当前为第3页。394041424344454647484950515253545556575859数据结构二叉树遍历实验报告全文共13页，当前为第4页。数据结构二叉树遍历实验报告全文共13页，当前为第4页。616263646566676869707172737475767778798081数据结构二叉树遍历实验报告全文共13页，当前为第5页。数据结构二叉树遍历实验报告全文共13页，当前为第5页。838485868788899091929394#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineElemTypecharstructBTreeNode{ ElemTypedata; structBTreeNode*left; structBTreeNode*right;};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){ 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); returnlh>rh?lh+1:rh+1;}voidmain(void){ structBTreeNode*T; CreateBTree(&T); printf("前序序列：\n"); Preorder(T); printf("\n"); printf("中序序列：\n"); Inorder(T); printf("\n"); printf("后序序列：\n"); Postorder(T); printf("\n"); printf("层次遍历序列：\n"); Levelorder(T); printf("\n"); printf("二叉树高度：%d\n",getHeight(T));}4.运行结果数据结构二叉树遍历实验报告全文共数据结构二叉树遍历实验报告全文共13页，当前为第6页。问题二：哈夫曼编码、译码系统问题描述对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件（选做）。从文件中读入给定的一篇英文短文（文件为ASCII编码，扩展名为txt）；统计并输出不同字符在文章中出现的频率（空格、换行、标点等不按字符处理）；根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；将文本文件利用哈夫曼树进行编码，存储成编码文件（编码文件后缀名.huf）进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。（选做）设计描述统计并输出不同字符在文章中出现的频率，通过建立两个数组chs和chs_freq来实现，chs存储文件中出现过的字符，chs_freq（初始化为全0）存储对应字符在文件中出现的频数，当扫描一个字符时，先与chs中已有字符进行比较，若数组中存在该字符，则将该字符对应频数加1，否则则将该字符加入数组，并频数加1。根据字符频率构造哈夫曼树，即将chs_freq数组作为权值数组，建立哈夫曼树，为了方便后续操作，为结构体BtreeNode添加一个新的成员变量symbol，建立二叉树时用以存储对应权值的字符。通过最优二叉树（哈夫曼树）输出每个字符的哈夫曼编码，是利用递归实现的，访问非叶子节点时，分别向左右子树递归调用，并将分支上的01编码保存到数组a对应元素中，向下一层len++。访问到非叶子节点时输出其保存在数组中的编码序列，并将其保存至哈夫曼编码文件orde.code。将文本文件利用哈夫曼树进行编码：每从文本文件中读取一个字符，则在哈夫曼编码文件order.code查找该字符，查找到后将该字符对应哈夫曼编码写入编码后文件order.huf。并将order.code文件指针重新指向开头，准备对下一个字符进行操作。数据结构二叉树遍历实验报告全文共13页，当前为第8页。3数据结构二叉树遍历实验报告全文共13页，当前为第8页。123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657数据结构二叉树遍历实验报告全文共13页，当前为第9页。5数据结构二叉树遍历实验报告全文共13页，当前为第9页。5960616263646566676869707172737475767778798081828384858687888990919293949596979899100101数据结构二叉树遍历实验报告全文共13页，当前为第10页。数据结构二叉树遍历实验报告全文共13页，当前为第10页。103104105106107108109110111112113114115116117118119120121122123124125126127128129#include<stdio.h>#include<stdlib.h>typedefintElemType;structBTreeNode{ ElemTypedata; structBTreeNode*left; structBTreeNode*right; charsymbol;};voidCountChar(FILE*fp,char*chs,int*ch_freq){ intnum=0; inti,tmp; charch=fgetc(fp); while(ch!=EOF) { if((ch>64&&ch<91)||(ch>96&&ch<123)){ 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;i<num;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;i<n;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;i<n;i++){ intk1=-1,k2; for(j=0;j<n;j++){ if(b[j]!=NULL&&k1==-1){k1=j;continue;} if(b[j]!=NULL){k2=j;break;} } for(j=k2;j<n;j++){ if(b[j]!=NULL){ if(b[j]->data<b[k1]->data){k2=k1;k1=j;} elseif(b[j]->data<b[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; } free(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;i<len;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((ch1>64&&ch1<91)||(ch1>96&&ch1<123)){ while(ch2!=EOF){ if(ch2==ch1){ fgetc(fp1); ch2=fgetc(fp1); whi