數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷實驗報告

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

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

3、用遞歸來實現(xiàn)：若一顆二叉樹為空，則它的深度為0，否則深度等于左右子樹的最大深度加一。3源程序12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include #include #include #define ElemType charstruct BTreeNode ElemType d

4、ata;struct BTreeNode* left;struct BTreeNode* right;void CreateBTree(struct BTreeNode* T)char ch;scanf_s(n%c, &ch);if (ch = #) *T = NULL;else (*T) = malloc(sizeof(struct BTreeNode);(*T)-data = ch;CreateBTree(&(*T)-left);CreateBTree(&(*T)-right); void Preorder(struct BTreeNode* T)if (T != NULL) printf

5、(%c , T-data);Preorder(T-left);Preorder(T-right);void Inorder(struct BTreeNode* T)if (T != NULL) Inorder(T-left);printf(%c , T-data);Inorder(T-right);void Postorder(struct BTreeNode* T)if (T != NULL) Postorder(T-left);Postorder(T-right);printf(%c , T-data);void Levelorder(struct BTreeNode* BT)struct

6、 BTreeNode* p;struct BTreeNode* q30;int front=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;int getHeight(struct BTreeNode* T)int lh

7、,rh;if (T = NULL) return 0;lh = getHeight(T-left);rh = getHeight(T-right);return lhrh ? lh + 1 : rh + 1;void main(void)struct BTreeNode* 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);pri

8、ntf(n);printf(二叉樹高度：%dn, getHeight(T);4.運行結(jié)果問題二： 哈夫曼編碼、譯碼系統(tǒng)1. 問題描述對一個ASCII編碼的文本文件中的字符進行哈夫曼編碼，生成編碼文件；反過來，可將編碼文件譯碼還原為一個文本文件（選做）。v 從文件中讀入給定的一篇英文短文（文件為ASCII編碼，擴展名為txt）；v 統(tǒng)計并輸出不同字符在文章中出現(xiàn)的頻率（空格、換行、標點等不按字符處理）；v 根據(jù)字符頻率構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼；v 將文本文件利用哈夫曼樹進行編碼，存儲成編碼文件（編碼文件后綴名.huf）v 進行譯碼，將huf文件譯碼為ASCII編碼的txt文件，與

9、原txt文件進行比較。（選做）2. 設(shè)計描述（1） 統(tǒng)計并輸出不同字符在文章中出現(xiàn)的頻率，通過建立兩個數(shù)組chs和chs_freq來實現(xiàn)，chs存儲文件中出現(xiàn)過的字符，chs_freq（初始化為全0）存儲對應(yīng)字符在文件中出現(xiàn)的頻數(shù)，當掃描一個字符時，先與chs中已有字符進行比較，若數(shù)組中存在該字符，則將該字符對應(yīng)頻數(shù)加1，否則則將該字符加入數(shù)組，并頻數(shù)加1。（2） 根據(jù)字符頻率構(gòu)造哈夫曼樹，即將chs_freq數(shù)組作為權(quán)值數(shù)組，建立哈夫曼樹，為了方便后續(xù)操作，為結(jié)構(gòu)體BtreeNode添加一個新的成員變量symbol，建立二叉樹時用以存儲對應(yīng)權(quán)值的字符。（3） 通過最優(yōu)二叉樹（哈夫曼樹）輸出每

10、個字符的哈夫曼編碼，是利用遞歸實現(xiàn)的，訪問非葉子節(jié)點時，分別向左右子樹遞歸調(diào)用，并將分支上的01編碼保存到數(shù)組a對應(yīng)元素中，向下一層len+。訪問到非葉子節(jié)點時輸出其保存在數(shù)組中的編碼序列，并將其保存至哈夫曼編碼文件orde.code。（4） 將文本文件利用哈夫曼樹進行編碼：每從文本文件中讀取一個字符，則在哈夫曼編碼文件order.code查找該字符，查找到后將該字符對應(yīng)哈夫曼編碼寫入編碼后文件order.huf。并將order.code文件指針重新指向開頭，準備對下一個字符進行操作。3源程序123456789101112131415161718192021222324252627282930

11、313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129#include #include typedef int ElemType;struct BTreeNode ElemType data;st

12、ruct BTreeNode* left;struct BTreeNode* right;char symbol;void CountChar(FILE *fp,char* chs,int* ch_freq) int num = 0;int i,tmp;char ch = 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

13、+; break; ch = fgetc(fp);chsnum=0;for (i = 0; i num; i+) printf(%c %dn, chsi, ch_freqi);struct BTreeNode* CreateHuffman(ElemType a, int n,char ss) int i, j;struct BTreeNode *b, *q;q = malloc(sizeof(struct BTreeNode);b = malloc(n*sizeof(struct BTreeNode*);for (i = 0; i data = ai; bi-left = bi-right =

14、 NULL;bi-symbol = ssi;for (i = 1; i n; i+) int k1 = -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 data data) k2 = k1; k1 = j; else if (bj-data data) k2 = j;q = malloc(sizeof(struct BTreeNode);q-data = bk1-data + bk2-data;q-left =

15、 bk1; q-right = bk2;bk1 = q; bk2 = NULL;free(b);return q;void HuffCoding(struct BTreeNode* FBT, int len) static int a50;char tmp;FILE *fp;int i;if(len = 0) fp=fopen(order.code,w);if(fp=fopen(order.code,a) = NULL) printf(文件打開失?。);exit(1);if (FBT != NULL) if (FBT-left = NULL & FBT-right = NULL) print

16、f(%c霍夫曼編碼為：, FBT-symbol);fputc(FBT-symbol,fp);fputc(t,fp);for (i = 0; i left, len + 1);alen = 1; HuffCoding(FBT-right, len + 1);fclose(fp);void TransCode(FILE *src) FILE *fp1,*fp2;char ch1,ch2;if(fp1=fopen(order.code,r) = NULL) printf(文件打開失??！n);exit(1);if(fp2=fopen(order.huf,w) = NULL) printf(文件打開失敗

17、！n);exit(1);fseek(src,0L,SEEK_SET);ch1 = fgetc(src);ch2 = fgetc(fp1);while (ch1 != EOF)if (ch164 & ch196 & ch1123) while(ch2 != EOF) if(ch2 = ch1)fgetc(fp1);ch2=fgetc(fp1);while(ch2!=n)fputc(ch2,fp2);ch2=fgetc(fp1); fputc(t,fp2);break;ch2 = fgetc(fp1);if(ch2 = EOF) printf(未找到對應(yīng)編碼!n);rewind(fp1);ch2 = fgetc(fp1);ch1 = fgetc(src);fclo