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

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