廈門理工學院數(shù)據(jù)結構試驗6

1、數(shù)據(jù)結構實驗報告學號姓名ZRZ專業(yè)、班18計卓1班實驗地點指導教師林仙麗實驗時間2020.5.12實驗序號：6實驗項LI名稱：樹和二義樹的操作實驗目的及要求1、進一步掌握指針變量、動態(tài)變量的含義。2、掌握二叉樹的結構特征，以及各種存儲結構的特點及適用范圉。3、掌握用指針類型描述、訪問和處理二義樹的運算。4、掌握用二叉樹前序、中序、后序、層次遍歷的方法。二、實驗設備（環(huán)境）及要求微型計算機；windows操作系統(tǒng)：Microsoft Visual Studio 6.0 集成開發(fā)環(huán)境。三、實驗內(nèi)容與步驟1 根據(jù)P129的方法，將a*b-（c+d*e/f）+g）轉化為表達式二叉樹（繪圖），并寫出表達

2、式 二叉樹的前序、中序和后序遍歷順序。先丿丫: -*ab+c*d/efg中序：a*b-c+d*e/f+g后序:ab*cdef/*+g+-2.鏈式表表示和實現(xiàn)二義樹如下：#include include #define max 50typedef struct liuyuint data;struct liuyu *lchild, *rchild;/test;liuyu *root, *p, *q Lmaxj;int sum二0;int m=sizeof(test);void insert_data(int x)/*生成二叉排序樹*/liuyu *p, *q, *s;s=(test*)mallo

3、c(m);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s;p=root;while (p)/*如何接入二叉排序樹的適當位置*/q=p;if (p-data=x)printf(，?data already exist! n);return;else if(xdata)p=p-lchild;elsep=p-rchild;if(xdata)q-lchild=s;elseq-rchild=s;void mainO/*先生成二叉排序樹*/int i, x;i=l ；:root二NULL;/*千萬別忘了賦初值給root!*/doprintf (pl

4、ease input data%d： i);i+;scanf (Wd, &x);/*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結朿*/if (x=-9999) printf C?nNow output data value:n?，);elseinsert_data(x);/*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!二-9999);改寫以上程序，并實現(xiàn)功能如下：(任選兩題實現(xiàn))1) .編寫函數(shù)實現(xiàn)前序、中序和后序遍歷。2) .分別編寫函數(shù)實現(xiàn)訃算所有結點及葉子結點的個數(shù)。3) .編寫函數(shù)實現(xiàn)按值查找功能。4) .編寫函數(shù)實現(xiàn)求二義樹的高度。圖2：二叉樹代碼效果圖實驗說明： 編寫函數(shù)實現(xiàn)前序、中序和后

5、序遍歷：這一部分的思路主要就是進行一個 遞歸的操作，我們從根結點開始向下遍歷，根據(jù)前療:、中序、后序的不同特點選 擇性的對左右子結點和父結點的值進行輸出，就可以達到三種不同的遍歷效果。例如先序遍歷，我們就可以先打印當前根結點的值，然后再對當前根結點的 左子結點進行遞歸，然后再對右結點進行遞歸，這樣就能實現(xiàn)打印順序為根結點, 然后左結點，最后右結點的操作，另外的中序和后序只需要將三條語句的順序進 行交換即可。void DLR(Tree* root):if (root != NULL):；printf(%droot-data);!DLR(root-lchild);:DLR(root-rchild)

6、;:圖3：先序遍歷代碼 分別編寫函數(shù)實現(xiàn)計算所有結點及葉子結點的個數(shù)：其實這一部分與上面 的二義樹遍歷很相似，遍歷二義樹的過程我們完全可以想象為就是對二義樹進行 一個結點的計數(shù)，而葉子結點實際上只需要加入一個特殊判斷即可，即左右結點 都為空就可以記為葉子結點。同樣的，我們可以使用遞歸來實現(xiàn)這個功能是最好 的。Node_count(root-lchild); Node_count(root-rchild); node+;return;圖4：結點計算核心代碼 編寫函數(shù)實現(xiàn)按值查找功能：同樣，查找值的功能只需要對二義樹遍歷的 部分就行修改就行，一旦找到對應的值就返回即可。 編寫函數(shù)實現(xiàn)求二義樹的高度

7、：這一部分我們可以釆用dfs的思想，只要 從根結點開始不斷的對左右向下遍歷，最后比較左右的深度大小，取最大值即可if (!root)return 0;return max(get_height(root-lchild) get_height(rootrchild) + 1;圖5：深度il算核心代碼3、用Huffman編碼方法，實現(xiàn)對通信字符的編碼和解碼。Ol MKrosoft V6ua! StucloX第1次: 第2次: 第3次: 第4次: 弟5次:6次: 第7次:m）/r. “點X1權值為1取出的右“點也丈出的WMcl權值為1如出的右“點也2出的左力點門權備為1 燦的左廿點x車侑為2 幅I的

8、左卄點權值為2R出的左1點“權i為31它創(chuàng)的父 弋值為：2 1它tn的父竹點取值為:2 2它們的父仃點權值為:3 2它們的父仃點權値為:4:4它們的父竹點權備為:7為：岀的右廿點x2 乂值為：岀的右廿點x2權值為：出的右也點x2灼i為:出的右W點x2 5（他為: 一ll出的右廿點x2權”i為： . IUII的左廿點玖權值為5 敢出的右也加2板値為:7它門的父W/AKffi為：212(5(2,3), 7(3(1,2(h 1, 4(2(1 1). 2)i的編碼為:碼加 u的軸碼為】 合的編碼為 J的編碼為9 f JK：00 0110010101011 1100 1101111請購入耍解碼的1100

9、1010101101111100110111100011100 1010 1011 01 111 100 1101 111 00 01 Just do it圖6：輸入字符串原碼來實現(xiàn)HuffmanTreeSI Microsoft Visual Studio if試占諂綸入些購入鄉(xiāng)一. 訥軻入第1個了符H 諂輸入樂1個7捋的權0. 19 諂輪入第2個7符1 諂輸入第2個了符的權10.21 諂軻入第3個7符o 諂輸入第3個7符的權0.0】 諂輪入第4個字符 諂輸入第4個了符的權（0.01 諂輸入曲5個了符.諂輸入第5個7符的權仇0. 03 請輸入第6個字符!諂輸入第6個了符的權值0. 06 說軻入

10、曲7個了符請輸入笫7個字符的ttfrto. 16BI輸入弟8個r;:riff輸入8個符的權值016 謚輸入心9個丫符d諸輸入第9個丫符的權值007諸輸入用10個丫符諸輸入用10個？ 第1次:.拯的權frtO. 1取出的A：廿點權值為001 取;I；的/irUxlKfrt為0 02 阪出的左力點*1權備為0.05 取出的左節(jié)點xltttfi M 07 JR出的左節(jié)點xlttffiM 11 取岀的左北點xl(fi為016 取出的烷竹點“權值為0.19 取出的左1*點xlttffi為027一販出的左*Jxl權值為0.4 I1(0.40.19.0. 21),0.6(0. 27(0.11(0.05(0.

11、02(0.01,0.01),0.03),0.06)0.0 33(0.16.0.17(0.07.0.1)H仙編構為I 】的編碼為| o的編碼為】 的編碼Z .的編碼為 !的編碼為、 x的編碼為I 啲編碼為 d的編碼為的編碼為】諂輸入要解碼的字符申 I 001000010101100000100111111101000001010111101000100 100001 01 01 100000 1001 1111 110 100000 101 01 1110 10001 Hello! world.射次:TkOSV00 01 100000 100001 10001 1001101110 1110 1

12、111取出的右“點*2儀值為:取:加2權值為: 取出的右竹點*2找備為： 取出的右m2權值為： 取出的右為: 取出的右U點找值為: 恥II的右曲點x2ttffi為： 取：為：=?。簗步點x2權值為：06它劄的父廿點權価為二10.01它們的父點權値為:0.02 0. 03它們的父“點權值為:0.05 0. 06佗幻的父廿點權值為:0.110.1它們的父點權仮為:0.170.16它幻的父卄點權值為:0.270.17它們的父“點權值為:0.33 0.21它Y的父“點嘆值為：0.40. 33它Y】的父廿點乂值為：0.6隸聯(lián)跚牆谿煽鏟倆辟怦弊躊爐點弩.聯(lián)制偶踹亦”.圖7：輸入權值來實現(xiàn)HuffmanTr

13、ee1 DB Mkrsoft Visual Studio fliXUWJfeS一X諂輸人113sada dsd r取III的右紡點工2權值為】取岀的右節(jié)點*2權值為,2它們的父節(jié)點權值為，3 取出的右節(jié)點工2權值知2它們的父節(jié)點權值為4 取出的右節(jié)點工2權值為I 2它們的父廿點權血為* 4 取川的右肖點冷3它們的父“點權値為:6 取HI的右百點x2HMi 4它們的父節(jié)點權値為x 8 取出的右節(jié)點*2權值為I 8它們的父節(jié)點權值為* 14第1次:取山的好節(jié)點P權値為】 第2次:取出的左節(jié)點燈權垃為1 第3次:取出的左節(jié)Axlttffl為2 第4次:取出的亞節(jié)點xlttffl為2 第5次:取川的左

14、節(jié)點xlttffl為3 第6次:取川的左節(jié)點xlttfft為4 新次:取出的左節(jié)點工】權值為614(6(3(1,2, 3, 8(4(2,2，4(2,2(1,1”劇齡黙聽能2x的編碼為：0009的編碼為* 001 d的編碼為】01 1的編碼加】00 a的編碼為：101的編碼為X 1103的編碼為:1110 g的編碼為:1111 - 110 1110 1111 01 000 3gdr諂輸入耍解碼的7符小I 1101110111101000圖&可以同時輸入數(shù)字、字符、空格、符號實驗說明： ：首先，要想構造出HuffmanTree,我們需要對輸入的字符權值進行處理, 這里山于主要的輸入方式為輸入字符串

15、，通過相應的函數(shù)來計算每個字符的占比 權值或者是直接輸入每個字符的權值兩種方式，相應的處理方式有略微的不同， 但是大體是一致的,我定義了一個double類型的weight數(shù)組來存放字符的權值, 然后再定義了一個code數(shù)組來存放侮個不重復的字符，這樣就能解決當用戶輸 入字符串時，就算有大量重復字符也能訃算出正確的權值，得到完整的權值后， 我們就可以開始構建HuffmanTreeo 首先我們根據(jù)code數(shù)組的大小來建立相應數(shù)量的HuffmanTree結點，同 時也要對這些結點進行初始化，然后我們建立一個HuffmanTree結點類型的優(yōu)先 隊列6根據(jù)結點的權值從小到大進行內(nèi)部排序，這樣就為我們下

16、一步正式構建 HuffmanTree做好準備，我們每次將q中最前面的兩個元素拿出進行合并，這樣 實現(xiàn)了每次合并結點都是權值最小的結點進行合并，然后我們將兩個結點合并后 的結點再次放入q隊列中，這樣循環(huán)直到q中只剩一下一個元素根節(jié)點，這樣一 棵HuffmanTree就構造完畢了。 HuffmanTree構造完畢后，我們可以利用遞歸函數(shù)來對HuffmanTree進行 遍歷，這樣做的目的是可以將每個字符的編碼進行打印，同時我們也可以模擬 HuffmanTree樹將每個結點的權值打印出來，這樣可以更直觀的看到 HuffmanTree內(nèi)部的構建T青況。 解碼的過程只需要根據(jù)輸入的密文對HuffmanTr

17、ee樹進行遍歷，從根結點 和密文的第一位，如果當前一位是則當前結點山根結點變成根結點的左節(jié) 點，如果當前一位是T則當前結點山根結點變成根結點的右節(jié)點，就這樣直 到根結點沒有左右結點時，我們再將這個節(jié)點中保存的字符打印出來，就實現(xiàn)了 一個字符的解碼，要繼續(xù)解碼的話只需要X前結點更新回最原本的根結點即可。四、分析與討論在這一次的實驗中，我學到了許多關于二義樹的知識，先是通過表達二叉 樹和二義樹的一些基本操作了解并明口了二義樹的原理，也體會到了二義樹中遞 歸思想的美妙，然后就是通過HuffmanTree樹對樹形結構有了更深的體會，也理 解了 HuffmanTree樹編碼和解碼的原理，讓我收獲了很多。

18、五、教師評語成績簽名:日期:附源程序淸單:2.include include typedef struct Treeint data;struct Tree* lchild, * rchild;Node;Tree* root,字 p, * q;int leaf = 0;int node = 0;int m = sizeof (Node);bool findflag = false;int height = 0;int max(int a, int b)if (a b)return a;elsereturn b;void insert_data(int/*生成二叉排序樹*/Tree * s;s

19、= (Node*)malloc(m);p = (Node*)malloc(m):q = (Node*)malloc(m):sdata = x;s-lchild = NULL;s-rchild = NULL;if (!root)root = s;return;p = root;while (p)/*如何接入二叉排序樹的適當位豆*/q = p;if (p-data = x)printf Cdata already exist! n):return;else if (x data)p = p-lchild;elsep = p*rchild;sdata = x;if (x data)q-lchild

20、= s;elseqrchild = s;void DLR(Tree* root)if (root != NULL)printf(%d 、 rootdata):DLR(rootlchiId);DLR (roofrchi Id);void LDR(Tree* root)if (root != NULL)LDR(rootlchiId);printf(%d 、 rootdata):LDR(rootrchiId);void LRD(Tree* root)if (root != NULL)LRD(root-lchiId);LRD(rootrchiId); printf(%d 、 rootdata):voi

21、d Xode_count(Tree* root)if (!root)return;if (!rootlchild & !root*rchild) node+;return;elseNodecount(rootlchild);Node_count(rootrchild); node+;return;void LeafNode_count(Tree* root)if (!root)return;if (!root-lchild & !rootrchild) leaf+;return;elseLeafNode_count(rootlchild);LeafNode_count(rootrchild);

22、return;int findvalue(int value,Tree* root)if (root != NULL)if (roofdata = value)findflag = true; return 0;elsefind_va1ue(va1ue, rootlchild); find_value(value, root-rchild);intget_height(Tree* root)if (!root)return 0;returnmax(get_height(root-lchild), get_height(rootrchiId) + 1;intmainO/*先生成二叉排序樹*/in

23、t i,i = 1；rootroot(Node*)malloc(m);NULL;/*千萬別忘了賦初值給wot!*/printf (please input data%d: i):i卄;scanf_s(%d &x);if (x = -9999) printf CnNow output data value：n): /*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結束*/elseinsert_data(X) ;/*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/ while (x != -9999);printfC先序遍歷為：“)；DLR(root);printf Cn r);printfC中序遍歷為:)；LDR(root);

24、printf Cn *);printfC后序遍歷為:LRD(root);printf Cn *);Nodecount(root);LeafNodecount(root);printfC這個二叉樹中的結點為：%d葉子結點為:%dn, node, leaf); int value;printf(諳輸入要查找的值：)；scanf_s C%d, &value);find_value(value, root);if (!findflag)printf (，z%d值在二叉樹中找不到rT, value);elseprintf (%d值在二叉樹中能找到n, value);findflag = false;pr

25、intf(請輸入要查找的值：)；scanf_s C%d, &value);find_value(value, root);if (!findflag)printf (%d值在二叉樹中找不到n value);elseprintf C%d值在二叉樹中能找到n, value);findflag = false;printfC 二叉樹髙度為：get_height (root):3.Sinclude i?include#include#includeJJinclude#includeSineludeSincludeSineludeusing namespace std;vector code;doubl

26、e weight256:int n;typedef struct HuffTreestring code:char symbol;double weight:HuffTree* lchild;HuffTree* rchild; Node, *odeptr;struct cmpbool operator()(Nodeptr & a, Nodeptr & b)return a-weight bweight;priority_queueNodeptrr vector, cmpq;void codework()cout ”歡迎使用霍夫曼樹” endl;cout 請選抒輸入字符串原碼或者輸入權值：” e

27、ndl;cout1 輸入原碼2輸入權值 endl;int x;cin x;char ch=getchar();systemCcls);switch (x)case 1:string s:cout 請輸入原碼：；getline(cin, s):for (int i = 0; i num;for (int i = 0; i y;if (count (code begin0, codeend(), x) = 0) code push_back(x);weightx= y;break;void PrintHuffmanTree(Nodeptr root)cout root-weight:if (roo

28、t-lchild != NULL | root-rchild != NULL)coutPrintHuffmanTree(rootlchild);cout,;PrintHuffmanTree(rootrchild);cout;Nodeptr CreatHuffmanTree 0codework ();n = code sizeO ;for (int i = 0; i symbol = code .i;CurNodeweight = weight.code .iCurNode-lchild = NULL;CurNode-rchild = NULL;q push (CurNode);for (int

29、 i = 1; i weight 取 出的右節(jié)點x2權值為： (double)x2-weight 它們的父節(jié)點權值為：weight + x2weight) endl;/zrz 2020.5. 20Nodeptr NewNode = new Node;NewNode*symbol = 0;NewNode*weight = xlweight + x2weight;NewNodelchild = xl;NewNode*rchild = x2;q push(NewNode);PrintHuffmanTree (q topO);cout endl:return q topO ;void Coding(Nodeptr