數據結構二叉樹遍歷實驗報告

問題一： 二叉樹遍歷問題描述設輸入該二叉樹的前序序列為：ABC##DE#G##F##HI##J#K##（#代表空子樹）請編程完成下列任務：⑴請根據此輸入來建立該二叉樹，并輸出該二叉樹的前序、中序和后序序列；⑵按層次遍歷的方法來輸出該二叉樹按層次遍歷的序列；⑶求該二叉樹的高度。設計描述1）二叉樹是一種樹形結構，遍歷就是要讓樹中的所有節(jié)點被且僅被訪問一次，即按一定規(guī)律排列成一個線性隊列。二叉（子）樹是一種遞歸定義的結構，包含三個部分：根結點（N）、左子樹（L）、右子樹（R）。根據這三個部分的訪問次序對二叉樹的遍歷進行分類， 總共有 6種遍歷方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉樹的遍歷就是研究這 6種具體的遍歷方案，顯然根據簡單的對稱性，左子樹和右子樹的遍歷可互換，即 NLR與NRL、LNR與RNL、LRN與RLN，分別相類似，因而只需研究 NLR、LNR和LRN三種即可，分別稱為“先序遍歷” 、“中序遍歷”和“后序遍歷” 。采用遞歸方式就可以容易的實現(xiàn)二叉樹的遍歷，算法簡單且直觀。（2）此外，二叉樹的層次遍歷即按照二叉樹的層次結構進行遍歷， 按照從上到下，同一層從左到右的次序訪問各節(jié)點。 遍歷算法可以利用隊列來實現(xiàn)， 開始時將整個樹的根節(jié)點入隊，然后每從隊列中刪除一個節(jié)點并輸出該節(jié)點的值時，都將它的非空的左右子樹入隊，當隊列結束時算法結束。（3）計算二叉樹高度也是利用遞歸來實現(xiàn)： 若一顆二叉樹為空， 則它的深度為0，否則深度等于左右子樹的最大深度加一。3．源程序#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineElemTypecharstructBTreeNode{6ElemTypedata;7structBTreeNode*left;8structBTreeNode*right;};voidCreateBTree(structBTreeNode**T){12charch;13scanf_s("\n%c",&ch);14if(ch=='#')*T=NULL;15else{16(*T)=malloc(sizeof(structBTreeNode));17(*T)->data=ch;18CreateBTree(&((*T)->left));19CreateBTree(&((*T)->right));20}}voidPreorder(structBTreeNode*T){24if(T!=NULL){25printf("%c",T->data);26Preorder(T->left);27Preorder(T->right);28}}voidInorder(structBTreeNode*T){32if(T!=NULL){33Inorder(T->left);34printf("%c",T->data);35Inorder(T->right);36}}voidPostorder(structBTreeNode*T){40if(T!=NULL){41Postorder(T->left);42Postorder(T->right);43printf("%c",T->data);44}}voidLevelorder(structBTreeNode*BT)47{48structBTreeNode*p;49structBTreeNode*q[30];50intfront=0,rear=0;51if(BT!=NULL){52rear=(rear+1)%30;53q[rear]=BT;54}55while(front!=rear){56front=(front+1)%30;57p=q[front];58printf("%c",p->data);59if(p->left!=NULL){60rear=(rear+1)%30;61q[rear]=p->left;62}63if(p->right!=NULL){64rear=(rear+1)%30;65q[rear]=p->right;66}67}}intgetHeight(structBTreeNode*T){71intlh,rh;72if(T==NULL)return0;73lh=getHeight(T->left);74rh=getHeight(T->right);75returnlh>rh?lh+1:rh+1;}voidmain(void){79structBTreeNode*T;80CreateBTree(&T);81printf("前序序列：\n");82Preorder(T);83printf("\n");84printf("中序序列：\n");85Inorder(T);86printf("\n");87printf("后序序列：\n");88Postorder(T);89printf("\n");90printf("層次遍歷序列：\n");91Levelorder(T);92printf("\n");93printf("二叉樹高度：%d\n",getHeight(T));94}運行結果問題二： 哈夫曼編碼、譯碼系統(tǒng)問題描述對一個ASCII編碼的文本文件中的字符進行哈夫曼編碼， 生成編碼文件；反過來，可將編碼文件譯碼還原為一個文本文件（選做） 。從文件中讀入給定的一篇英文短文 （文件為 ASCII編碼，擴展名為 txt）；統(tǒng)計并輸出不同字符在文章中出現(xiàn)的頻率 （空格、換行、標點等不按字符處理）；根據字符頻率構造哈夫曼樹，并給出每個字符的哈夫曼編碼；將文本文件利用哈夫曼樹進行編碼，存儲成編碼文件（編碼文件后綴名.huf）進行譯碼，將比較。（選做）

huf

文件譯碼為

ASCII

編碼的

txt

文件，與原

txt

文件進行2. 設計描述（1）統(tǒng)計并輸出不同字符在文章中出現(xiàn)的頻率，通過建立兩個數組chs_freq 來實現(xiàn)，chs存儲文件中出現(xiàn)過的字符， chs_freq

chs和（初始化為全 0）存儲對應字符在文件中出現(xiàn)的頻數，當掃描一個字符時，先與chs中已有字符進行比較，若數組中存在該字符，則將該字符對應頻數加1，否則則將該字符加入數組，并頻數加 1。（2）根據字符頻率構造哈夫曼樹， 即將chs_freq 數組作為權值數組， 建立哈夫曼樹，為了方便后續(xù)操作，為結構體 BtreeNode添加一個新的成員變量symbol，建立二叉樹時用以存儲對應權值的字符。3）通過最優(yōu)二叉樹（哈夫曼樹）輸出每個字符的哈夫曼編碼，是利用遞歸實現(xiàn)的，訪問非葉子節(jié)點時，分別向左右子樹遞歸調用，并將分支上的01編碼保存到數組a對應元素中，向下一層len++。訪問到非葉子節(jié)點時輸出其保存在數組中的編碼序列，并將其保存至哈夫曼編碼文件orde.code。4）將文本文件利用哈夫曼樹進行編碼：每從文本文件中讀取一個字符，則在哈夫曼編碼文件order.code查找該字符，查找到后將該字符對應哈夫曼編碼寫入編碼后文件order.huf。并將order.code文件指針重新指向開頭，準備對下一個字符進行操作。3．源程序#include<stdio.h>#include<stdlib.h>typedefintElemType;structBTreeNode{5ElemTypedata;6structBTreeNode*left;7structBTreeNode*right;8charsymbol;9};10voidCountChar(FILE*fp,char*chs,int*ch_freq){11intnum=0;12inti,tmp;13charch=fgetc(fp);14while(ch!=EOF)15{16if((ch>64&&ch<91)||(ch>96&&ch<123)){17for(tmp=0;tmp<=num;tmp++)18{19if(ch==chs[tmp]){ch_freq[tmp]++;break;}20if(tmp==num){chs[num]=ch;ch_freq[num]++;num++;break;}21}22}23ch=fgetc(fp);24}25chs[num]='\0';26for(i=0;i<num;i++)printf("%c%d\n",chs[i],ch_freq[i]);}structBTreeNode*CreateHuffman(ElemTypea[],intn,charss[]){29inti,j;30structBTreeNode**b,*q;31q=malloc(sizeof(structBTreeNode));32b=malloc(n*sizeof(structBTreeNode*));33for(i=0;i<n;i++){34b[i]=malloc(sizeof(structBTreeNode));35b[i]->data=a[i];b[i]->left=b[i]->right=NULL;b[i]->symbol=ss[i];36}37for(i=1;i<n;i++){38intk1=-1,k2;39for(j=0;j<n;j++){40if(b[j]!=NULL&&k1==-1){k1=j;continue;}41if(b[j]!=NULL){k2=j;break;}42}43for(j=k2;j<n;j++){44if(b[j]!=NULL){45if(b[j]->data<b[k1]->data){k2=k1;k1=j;}46elseif(b[j]->data<b[k2]->data)k2=j;47}48}49q=malloc(sizeof(structBTreeNode));50q->data=b[k1]->data+b[k2]->data;51q->left=b[k1];q->right=b[k2];52b[k1]=q;b[k2]=NULL;53}54free(b);55returnq;};voidHuffCoding(structBTreeNode*FBT,intlen){58staticinta[50];59chartmp;60FILE*fp;61inti;62if(len==0)fp=fopen("order.code","w");63if((fp=fopen("order.code","a"))==NULL){printf("文件打開失敗！64if(FBT!=NULL){65if(FBT->left==NULL&&FBT->right==NULL){66printf("%c霍夫曼編碼為：",FBT->symbol);67fputc(FBT->symbol,fp);68fputc('\t',fp);69for(i=0;i<len;i++){70printf("%d",a[i]);71tmp=a[i]+48;72fputc(tmp,fp);73}74printf("\n");fputc('\n',fp);75}76else{77a[len]=0;HuffCoding(FBT->left,len+1);78a[len]=1;HuffCoding(FBT->right,len+1);79}80}81fclose(fp);}voidTransCode(FILE*src){84FILE*fp1,*fp2;85charch1,ch2;86if((fp1=fopen("order.code","r"))==NULL){printf("文件打開失?。?7if((fp2=fopen("order.huf","w"))==NULL){printf("文件打開失??！88fseek(src,0L,SEEK_SET);89ch1=fgetc(src);90ch2=fgetc(fp1);91while(ch1!=EOF)92{93if((ch1>64&&ch1<91)||(ch1>96&&ch1<123)){94while(ch2!=EOF){95if(ch2==ch1){96fgetc(fp1);9