數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷實(shí)驗(yàn)報(bào)告

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

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

3、也是利用遞歸來實(shí)現(xiàn)：若一顆二叉樹為空，則它的深度為0，否則深度等于左右子樹的最大深度加一。3源程序12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include <stdio.h>#include <stdlib.h>#include <malloc.h&g

4、t;#define ElemType charstruct BTreeNode ElemType data;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)->

5、;left);CreateBTree(&(*T)->right); void Preorder(struct BTreeNode* T)if (T != NULL) printf("%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 P

6、ostorder(struct BTreeNode* T)if (T != NULL) Postorder(T->left);Postorder(T->right);printf("%c ", T->data);void Levelorder(struct BTreeNode* BT)struct 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)% 3

7、0;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,rh;if (T = NULL) return 0;lh = getHeight(T->left);rh = getHeight(T->right);return lh>rh ?

8、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

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

10、將huf文件譯碼為ASCII編碼的txt文件，與原txt文件進(jìn)行比較。（選做）2. 設(shè)計(jì)描述（1） 統(tǒng)計(jì)并輸出不同字符在文章中出現(xiàn)的頻率，通過建立兩個數(shù)組chs和chs_freq來實(shí)現(xiàn)，chs存儲文件中出現(xiàn)過的字符，chs_freq（初始化為全0）存儲對應(yīng)字符在文件中出現(xiàn)的頻數(shù)，當(dāng)掃描一個字符時，先與chs中已有字符進(jìn)行比較，若數(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)值

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

12、192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129#include <stdio.h>#include <stdlib.h>

13、;typedef int ElemType;struct BTreeNode ElemType data;struct 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 (ch>64 && ch<91)|(ch>96 && ch<123) for (tmp = 0; t

14、mp <= 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 %dn", chsi, ch_freqi);struct BTreeNode* CreateHuffman(ElemType a, int n,char ss) int i, j;struct BTreeNode *

15、b, *q;q = malloc(sizeof(struct BTreeNode);b = malloc(n*sizeof(struct BTreeNode*);for (i = 0; i < n; i+) bi = malloc(sizeof(struct BTreeNode);bi->data = ai; bi->left = bi->right = NULL;bi->symbol = ssi;for (i = 1; i < n; i+) int k1 = -1, k2;for (j = 0; j < n; j+) if (bj != NULL &

16、amp;&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; else if (bj->data < bk2->data) k2 = j;q = malloc(sizeof(struct BTreeNode);q->data = bk1->data + bk2->data;q->left = b

17、k1; 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);

18、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", ai);tmp=ai+48;fputc(tmp,fp);printf("n");fputc('n',fp);else alen

19、= 0; HuffCoding(FBT->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("文件打開失??！n");exit(1);fseek(src,0L,SEEK_SET);ch1 = fgetc(src);ch2 = fgetc(fp1);wh