二叉樹的存儲與實現(xiàn)

1、 實 驗 報 告實驗課程名稱 數(shù)據(jù)結(jié)構(gòu)與算法 實驗項目名稱 二叉樹的存儲與實現(xiàn) 年 級 08 級 專 業(yè) 數(shù) 學(xué) 類 學(xué)生姓名 學(xué) 號 理 學(xué) 院實驗時間： 年 月 日學(xué)生實驗室守則一、按教學(xué)安排準(zhǔn)時到實驗室上實驗課，不得遲到、早退和曠課。二、進入實驗室必須遵守實驗室的各項規(guī)章制度，保持室內(nèi)安靜、整潔，不準(zhǔn)在室內(nèi)打鬧、喧嘩、吸煙、吃食物、隨地吐痰、亂扔雜物，不準(zhǔn)做與實驗內(nèi)容無關(guān)的事，非實驗用品一律不準(zhǔn)帶進實驗室。三、實驗前必須做好預(yù)習(xí)（或按要求寫好預(yù)習(xí)報告），未做預(yù)習(xí)者不準(zhǔn)參加實驗。四、實驗必須服從教師的安排和指導(dǎo)，認真按規(guī)程操作，未經(jīng)教師允許不得擅自動用儀器設(shè)備，特別是與本實驗無關(guān)的儀器設(shè)備

2、和設(shè)施，如擅自動用或違反操作規(guī)程造成損壞，應(yīng)按規(guī)定賠償，嚴(yán)重者給予紀(jì)律處分。五、實驗中要節(jié)約水、電、氣及其它消耗材料。六、細心觀察、如實記錄實驗現(xiàn)象和結(jié)果，不得抄襲或隨意更改原始記錄和數(shù)據(jù)，不得擅離操作崗位和干擾他人實驗。七、使用易燃、易爆、腐蝕性、有毒有害物品或接觸帶電設(shè)備進行實驗，應(yīng)特別注意規(guī)范操作，注意防護；若發(fā)生意外，要保持冷靜，并及時向指導(dǎo)教師和管理人員報告，不得自行處理。儀器設(shè)備發(fā)生故障和損壞，應(yīng)立即停止實驗，并主動向指導(dǎo)教師報告，不得自行拆卸查看和拼裝。八、實驗完畢，應(yīng)清理好實驗儀器設(shè)備并放回原位，清掃好實驗現(xiàn)場，經(jīng)指導(dǎo)教師檢查認可并將實驗記錄交指導(dǎo)教師檢查簽字后方可離去。九、無

3、故不參加實驗者，應(yīng)寫出檢查，提出申請并繳納相應(yīng)的實驗費及材料消耗費，經(jīng)批準(zhǔn)后，方可補做。十、自選實驗，應(yīng)事先預(yù)約，擬訂出實驗方案，經(jīng)實驗室主任同意后，在指導(dǎo)教師或?qū)嶒灱夹g(shù)人員的指導(dǎo)下進行。十一、實驗室內(nèi)一切物品未經(jīng)允許嚴(yán)禁帶出室外，確需帶出，必須經(jīng)過批準(zhǔn)并辦理手續(xù)。學(xué)生所在學(xué)院： 理學(xué)院 專業(yè)： 數(shù)學(xué)類 班級：08級姓 名學(xué) 號實驗組實驗時間指導(dǎo)教師成 績實驗項目名稱二叉樹的存儲與實現(xiàn)實驗?zāi)康募耙螅簝?nèi)容：二叉樹的存儲和基本操作（2學(xué)時）、二叉樹的應(yīng)用（Huffman樹和Huffman編碼，2學(xué)時）。要求：通過實驗，要求學(xué)生掌握用二叉鏈表存儲結(jié)構(gòu)實現(xiàn)二叉樹的表示方法，并能實現(xiàn)其基本運算：二叉鏈

4、表建立及其它有關(guān)處理，在此基礎(chǔ)上實現(xiàn)Huffman樹和Huffman編碼。要求掌握樹的編程，加深理解遞歸的原理。實驗硬件及軟件平臺： 計算機，VC+平臺。實驗步驟：1. 選擇菜單“開始/程序/Microsoft Visual Studio 6.0/Microsoft Visual C+ 6.0”,得到Visual C+ 6.0啟動后的用戶界面； 2. 創(chuàng)建一個新工程； 3. 編寫一個簡單的C+源程序，并保存； 4. 編譯連接和運行程序。實驗內(nèi)容（包括實驗具體內(nèi)容、算法分析、源代碼等等）：程序（1）如下：該二叉樹為課本127頁圖6.8（b）#include #include #include #

5、include #include #define SIZE 100using namespace std;typedef struct BiTNode /定義二叉樹節(jié)點結(jié)構(gòu)char data; /數(shù)據(jù)域struct BiTNode *lchild,*rchild; /左右孩子指針域BiTNode,*BiTree;int visit(BiTree T);void CreateBiTree(BiTree &T); /生成一個二叉樹void PreOrder(BiTree); /遞歸先序遍歷二叉樹void InOrder(BiTree); /遞歸中序遍歷二叉樹void PostOrder(BiTre

6、e); /遞歸后序遍歷二叉樹/主函數(shù)void main()BiTree T; char j;int flag=1;/-程序解說-printf(本程序?qū)崿F(xiàn)二叉樹的操作。n);printf(葉子結(jié)點以空格表示。n);printf(可以進行建立二叉樹，遞歸先序、中序、后序遍歷。n);printf(n);printf(請建立二叉樹。n);printf(建樹將以三個空格后回車結(jié)束。n);printf(例如:1 2 3 4 5 6 (回車)n); CreateBiTree(T); /初始化隊列 printf(建立二叉樹已經(jīng)完畢！n);printf(請輸入遍歷的flag:);getchar();while(

7、flag) printf(n); printf(請選擇: n); printf(1.遞歸先序遍歷n); printf(2.遞歸中序遍歷n); printf(3.遞歸后序遍歷n); printf(0.退出程序n); scanf( %c,&j); switch(j) case 1: if(T) printf(遞歸先序遍歷二叉樹:); PreOrder(T); printf(n); else printf(二叉樹為空!n); break; case 2: if(T) printf(遞歸中序遍歷二叉樹:); InOrder(T); printf(n); else printf(二叉樹為空!n); br

8、eak; case 3: if(T) printf(遞歸后序遍歷二叉樹:); PostOrder(T); printf(n); else printf(二叉樹為空!n); break; default: flag=0; printf(程序運行結(jié)束，按任意鍵退出!n); /建立二叉樹void CreateBiTree(BiTree &T)char ch;scanf(%c,&ch); /讀入一個字符 if(ch= ) T=NULL; /為什么這里一定是空格才可以呢 其他字符就不可以！ else T=(BiTNode *)malloc(sizeof(BiTNode); /生成一個新結(jié)點 T-data

9、=ch;/生成根結(jié)點 CreateBiTree(T-lchild); /構(gòu)造左子樹 CreateBiTree(T-rchild); /構(gòu)造右子樹/先序遍歷的遞歸void PreOrder(BiTree T)if(T) printf(%c ,T-data); /訪問結(jié)點 PreOrder(T-lchild); /遍歷左子樹 PreOrder(T-rchild); /遍歷右子樹/中序遍歷的遞歸void InOrder(BiTree T)if(T) InOrder(T-lchild); /遍歷左子樹 printf(%c ,T-data); /訪問結(jié)點 InOrder(T-rchild); /遍歷右子

10、樹/后序遍歷的遞歸void PostOrder(BiTree T)if(T) PostOrder(T-lchild); /遍歷左子樹 PostOrder(T-rchild); /遍歷右子樹 printf(%c ,T-data);/訪問結(jié)點int visit(BiTree T)if(T) printf(%c ,T-data); return 1;else return 0;程序（2）如下：/HuffmanTree#include #include #include typedef structunsigned int weight;unsigned int parent,lchild,rchil

11、d;HTNode,*HuffmanTree;/哈夫曼樹的存儲結(jié)構(gòu)typedef char *HuffmanCode;/動態(tài)分配數(shù)組存儲哈夫曼編碼表int min(HuffmanTree t,int i)int j,flag;unsigned int k=999;for(j=1;j=i;j+)if(tj.weightk & tj.parent=0)k=tj.weight;flag=j;tflag.parent=1;return flag;void select(HuffmanTree t,int i,int &s1,int &s2) s1=min(t,i);s2=min(t,i);return

12、;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)int m,i,s1,s2,start;unsigned c,f;HuffmanTree p;char *cd;if(n=1)return ;m=2*n-1;HT=(HuffmanTree) malloc (m+1)*sizeof(HTNode);for(p=HT+1,i=1;i=n;+i,+p,+w)(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;for(;i=m;+i,+p)(*p).parent

13、=0;for(i=n+1;i=m;+i)select(HT,i-1,s1,s2);HTi.lchild=s1;HTi.rchild=s2;HTs1.parent=i;HTs2.parent=i;HTi.weight=HTs1.weight+HTs2.weight;/從葉子到根逆向求每個字符的哈夫曼編碼HC=(HuffmanCode) malloc (n+1)*sizeof(char*);/分配n個字符編碼的頭指針向量（0不用）cd=(char*)malloc(n*sizeof(char);cdn-1=0;for(i=1;i1): );scanf(%d,&n);w=(int *)malloc(n*sizeof(int);printf(請依次輸入%d個權(quán)值（整型）:n,n);for(i=0;i=n-1;i+)scanf