數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)樹(shù)和叉樹(shù)的操作

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)序號(hào)：6實(shí)驗(yàn)項(xiàng)目名稱(chēng)：樹(shù)和二叉樹(shù)的操作學(xué)號(hào)姓名專(zhuān)業(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、掌握用指針類(lèi)型描述、訪問(wèn)和處理二叉樹(shù)的運(yùn)算。4、掌握用二叉樹(shù)前序、中序、后序、層次遍歷的方法。二、實(shí)驗(yàn)設(shè)備(環(huán)境)及要求微型計(jì)算機(jī)；wi ndows操作系統(tǒng)；Microsoft Visual Studio 6.0 集成開(kāi)發(fā)環(huán)境。三、實(shí)驗(yàn)內(nèi)容與步驟1.根據(jù)P129的方法，將a*b-(c+d*e/f)+g)轉(zhuǎn)化為表達(dá)式二叉樹(shù)(繪圖)，并寫(xiě)出表達(dá)式二叉樹(shù)的前序、中序和后序遍歷順先序：

2、-*ab+c*d/efg中序：a*b-c+d*e/f+g后序：ab*cdef/*+g+-2.鏈?zhǔn)奖肀硎竞蛯?shí)現(xiàn)二叉排序樹(shù)如下:#i nclude #i nclude typedef int TEIemType;typedef struct BiTNodeTElemType data; struct BiTNode *lchild,*rchild;BiNode, *Bitree;Bitree root;/ 定義根結(jié)點(diǎn)void in sert_data(i nt x) /*生成/樹(shù)*/Bitree p,q,s; s=(Bitree)malloc(sizeof(BiNode); / s-data=x;

3、 / s-lchild=NULL; s-rchild=NULL;if(!root)結(jié)點(diǎn)賦值root=s;創(chuàng)建結(jié)點(diǎn) elsep=root; while(p) /*如何接入二叉排序樹(shù)的適當(dāng)位置*/q=p;if(p-data=x) /prin tf(data already exist! n “); return;else if(xdata)p=p-lchild;elsep=p-rchild;相同結(jié)點(diǎn)不能重復(fù)插入if(xdata) q-lchild=s;elseq-rchild=s;void main ()/*int i=1, x; /iroot=NULL;先生成二叉排序樹(shù)*/記錄結(jié)點(diǎn)個(gè)數(shù)，x存放結(jié)

4、點(diǎn)值/*千萬(wàn)別忘了賦初值給root!*/printf（”請(qǐng)輸入數(shù)據(jù)，-9999表示輸入結(jié)束n）;doprin tf(please in put data %d:,i);i+;scanf(%d,&x);/*從鍵盤(pán)采集數(shù)據(jù)，以-9999表示輸入結(jié)束*/if(x=-9999)prin tf(nNow output data value: n);elseinsert_data(x); /*調(diào)用插入數(shù)據(jù)元素的函0, 0 , 數(shù)*/while(x!=-9999);改寫(xiě)以上程序，實(shí)現(xiàn)功能如下(任選三題)：1.編寫(xiě)函數(shù)實(shí)現(xiàn)前序、中序和后序遍歷。請(qǐng)輸入數(shù)據(jù)宀號(hào)9表示輸入結(jié)束please input please

5、 input please input please input please input please inputdata 1:1data 2:2data 3：3data 4data 5：5data 6：-9999Now output data value:DLR12345LDR12345LRD54321Preany key to continue3.編寫(xiě)函數(shù)實(shí)現(xiàn)層序遍歷4.編寫(xiě)函數(shù)實(shí)現(xiàn)查詢(xún)二叉樹(shù)中的某個(gè)結(jié)點(diǎn)(分查到和查不到兩種情況)5 編寫(xiě)函數(shù)實(shí)現(xiàn)求二叉樹(shù)的深度請(qǐng)輸入數(shù)據(jù)*表示輸入結(jié)束please intuit data 1:4pIeqw 耳 input弘2 - 6please input

6、 daita 3:9 plese input data 4!8Ipleascinput data 5：5pleaseinput data 6 : 9999*ou outpat data ualue:樹(shù)的深度為訶Press ankey to continue6.編寫(xiě)函數(shù)實(shí)現(xiàn)中序非遞歸遍歷（利用棧）四、實(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ī)?nèi)掌冢焊皆闯绦蚯鍐?1.#i nclude #in elude typedef int TEIemType;typedef struc

7、t BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiNode, *Bitree;DLR( Bitree root ) if (root !=NULL) / 非空二叉樹(shù)printf(%d,root-data); / 訪問(wèn) DDLR(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);retu

8、rn(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) /* 如何接入二

9、叉排序樹(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;elsep=p-rchild; if(xdata) q-lchild=s;elseq-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 %

10、d:,i);i+;-9999 表示輸入結(jié)束 */*/scanf(%d,&x); /* 從鍵盤(pán)采集數(shù)據(jù)，以 if(x=-9999)printf(nNow output data value:n);elseinsert_data(x); /* 調(diào)用插入數(shù)據(jù)元素的函數(shù) while(x!=-9999);printf(nDLR);DLR(root);printf(nLDR);LDR(root);printf(nLRD);LRD(root);2.#include #include typedef int TElemType;typedef struct BiTNodeTElemType data;stru

11、ct 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

12、)/*生成 /樹(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;elsep=p-rchild; if(xdata) q-lchild=s;else q

13、-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);-9999 表示輸入結(jié)束 */*/i+;scanf(%d,&x); /* 從鍵盤(pán)采集數(shù)據(jù)，以 if(x=-9999)printf(nNow output data value:n);else insert_data(x); /* 調(diào)用插入數(shù)據(jù)元素的函數(shù) while

14、(x!=-9999); printf( n 葉節(jié)點(diǎn)個(gè)數(shù) =); sum=CountLeaf (root); printf(%dn,sum);5.#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

15、) 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;elsep=p-rchild; if(xdata) q-lchild=s;elseq-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)別忘了賦初值給 root!*/ printf(