數(shù)據(jù)結(jié)構(gòu)實驗6.doc

數(shù)據(jù)結(jié)構(gòu)實驗報告實驗序號：6 實驗項目名稱：樹和二叉樹的操作學(xué)號姓名專業(yè)、班實驗地點指導(dǎo)教師實驗時間一、實驗?zāi)康募耙?、進一步掌握指針變量、動態(tài)變量的含義。2、掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點及適用范圍。3、掌握用指針類型描述、訪問和處理二叉樹的運算。4、掌握用二叉樹前序、中序、后序、層次遍歷的方法。二、實驗設(shè)備（環(huán)境）及要求微型計算機；windows 操作系統(tǒng)；Microsoft Visual Studio 6.0集成開發(fā)環(huán)境。三、實驗內(nèi)容與步驟1.根據(jù)下圖中的樹回答問題-。 列出所有的葉子結(jié)點； K,L,F,M,H,I,J 列出G結(jié)點的雙親； B 列出E結(jié)點的孩子； K.L 列出I結(jié)點所有的堂兄弟； E,F,G,H 列出B結(jié)點所有的子孫； E,F,G,K,L,M 結(jié)點E的度是多少； 2 樹的度是多少； 3 結(jié)點E的層次是多少； 3 樹的深度是多少； 42根據(jù)P129的方法，將a*b-(c+d*e/f)+g)轉(zhuǎn)化為表達式二叉樹（繪圖），并寫出表達式二叉樹的前序、中序和后序遍歷順序。-*+ab+gc/f*de先序：-*ab+c/*defg中序：a*b-c+d*e/f+g后序：ab*cde*f/+g+-3. 畫出和下列二叉樹相應(yīng)的森林：4. 鏈?zhǔn)奖肀硎竞蛯崿F(xiàn)二叉排序樹如下：#include #include typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;Bitree root;/定義根結(jié)點 void insert_data(int x) /*生成二叉排序樹*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /創(chuàng)建結(jié)點s-data=x; /結(jié)點賦值s-lchild=NULL;s-rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序樹的適當(dāng)位置*/q=p;if(p-data=x) /相同結(jié)點不能重復(fù)插入printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main() /*先生成二叉排序樹*/int i=1,x; /i記錄結(jié)點個數(shù)，x存放結(jié)點值root=NULL; /*千萬別忘了賦初值給root!*/printf(請輸入數(shù)據(jù),-9999表示輸入結(jié)束n);doprintf(please input data %d:,i);i+;scanf(%d,&x); /*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結(jié)束*/if(x=-9999) printf(nNow output data value:n); else insert_data(x); /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=-9999); 改寫以上程序，實現(xiàn)功能如下(任選三題)：1). 編寫函數(shù)實現(xiàn)前序、中序和后序遍歷。2). 編寫函數(shù)實現(xiàn)計算葉節(jié)點個數(shù)。3). 編寫函數(shù)實現(xiàn)層序遍歷。4). 編寫函數(shù)實現(xiàn)查詢二叉樹中的某個結(jié)點(分查到和查不到兩種情況)。5)編寫函數(shù)實現(xiàn)求二叉樹的深度6). 編寫函數(shù)實現(xiàn)中序非遞歸遍歷(利用棧)以下題目為選做題：5. 如果通訊字符a，b，c，d出現(xiàn)頻度分別為7，5，2，4某同學(xué)設(shè)計了如下程序，請根據(jù)程序畫出對應(yīng)的二叉樹，計算所畫出的二叉樹的帶權(quán)路徑長度；if(input=c) printf(%c,c); else if(input=d) printf(%c,d); else if(input=a) printf(%c,a); elseprintf(%c,b); WPL=7*3+5*3+4*2+2*1=46請畫出對應(yīng)的赫夫曼（哈弗曼）樹；計算赫夫曼樹的帶權(quán)路徑長度；WPL=2*3+4*3+5*2+7*1=35根據(jù)赫夫曼樹，用if-else語句修改中的程序，寫出最佳判定算法。if(input=a) printf(%c,a); else if(input=b) printf(%c,b); else if(input=c) printf(%c,c); elseprintf(%c,d);四、實驗結(jié)果與數(shù)據(jù)處理詳細記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果（貼圖）。五、分析與討論對上機實踐結(jié)果進行分析，上機的心得體會。六、教師評語簽名：日期：成績附源程序清單：1、#include #include typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;DLR( Bitree root ) if (root !=NULL) /非空二叉樹 printf(%d,root-data); /訪問D DLR(root-lchild); /遞歸遍歷左子樹 DLR(root-rchild); /遞歸遍歷右子樹 return(0); LDR(Bitree root) if(root !=NULL) LDR(root-lchild); printf(%d,root-data); LDR(root-rchild); return(0);LRD (Bitree root) if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(%d,root-data); return(0);Bitree root;/定義根結(jié)點 void insert_data(int x) /*生成/樹*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /創(chuàng)建結(jié)點s-data=x; /結(jié)點賦值s-lchild=NULL;s-rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序樹的適當(dāng)位置*/q=p;if(p-data=x) /相同結(jié)點不能重復(fù)插入printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main() /*先生成二叉排序樹*/int i=1,x; /i記錄結(jié)點個數(shù)，x存放結(jié)點值root=NULL; /*千萬別忘了賦初值給root!*/printf(請輸入數(shù)據(jù),-9999表示輸入結(jié)束n);doprintf(please input data %d:,i);i+;scanf(%d,&x); /*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結(jié)束*/if(x=-9999) printf(nNow output data value:n); else insert_data(x); /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=-9999); printf(nDLR:); DLR(root); printf(nLDR:); LDR(root); printf(nLRD:); LRD(root);printf(n);2、#include #include typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;Bitree root;/定義根結(jié)點 int CountLeaf (Bitree root) /返回指針T所指二叉樹中所有葉子結(jié)點個數(shù)int m,n; if (!root ) return 0; if (!root-lchild & !root-rchild) return 1; else m = CountLeaf( root-lchild); n = CountLeaf( root-rchild); return (m+n); /else / CountLeafvoid insert_data(int x) /*生成/樹*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /創(chuàng)建結(jié)點s-data=x; /結(jié)點賦值s-lchild=NULL;s-rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序樹的適當(dāng)位置*/q=p;if(p-data=x) /相同結(jié)點不能重復(fù)插入printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main() /*先生成二叉排序樹*/int i=1,x; /i記錄結(jié)點個數(shù)，x存放結(jié)點值int sum;root=NULL; /*千萬別忘了賦初值給root!*/printf(請輸入數(shù)據(jù),-9999表示輸入結(jié)束n);doprintf(please input data %d:,i);i+;scanf(%d,&x); /*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結(jié)束*/if(x=-9999) printf(nNow output data value:n); else insert_data(x); /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=-9999);printf( n葉節(jié)點個數(shù)=);sum=CountLeaf (root);printf(%dn,sum);3、#include #include typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;Bitree root;/定義根結(jié)點 int Depth (Bitree root ) / 返回二叉樹的深度 int depthval,depthLeft,depthRight;if (root=NULL) depthval = 0; else depthLeft = Depth( root-lchild ); depthRight= Depth( root-rchild ); depthval = 1+(depthLeftdepthRight?depthLeft:depthRight); return depthval;void insert_data(int x) /*生成/樹*/ Bitree p,q,s;s=(Bitree)malloc(sizeof(BiNode); /創(chuàng)建結(jié)點s-data=x; /結(jié)點賦值s-lchild=NULL;s-rchild=NULL;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序樹的適當(dāng)位置*/q=p;if(p-data=x) /相同結(jié)點不能重復(fù)插入printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void main() /*先生成二叉排序樹*/int i=1,x; /i記錄結(jié)點個數(shù)，x存放結(jié)點值int d;root=NULL; /*千萬別