實(shí)驗(yàn)五--二叉樹的建立及遍歷.doc

《實(shí)驗(yàn)五--二叉樹的建立及遍歷.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、實(shí)驗(yàn)五二叉樹的建立及遍歷一、實(shí)驗(yàn)?zāi)康?．熟悉二叉樹的存貯結(jié)構(gòu)及遍歷方式，掌握有關(guān)算法的實(shí)現(xiàn)。2．能夠利用二叉樹解決具體問題。二、實(shí)驗(yàn)內(nèi)容1.要求采用二叉鏈表作為存貯結(jié)構(gòu)，樹中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)類型設(shè)定為字符型。完成二叉樹的建立、先序、中序、和后序遞歸遍歷的操作。2.利用棧實(shí)現(xiàn)非遞歸中序遍歷二叉樹。3.利用隊(duì)列實(shí)現(xiàn)按層遍歷二叉樹。實(shí)現(xiàn)提示：本算法要采用一個(gè)隊(duì)列q，先輸出二叉樹根結(jié)點(diǎn)，然后判斷：若其左孩子指針非空，則將其入隊(duì)列；若其右孩子指針非空，則也將其入隊(duì)列。然后取隊(duì)列首指針，對(duì)其所指結(jié)點(diǎn)繼續(xù)做如上操作，直到隊(duì)列空為止。因?yàn)殛?duì)列的特點(diǎn)是先

2、進(jìn)先出，從而達(dá)到按層次順序遍歷二叉樹目的。#include#include#includetypedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;voidcreat(BiTree&T){//填充創(chuàng)建樹的代碼}voidpreorder(BiTreeT){//填充先序遍歷代碼}voidinorder(BiTreeT){\填充中序遍歷代碼}voidpostorder(BiTreeT){

3、填充后序遍歷代碼}main(){BiTreeT;creat(T);preorder(T);printf("");postorder(T);printf("");inorder(T);printf("");}實(shí)驗(yàn)六查找一、實(shí)驗(yàn)?zāi)康?．掌握順序查找和折半查找兩種查找的算法及實(shí)現(xiàn)技術(shù)；了解它們各自的優(yōu)缺點(diǎn)。2．構(gòu)造并能輸出二叉排序樹。3．熟悉上述查找方法的適用范圍和條件，基本思想及效率分析。二、實(shí)驗(yàn)內(nèi)容⒈順序查找建立一個(gè)學(xué)生信息表，表中的每個(gè)數(shù)據(jù)元素是一個(gè)記錄，其中的以學(xué)號(hào)作為關(guān)鍵字，編程進(jìn)行順序查找。如果找到，就輸出該元素的

4、位置；如果沒找到，輸出0。#includetypedefstruct{intnu;charna[20];intscore;}elemtype;typedefstruct{elemtypeelem[20];intlength;}SSTable;intSearch_Seq(SSTableST,intkey){//順序查找}voidmain(){SSTableST;intx=1,i,key;printf("Enterlength:");scanf("%d",&ST.length);for(i=1;i<=ST.lengt

5、h;i++){printf("No.%dnumber:",i);scanf("%d",&ST.elem[i].nu);printf("name:");scanf("%s",&ST.elem[i].na);printf("score:");scanf("%d",&ST.elem[i].score);}while(x==1){printf("Enterthenumbertosearch:");scanf("%d",&key);i=Search_Seq(ST,key);if(i>0){printf("Theelement

6、isno.%d:",i);printf("nu:%d,name:%s,score:%d",ST.elem[i].nu,ST.elem[i].na,ST.elem[i].score);}elseprintf("Thereisno%d",key);printf("1-Continue2-Out");scanf("%d",&x);}}⒉折半查找建立一個(gè)學(xué)生信息表，表中的每個(gè)數(shù)據(jù)元素是一個(gè)記錄，要求表按關(guān)鍵字“學(xué)號(hào)”有序，編程實(shí)現(xiàn)折半查找。如果找到，就輸出該元素的位置；如果沒找到，輸出0。#include

7、typedefstruct{intnu;charna[20];intscore;}elemtype;typedefstruct{elemtypeelem[20];intlength;}SSTable;intSearch_Bin(SSTableST,intkey){//填加折半查找的代碼}voidmain(){SSTableST;intx=1,i,key;printf("Enterlength:");scanf("%d",&ST.length);for(i=1;i<=ST.length;i++){printf("No.%dnum

8、ber:",i);scanf("%d",&ST.elem[i].nu);printf("name:");scanf("%s",&ST.elem[i].na);printf("score:");scanf("%d"