1、實(shí)用標(biāo)準(zhǔn)文檔數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告題目： 二叉樹(shù)抽象數(shù)據(jù)類型的實(shí)現(xiàn)學(xué)院* 學(xué)院專業(yè)*年級(jí)班別*學(xué)號(hào)*學(xué)生姓名*指導(dǎo)教師成績(jī) _2012年6月文案大全實(shí)用標(biāo)準(zhǔn)文檔報(bào)告：內(nèi)容：詳細(xì)完整不完整設(shè)計(jì)方案：非常合理合理較差實(shí)現(xiàn)：全部實(shí)現(xiàn)部分實(shí)現(xiàn)未實(shí)現(xiàn)文檔格式：規(guī)范基本規(guī)范不規(guī)范答辯：理解題目透徹，問(wèn)題回答流利理解題目較透徹，回答問(wèn)題基本正確部分理解題目，部分問(wèn)題回答正確未能完全理解題目，答辯情況較差總評(píng)成績(jī)：優(yōu)良中及格不及格文案大全實(shí)用標(biāo)準(zhǔn)文檔一實(shí)驗(yàn)概要二叉樹(shù)抽象數(shù)據(jù)類型的實(shí)現(xiàn)二 . 實(shí)驗(yàn)?zāi)康?. 了解二叉樹(shù)的定義以及各項(xiàng)基本操作。2. 實(shí)現(xiàn)二叉樹(shù)存儲(chǔ)、遍歷及其他基本功能三.實(shí)驗(yàn)儀器設(shè)備和材料Visual s

2、tudio 2010四實(shí)驗(yàn)的內(nèi)容1. 二叉樹(shù)類型定義以及各基本操作的簡(jiǎn)要描述；ADT BinaryTree 數(shù)據(jù)對(duì)象 D:D 是具有相同特性的數(shù)據(jù)元素的集合.數(shù)據(jù)關(guān)系 R:若 D=?，則 R=,稱 BinaryTree 為空二叉樹(shù)；若 D，則 R=H， H 是如下二元關(guān)系：(1) 在 D中存在惟一的稱為根的數(shù)據(jù)元素 root ，它在關(guān)系 H 下無(wú)前驅(qū)；(2) 若 D-root ?，則存在 D-root=D1,Dr ，且 D1 Dr=?；(3) 若 D1?，則 D1 中存在惟一的元素 x1，H，且存在 Dr上的關(guān)系 HrH；H=， ，H1,Hr ；(4) （D1， H1 ）是一棵符合本定義的二叉

3、樹(shù)，稱為根的左子樹(shù)，是一棵符合本定義的二叉樹(shù)，稱為根的右子樹(shù)。基本操作 P:InitBiTree(&T);操作結(jié)果：構(gòu)造空二叉樹(shù)T。DestroyBiTree(&T);初始條件：二叉樹(shù)T 存在。操作結(jié)果：銷毀二叉樹(shù)T。CreateBiTree(&T,definition);初始條件： definition給出二叉樹(shù) T 的定義。操作結(jié)果：按 definition構(gòu)造二叉樹(shù) T。ClearBiTree(&T);初始條件：二叉樹(shù)T 存在。操作結(jié)果：將二叉樹(shù)T 清為空樹(shù)。BiTreeEmpty(T);初始條件：二叉樹(shù)T 存在。操作結(jié)果：若 T 為空二叉樹(shù)，則返回TURE,否則 FALSE。BiTre

4、eDepth(T);初始條件：二叉樹(shù)T 存在。文案大全實(shí)用標(biāo)準(zhǔn)文檔操作結(jié)果：返回T 的深度。Root(T);初始條件：二叉樹(shù)T 存在。操作結(jié)果：返回T 的根。Value(T,e);初始條件：二叉樹(shù)T 存在， e 是 T 中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回 e 的值。Assign(T,&e,value);初始條件：二叉樹(shù)T 存在， e 是 T 中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：結(jié)點(diǎn)e 賦值為 value 。Parent(T,e);初始條件：二叉樹(shù)T 存在， e 是 T 中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：若 e 是 T 的非跟結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。LeftChild(T,e);初始條件：二叉樹(shù)T 存在， e

5、 是 T 中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e 的左孩子。若 e 無(wú)左孩子，則返回“空” 。RightChild(T,e);初始條件：二叉樹(shù)T 存在， e 是 T 中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回e 的右孩子。若 e 無(wú)右孩子，則返回“空” 。LeftSibling(T,e);初始條件：二叉樹(shù)T 存在， e 是 T 中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回 e 的左兄弟。若 e 無(wú)左孩子或無(wú)左兄弟，則返回“空” 。RightSibling(T,e);初始條件：二叉樹(shù)T 存在， e 是 T 中的某個(gè)結(jié)點(diǎn)。操作結(jié)果：返回 e 的右兄弟。若 e 無(wú)右孩子或無(wú)右兄弟，則返回“空” 。ADT BinaryTree2. 所選擇

6、的存儲(chǔ)結(jié)構(gòu)描述及在此存儲(chǔ)結(jié)構(gòu)上各基本操作的實(shí)現(xiàn)；3. 源代碼主文件 :main.ccp:#includebase.h/公用頭文件、公共常量及公共函數(shù)等#includebitree.h/二叉樹(shù)二叉鏈表基本操作voidMenu();/菜單函數(shù)voidProduce(char *str);/隨機(jī)產(chǎn)生二叉樹(shù)先序序列函數(shù)intmain()/主函數(shù)BiTree T,bt,insert_bt;charcmd,strMAXSIZE,elem;intloc,temp;文案大全實(shí)用標(biāo)準(zhǔn)文檔InitBiTree(T);/初始化二叉鏈表二叉樹(shù)Menu();/顯示菜單while(1)ClearLine();/清空結(jié)果顯

7、示區(qū)printf(請(qǐng)選擇操作： ( 按 Q 退出 );cmd = getch();ClearLine();fflush(stdin);switch(cmd)case 0:/隨機(jī)創(chuàng)建一棵二叉樹(shù)while(cmd != y & cmd != Y)Produce(str);/隨機(jī)產(chǎn)生二叉樹(shù)先序序列CreateBiTree(T,str);/用此序列建樹(shù)ShowBiTree(T);/廣義表形式顯示printf(使用創(chuàng)建的這個(gè)二叉樹(shù)?);cmd = getch();ClearLine();break;case 2:/手動(dòng)創(chuàng)建一棵二叉樹(shù)printf( 請(qǐng)按二叉樹(shù)先序序列輸入二叉樹(shù)： ( 空結(jié)點(diǎn)用空格 表示

8、)n ); CreateBiTree(T);ClearLine();printf(二叉樹(shù)創(chuàng)建成功!n);ShowBiTree(T);getch();break;case 4:/銷毀二叉樹(shù)DestroyBiTree(T);printf(二叉樹(shù)已被銷毀!);getch();break;case 6:/判空if(BiTreeEmpty(T) printf(二叉樹(shù)是空二叉樹(shù)。);elseprintf(二叉樹(shù)非空 );getch();break;case 8:/求深度printf(深度是 %d,BiTreeDepth(T);getch();break;文案大全實(shí)用標(biāo)準(zhǔn)文檔case a:/求左孩子Show

9、BiTree(T);printf(你想求哪個(gè)字符的左孩子？);doelem = getchar();ClearLine();bt = SearchBiTree(T,elem);/查找指定的結(jié)點(diǎn)值elemif(!bt) printf(你輸入的結(jié)點(diǎn)不存在! 請(qǐng)重新輸入：);while(!bt);ClearLine();bt = LeftChild(T,bt);/求左孩子if(bt) printf( %c的左孩子是 %c,elem,bt-data);elseprintf( %c沒(méi)有左孩子 ,elem);printf(n參照二叉樹(shù) :);ShowBiTree(T);getch();break;case

10、 c:/求右孩子ShowBiTree(T);printf(你想求哪個(gè)字符的右孩子？);doelem = getchar();ClearLine();bt = SearchBiTree(T,elem);if(!bt) printf(你輸入的結(jié)點(diǎn)不存在! 請(qǐng)重新輸入：);while(!bt);ClearLine();bt = RightChild(T,bt);if(bt) printf( %c的右孩子是 %c,elem,bt-data);elseprintf( %c沒(méi)有右孩子 ,elem);printf(n參照二叉樹(shù) :);ShowBiTree(T);getch();break;case 1:/先

11、序遍歷if(!BiTreeEmpty(T)printf(先序遍歷序列為：);PreOrderTraverse(T,Visit);else printf(二叉樹(shù)空，請(qǐng)先建樹(shù)!);getch();break;case 3:/中序遍歷文案大全實(shí)用標(biāo)準(zhǔn)文檔if(!BiTreeEmpty(T)printf(中序遍歷序列為：);InOrderTraverse(T,Visit);else printf(二叉樹(shù)空，請(qǐng)先建樹(shù)!);getch();break;case 5:/后序遍歷if(!BiTreeEmpty(T)printf(后序遍歷序列為：);PostOrderTraverse(T,Visit);else

12、 printf(二叉樹(shù)空，請(qǐng)先建樹(shù)!);getch();break;case 7:/層次遍歷if(!BiTreeEmpty(T)printf(層次遍歷序列為：);LevelOrderTraverse(T,Visit);else printf(二叉樹(shù)空，請(qǐng)先建樹(shù)!);getch();break;case 9:/插入一棵二叉樹(shù)為另一棵二叉樹(shù)的子樹(shù)do/隨機(jī)創(chuàng)建一棵右孩子為空Produce(str);/且層數(shù)小于4 的樹(shù)CreateBiTree(insert_bt,str);while(insert_bt-rchild|BiTreeDepth(insert_bt) 3);printf(先隨機(jī)創(chuàng)建一棵

13、右子樹(shù)空的二叉樹(shù)如圖n);ShowBiTree(insert_bt);/新創(chuàng)建的樹(shù)getch();printf(你想插入這棵樹(shù)為原樹(shù)哪個(gè)結(jié)點(diǎn)的子樹(shù):n);ShowBiTree(T);bt = SearchBiTree(T,getchar();ClearLine();printf(你想插入為0.左孩子1.右孩子 :);fflush(stdin);scanf(%d,&loc);if(!InsertChild(T, bt, loc, insert_bt)printf(插入出錯(cuò) !);else文案大全實(shí)用標(biāo)準(zhǔn)文檔ClearLine();printf(插入成功 ! 插入后 T 廣義表形式為:n);Sho

14、wBiTree(T);getch();break;case b:/刪除指定結(jié)點(diǎn)的子樹(shù)ShowBiTree(T);printf(你想刪除哪個(gè)結(jié)點(diǎn)的子樹(shù)?);fflush(stdin);bt = SearchBiTree(T,getchar();printf(n你想刪除0. 左子樹(shù) 1. 右子樹(shù) : );fflush(stdin);scanf(%d,&loc);ClearLine();if(!DeleteChild(T,bt,loc) printf(刪除出錯(cuò) !);else printf(刪除成功，檢查結(jié)果n);ShowBiTree(T);getch();break;case e:/返回先序序列第

15、i 個(gè)結(jié)點(diǎn)的值printf(請(qǐng)輸入一個(gè)結(jié)點(diǎn)的先序序列序號(hào): );scanf(%d,&loc);temp = loc;ClearLine();elem = Value(T,temp);printf(參照二叉樹(shù) :);ShowBiTree(T);printf(n);if(elem = )printf(該結(jié)點(diǎn)不存在。);else printf(先序序列第 %d個(gè)結(jié)點(diǎn)值為 %c,loc,elem);getch();break;case d:/結(jié)點(diǎn)賦值ShowBiTree(T);printf(請(qǐng)輸入要賦值的結(jié)點(diǎn): );doelem = getchar();ClearLine();bt = SearchB

16、iTree(T,elem);if(!bt) printf(你輸入的結(jié)點(diǎn)不存在! 請(qǐng)重新輸入：);while(!bt);ClearLine();printf(請(qǐng)輸入新值 : );fflush(stdin);文案大全實(shí)用標(biāo)準(zhǔn)文檔elem = getchar();Assign(T,bt,elem);printf(賦值成功，請(qǐng)查看二叉樹(shù)狀態(tài).n);ShowBiTree(T);getch();break;case Q:/退出case q: exit(0);return 0;voidMenu()/顯示菜單函數(shù)printf( 0.隨機(jī)創(chuàng)建 CreateBiTree()1.先序遍歷 PreOrderTrave

17、rse();printf(nn2.手 動(dòng)創(chuàng) 建CreateBiTree()3.中序 遍歷InOrderTraverse();printf(nn4.銷 毀DestoryBiTree()5.后 序 遍 歷PostOrderTraverse();printf(nn6.判 空BiTreeEmpty()7.層 次 遍 歷LevelOrderTraverse();printf(nn 8.求深度BiTreeDepth()9.插入子樹(shù)InsertChild();printf(nn a.求左孩子 LeftChild()b.刪除子樹(shù)DeleteChild();printf(nn c.求右孩子 RightChild

18、()d.結(jié)點(diǎn)賦值A(chǔ)ssign();printf(nn e.求結(jié)點(diǎn)值 Value();printf(nn);voidProduce(char *str)/ 用隨機(jī)數(shù)產(chǎn)生二叉樹(shù)層次字符序列/使所有節(jié)點(diǎn)的字符不相同，空節(jié)點(diǎn)用&表示intexist27 , i , elem, maxnodes = rand()%41;while( maxnodes 31) maxnodes = rand()%41; /* 隨機(jī)產(chǎn)生一個(gè) 大于 15 小于 31 的隨機(jī)數(shù)作為結(jié)點(diǎn)個(gè)數(shù) */for(i = 0; i 27 ;i+) existi = 0;/初始化存在數(shù)組，用于使所有結(jié)點(diǎn)值不同i = 1;while(i ma

19、xnodes)elem = rand() % 26 ;if(!existelem & stri/2 != &) /結(jié)點(diǎn)未生成且存在父節(jié)點(diǎn)文案大全實(shí)用標(biāo)準(zhǔn)文檔stri+ = elem + A;existelem = 1;else stri+ = &;stri = 0;頭文件 :base.h:#includestdio.h#includeconio.h#includestdlib.h#includewindows.h#includemalloc.h#includemath.h#defineOK1#defineTRUE1#defineERROR0#defineFALSE0#defineMAXSIZE

20、100typedefintStatus;typedefcharTElemType;shortwherex()/返回光標(biāo)的 x 坐標(biāo)shortwherey()/ 返回光標(biāo)的y 坐標(biāo)void gotoxy(short x,short y)/ 移動(dòng)光標(biāo)到（x， y）坐標(biāo)COORD point = x, y;SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), point);文案大全實(shí)用標(biāo)準(zhǔn)文檔void ClearLine(unsigned y = 17)/ 清除第 y 行與 y+1 行的字符，并使光標(biāo)在行首，默認(rèn)清除第17至19行for(

21、int i = 0;i 256;i+)gotoxy(i,y);putchar( );gotoxy(0,wherey()-3);void ClearAera(unsigned x = 96, unsigned y = 17)/ 清除 (0,y)-(x,y+1)區(qū)域的字符，并使光標(biāo)移動(dòng)到y(tǒng)for(unsigned i = 0; ilchild);/刪除左子樹(shù)DestroyBiTree(T-rchild);/刪除右子樹(shù)free(T);T = NULL;return OK;StatusCreateBiTree(BiTree &T)/先序建立二叉樹(shù)T, 空格表示空結(jié)點(diǎn)TElemType ch;fflus

22、h(stdin);ch=getche();if(ch = ) T = NULL;elseT = (BiTree)malloc(sizeof(BiTNode);if(!T) exit(OVERFLOW);T-data = ch;/生成頭結(jié)點(diǎn)CreateBiTree(T-lchild);/構(gòu)造左子樹(shù)CreateBiTree(T-rchild);/構(gòu)造右子樹(shù)return OK;StatusCreateBiTree(BiTree &T,char *str,unsigned i = 1)/ str儲(chǔ)存著二叉樹(shù)的層次序列，stri=&表示結(jié)點(diǎn)不存在/ i 為當(dāng)前要?jiǎng)?chuàng)建結(jié)點(diǎn)對(duì)應(yīng)的數(shù)組序號(hào)節(jié)點(diǎn)/由字符數(shù)組st

23、r先序建立一棵二叉樹(shù)Tif(stri = & | i = strlen(str) T = NULL; /第 i 個(gè)結(jié)點(diǎn)不存在elseT = (BiTree)malloc(sizeof(BiTNode);if(!T) exit(OVERFLOW);T-data = stri;/生成根節(jié)點(diǎn)CreateBiTree(T-lchild, str, i*2);/構(gòu)造左子樹(shù)CreateBiTree(T-rchild, str, i*2+1);/構(gòu)造右子樹(shù)return OK;文案大全實(shí)用標(biāo)準(zhǔn)文檔StatusBiTreeEmpty(BiTree T)/若 T 為空二叉樹(shù)，則返回TRUE，否則返回FALSEif

24、(!T)return TRUE;elsereturn FALSE;intBiTreeDepth(BiTree T)/ 返回 T 的深度/ 利用層次遍歷求深度if(!T) return 0;BiTreequeue200;int dep =0;intrear = 0 ,front = 0;queuerear+ = T;while(rear != front)T = queuefront+;if(T-data)dep+;if(T-lchild) queuerear+ = T-lchild;if(T-rchild) queuerear+ = T-rchild;else dep-;return dep;

25、TElemTypeValue(BiTree T,int&k)/ 返回二叉樹(shù)先序遍歷第 k 個(gè)節(jié)點(diǎn)的值，不存在則返回空格 if(!T | k data;BiTree stack100,p = T;/定義數(shù)組棧inttop = 0 ,i=-1;/初始化棧頂指針while(p | top 0 )/當(dāng)結(jié)點(diǎn)不空或棧不空if(p)文案大全實(shí)用標(biāo)準(zhǔn)文檔i+;if(i=k)return p-data;stacktop+ = p;/根指針入棧，遍歷左子樹(shù)p = p-lchild;else/根指針退棧，遍歷右子樹(shù)p = stack-top;p = p-rchild;voidAssign(BiTree T,BiTr

26、ee &p,TElemType value)/ 二叉樹(shù) T 存在， e 是 T 中某個(gè)結(jié)點(diǎn)/ 結(jié)點(diǎn) p 賦值為 valueif(p) p-data = value;BiTreeLeftChild(BiTree T,BiTree p)/ 返回 p 的左孩子。若 p 無(wú)左孩子，則返回“空”return p-lchild;BiTreeRightChild(BiTree T,BiTree p)/ 返回 p 的右孩子。若 p 無(wú)右孩子，則返回“空”return p-rchild;StatusInsertChild(BiTree &T,BiTree &p,int LR,BiTree &c)/二叉樹(shù) T 存

27、在， p 指向 T 中某個(gè)結(jié)點(diǎn)，LR 為 0 或 1，非空二叉樹(shù)c 與 T 不相交且右子樹(shù)為空。/根據(jù) LR為 0 或 1，插入 c 為 T 中 p 所指向結(jié)點(diǎn)的左或右子樹(shù)。/ p所指結(jié)點(diǎn)的原有左或右子樹(shù)則成為c 的右子樹(shù)。if( !T | !c | !p | (LR != 0 & LR != 1)return ERROR;/不符合條件if(LR =0 )/插入為左子樹(shù)c-rchild = p-lchild;p-lchild = c;文案大全實(shí)用標(biāo)準(zhǔn)文檔if(LR = 1)/插入為右子樹(shù)c-rchild = p-rchild;p-rchild = c;return OK;StatusDelet

28、eChild(BiTree &T,BiTree &p,int LR)/ p指向 T 中某個(gè)結(jié)點(diǎn)，LR 為 0 或 1./用隊(duì)列，根據(jù)LR 為 0 或 1，刪除 T 中 P 所指結(jié)點(diǎn)的左或右子樹(shù)if(!T | !p | (LR != 1 & LR != 0)return ERROR;BiTreequeue200;/定義數(shù)組隊(duì)列intrear = 0, front = 0 ;/初始化隊(duì)列的頭指針和尾指針if(LR = 0 & p-lchild)/ LR為 0 且所刪除左孩子存在queuerear+ = p-lchild;/則左孩子入隊(duì)p-lchild = NULL;if(LR = 1 & p-rc

29、hild)/ LR為 1 且所刪除右孩子存在queuerear+ = p-rchild;/則右孩子入隊(duì)p-rchild = NULL;while(rear != front)/用隊(duì)列層次遍歷，刪除所要求的子樹(shù)p = queuefront+;if(p-lchild) queuerear+ = p-lchild;if(p-rchild) queuerear+ = p-rchild;free(p);return OK;StatusPreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/非遞歸先序遍歷二叉樹(shù)。對(duì)每個(gè)節(jié)點(diǎn)調(diào)用Visit函數(shù)BiTree

30、 stack100,p = T;/定義數(shù)組棧inttop = 0 ;/初始化棧頂指針文案大全實(shí)用標(biāo)準(zhǔn)文檔while(p | top 0 )/當(dāng)結(jié)點(diǎn)不空或棧不空if(p)if(!Visit(p-data)/訪問(wèn)根節(jié)點(diǎn)return ERROR;stacktop+ = p;/根指針入棧，遍歷左子樹(shù)p = p-lchild;else/根指針退棧，遍歷右子樹(shù)p = stack-top;p = p-rchild;return OK;StatusInOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/非遞歸中序遍歷二叉樹(shù)，對(duì)每個(gè)節(jié)點(diǎn)調(diào)用Visit。BiTr

31、ee stack100,p = T;/定義數(shù)組棧inttop = 0 ;/初始化棧頂指針while(p | top 0 )if(p)/根指針入棧，遍歷左子樹(shù)stacktop+ = p;p = p-lchild;else/根指針退棧，遍歷右子樹(shù)p = stack-top;if(!Visit(p-data)return ERROR;p = p-rchild;return OK;StatusPostOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/用棧非遞歸后序遍歷二叉樹(shù)T。/與非遞歸先序中序的區(qū)別在于，多定義一visited數(shù)組，用來(lái)記錄訪問(wèn)次

32、數(shù)/ 第二次訪問(wèn)時(shí)才退棧。文案大全實(shí)用標(biāo)準(zhǔn)文檔BiTreestack100 , p = T;/定義數(shù)組棧inttop = 0, visited100;/初始化棧頂指針與訪問(wèn)次數(shù)數(shù)組while(p | top 0)if(p)/遍歷左子樹(shù)，置訪問(wèn)數(shù)組為第一次訪問(wèn)stacktop+ = p;visitedtop-1 = 0;p = p-lchild;elseif(visitedtop-1 = 0)/若棧頂結(jié)點(diǎn)只訪問(wèn)一次，遍歷右子樹(shù)p = stacktop-1;visitedtop-1 +;p = p-rchild;else if(visitedtop-1 = 1)/若第二次訪問(wèn)，則根指針退棧，訪問(wèn)根節(jié)點(diǎn)。if(!Visit(stack-top-data) return ERROR;return OK;StatusLevelOrderTraverse(BiTree T,Status (*Visit)(TElemType e)/用隊(duì)列層次遍歷二叉樹(shù)T。/對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit（）失敗，則操作失敗if(!T)return OK;BiTreequeue200;/定義數(shù)組隊(duì)列intrear = 0 ,front = 0;/初始化隊(duì)頭、隊(duì)尾指針queuerear+ = T;/根