數(shù)據(jù)結構二叉樹遍歷實驗報告

1、問題一:二叉樹遍歷1 .問題描述設輸入該二叉樹的前序序列為：ABC#DE#G#F#HI#J#K踴代表空子樹）請編程完成下列任務：請根據(jù)此輸入來建立該二叉樹，并輸出該二叉樹的前序、中序和后序序列；按層次遍歷的方法來輸出該二叉樹按層次遍歷的序列；求該二叉樹的高度。2 .設計描述（1）二叉樹是一種樹形結構，遍歷就是要讓樹中的所有節(jié)點被且僅被訪問一次，即按一定規(guī)律排列成一個線性隊列。二叉（子）樹是一種遞歸定義的結構，包含三個部分：根結點（N）、左子樹（L）、右子樹（R）。根據(jù)這三個部分的訪問次序對二叉樹的遍歷進行分類，總共有6種遍歷方案：NLRLNRLRNNRLRNL和LNR研究二叉樹的遍歷就是研究這

2、6種具體的遍歷方案，顯然根據(jù)簡單的對稱性，左子樹和右子樹的遍歷可互換，即NLR與NRLLNR與RNLLRN與RLN分別相類似，因而只需研究NLRLNR和LRN三種即可，分別稱為“先序遍歷”、“中序遍歷”和“后序遍歷”。采用遞歸方式就可以容易的實現(xiàn)二叉樹的遍歷，算法簡單且直觀。（2）止匕外，二叉樹的層次遍歷即按照二叉樹的層次結構進行遍歷，按照從上到下，同一層從左到右的次序訪問各節(jié)點。遍歷算法可以利用隊列來實現(xiàn)，開始時將整個樹的根節(jié)點入隊，然后每從隊列中刪除一個節(jié)點并輸出該節(jié)點的值時，都將它的非空的左右子樹入隊，當隊列結束時算法結束。（3）計算二叉樹高度也是利用遞歸來實現(xiàn)：若一顆二叉樹為空，則它的

3、深度為0,否則深度等于左右子樹的最大深度加一。123456783 .源程序#include<>#include<>#include<>#defineElemTypecharstructBTreeNodeElemTypedata;structBTreeNode*left;structBTreeNode*right;910111213141516171819202122232425262728293031323334353637383940414243444546；voidCreateBTree(structBTreeNode*T)charch;scanf_s(

4、"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(s

5、tructBTreeNode*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)474849505152535455565758596061626364656667686970717273747

6、576777879808182structBTreeNode*p;structBTreeNode*q30;intfront=0,rear=0;if(BT!=NULL)rear=(rear+1)%30;qrear=BT;while(front!=rear)front=(front+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;intget

7、Height(structBTreeNode*T)intlh,rh;if(T=NULL)return0;lh=getHeight(T->left);rh=getHeight(T->right);returnlh>rhlh+1:rh+1;voidmain(void)structBTreeNode*T;CreateBTree(&T);printf("前序序列：n");Preorder(T);printf("n");printf("中序序列：n");838485868788899091Inorder(T);prin

8、tf("n");printf("后序序列：n");Postorder(T);printf("n");printf("層次遍歷序列：n");Levelorder(T);printf("n");printf("二叉樹高度：dn", getHeight(T);9293944.運行結果問題二：哈夫曼編碼、譯碼系統(tǒng)1 .問題描述對一個ASCI編碼的文本文件中的字符進行哈夫曼編碼，生成編碼文件；反過來，可將編碼文件譯碼還原為一個文本文件（選做）。從文件中讀入給定的一篇英文短文（文件為AS

9、CII編碼，擴展名為txt）;統(tǒng)計并輸出不同字符在文章中出現(xiàn)的頻率（空格、換行、標點等不按字符處理）；根據(jù)字符頻率構造哈夫曼樹，并給出每個字符的哈夫曼編碼；將文本文件利用哈夫曼樹進行編碼，存儲成編碼文件（編碼文件后綴名.huf）進行譯碼，將huf文件譯碼為ASCII編碼的txt文件，與原txt文件進行比較。（選做）2 .設計描述（1）統(tǒng)計并輸出不同字符在文章中出現(xiàn)的頻率，通過建立兩個數(shù)組chs和chs_freq來實現(xiàn)，chs存儲文件中出現(xiàn)過的字符，chs_freq（初始化為全0）存儲對應字符在文件中出現(xiàn)的頻數(shù)，當掃描一個字符時，先與chs中已有字符進行比較，若數(shù)組中存在該字符，則將該字符對應頻

10、數(shù)加1,否則則將該字符加入數(shù)組，并頻數(shù)加1。（2）根據(jù)字符頻率構造哈夫曼樹，即將chs_freq數(shù)組作為權值數(shù)組，建立哈夫曼樹，為了方便后續(xù)操作，為結構體BtreeNode添加一個新的成員變量symbol,建立二叉樹時用以存儲對應權值的字符。（3）通過最優(yōu)二叉樹（哈夫曼樹）輸出每個字符的哈夫曼編碼，是利用遞歸實現(xiàn)的，訪問非葉子節(jié)點時，分別向左右子樹遞歸調用，并將分支上的01編碼保存到數(shù)組a對應元素中，向下一層len+。訪問到非葉子節(jié)點時輸出其保存在數(shù)組中的編碼序列，并將其保存至哈夫曼編碼文件。（4）將文本文件利用哈夫曼樹進行編碼：每從文本文件中讀取一個字符，則在哈夫曼編碼文件查找該字符，查找到

11、后將該字符對應哈夫曼編碼寫入編碼后文件。并將文件指針重新指向開頭，準備對下一個字符進行操作。3 .源程序1234#include<>#include<>typedefintElemType;structBTreeNodeElemTypedata;structBTreeNode*left;7891011121314151617181920212223242526272829303132333435363738394041424344454647484950structBTreeNode*right;charsymbol;voidCountChar(FILE*fp,char

12、*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=chstmp)ch_freqtmp+;break;if(tmp=num)chsnum=ch;ch_freqnum+;num+;break;ch=fgetc(fp);chsnum=''0'for(i=0;i<num;i+)printf("%c%

13、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;i<n;i+)bi=malloc(sizeof(structBTreeNode);bi->data=ai;bi->left=bi->right=NULL;bi->symbol=ssi;for(i=1;i&l

14、t;n;i+)intk1=-1,k2;for(j=0;j<n;j+)if(bj!=NULL&&k1=-1)k1=j;continue;if(bj!=NULL)k2=j;break;for(j=k2;j<n;j+)if(bj!=NULL)if(bj->data<bk1->data)k2=k1;k1=j;elseif(bj->data<bk2->data)k2=j;q=malloc(sizeof(structBTreeNode);q->data=bk1->data+bk2->data;5152535455565758

15、596061626364656667686970717273747576777879808182838485868788899091929394q->left=bk1;q->right=bk2;bk1=q;bk2=NULL;free(b);returnq;；voidHuffCoding(structBTreeNode*FBT,intlen)staticinta50;chartmp;FILE*fp;inti;if(len=0)fp=fopen("","w");if(fp=fopen("","a")=NUL

16、L)printf("文件打開失?。f(FBT!=NULL)if(FBT->left=NULL&&FBT->right=NULL)printf("%c霍夫曼編碼為："，F(xiàn)BT->symbol);fputc(FBT->symbol,fp);fputc('t',fp);for(i=0;i<len;i+)printf("%d",ai);tmp=ai+48;fputc(tmp,fp);printf("n");fputc('n',fp);elsealen=0

17、;HuffCoding(FBT->left,len+1);alen=1;HuffCoding(FBT->right,len+1);fclose(fp);voidTransCode(FILE*src)FILE*fp1,*fp2;charch1,ch2;if(fp1=fopen("","r")=NULL)printf("文件打開失??！if(fp2=fopen("","w")=NULL)printf("文件打開失敗!fseek(src,0L,SEEK_SET);ch1=fgetc(src)

18、;ch2=fgetc(fp1);while(ch1!=EOF)n");exit(1);n");exit(1);n");exit(1);if(ch1>64&&ch1<91)|(ch1>96&&ch1<123)while(ch2!=EOF)9596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129if(ch2=ch1)fgetc(fp1);ch2=fgetc(fp1);wh

19、ile(ch2!='n')fputc(ch2,fp2);ch2=fgetc(fp1);fputc('t',fp2);break;ch2=fgetc(fp1);if(ch2=EOF)printf("未找到對應編碼！n");rewind(fp1);ch2=fgetc(fp1);ch1=fgetc(src);fclose(fp1);fclose(fp2);voidmain(void)charchs100;intch_freq100=0;structBTreeNode*T;FILE*fp;if(fp=fopen("","r")=NULL)printf("文件打開失??！n");exi