數(shù)據(jù)結(jié)構(gòu)實驗報告實驗題目:創(chuàng)建二叉排序樹與查找實驗?zāi)康模?、掌握使用Visual C+6.0上機調(diào)試程序的基本方法；2、 掌握二叉排序樹的創(chuàng)建和二叉排序樹查找的方法。3、 提高自己分析問題和解決問題的能力，在實踐中理解教材上的理論。實驗內(nèi)容：建立至少10個頂點的二叉排序樹，然后對其進(jìn)行中序遍歷，接著進(jìn)行查找，判斷待查找數(shù)據(jù)是否存在。一、需求分析1、輸入的形式和輸入值的范圍：根據(jù)提示，首先輸入頂點中的數(shù)據(jù)，在進(jìn)行查找操作時，輸入待查找的數(shù)據(jù)，接著選擇下一步要進(jìn)行的操作(A.新二叉排序樹;B.繼續(xù)查找;C.結(jié)束操作)。2、輸出的形式：輸出二叉排序的中序遍歷結(jié)果，在輸入待查找的數(shù)據(jù)后，輸出查找的結(jié)果。3、程序所能達(dá)到的功能：輸入頂點數(shù)據(jù)后，創(chuàng)建二叉排序樹，接著進(jìn)行中序遍歷，再輸入待查找數(shù)據(jù)進(jìn)行查找操作。4、測試數(shù)據(jù)：請輸入頂點數(shù)據(jù):53 25 76 20 48 14 60 84 33 78中序遍歷結(jié)果為:14 20 25 33 48 53 60 76 78 84輸入待查找數(shù)據(jù):33待查找數(shù)據(jù)存在選擇操作(A.新二叉排序樹;B.繼續(xù)查找;C.結(jié)束操作):B輸入待查找數(shù)據(jù):54待查找數(shù)據(jù)不存在選擇操作(A.新二叉排序樹;B.繼續(xù)查找;C.結(jié)束操作):C謝謝使用!Press any key to continue二 概要設(shè)計1、 二叉排序樹又稱二叉查找樹，對一個二叉樹若規(guī)定：任一結(jié)點如果有左子樹，其左子樹各結(jié)點的數(shù)據(jù)必須小于該結(jié)點的數(shù)據(jù)；任一結(jié)點如果有右子樹，其右子樹各結(jié)點的數(shù)據(jù)必須大于該結(jié)點的數(shù)據(jù)。按這樣規(guī)定構(gòu)成的二叉樹稱為二叉排序樹。對二叉排序樹進(jìn)行中序遍歷所得到的結(jié)點序列是一個有序序列。2、 創(chuàng)建二叉排序樹的非遞歸算法執(zhí)行的步驟如下：生成一個新結(jié)點；與根結(jié)點進(jìn)行比較，如果小于根結(jié)點，沿左鏈域比較，如果大于根結(jié)點，沿右鏈域比較；直至到終端，插入該結(jié)點。以序列53，25，76，20，48，14，60，84，33，78為例，所創(chuàng)建的二叉排序樹如圖所示。3、 二叉排序樹查找二叉排序樹查找的基本思路：查找過程從根結(jié)點開始，首先將它的關(guān)鍵字與給定值k進(jìn)行比較，如果相等，則查找成功，輸出有關(guān)的信息；如果不等，若根結(jié)點關(guān)鍵字大于給定值k，向左子樹繼續(xù)查找，否則向右子樹繼續(xù)查找。向子樹查找又是樹狀查找，先以子樹的根結(jié)點數(shù)據(jù)與k進(jìn)行比較，如果不相等又轉(zhuǎn)向它的左子樹或右子樹繼續(xù)查找。4、本程序的基本操作和模塊：建立二叉排序樹的函數(shù)：Create(BiTNode *B)二叉樹的中序遍歷函數(shù)：Inorder(BiTNode *B,SeqStack &K)查找函數(shù)：Search(BiTNode *B,int key)主函數(shù)：main( )函數(shù)的調(diào)用關(guān)系如下圖所示: 三 詳細(xì)設(shè)計（1） 元素類型、結(jié)點類型1、 二叉樹結(jié)點的類型描述typedef struct nodechar data;/data用于存儲二叉樹中的字母struct node *lchild;/lchild為指向該結(jié)點左孩子的指針struct node *rchild;/rchild為指向該結(jié)點下一層的指針BiTNode;2、順序棧的類型描述typedef structBiTNode *pin40;/指針數(shù)組，用于存儲廣義表結(jié)點指針int top;/棧頂指針SeqStack;（2） 每個模塊的分析1、 主程序模塊main()定義根結(jié)點指針定義棧并初始化棧申請根結(jié)點空間，令根結(jié)點B的lchild域和rchild域為空 調(diào)用創(chuàng)建二叉排序樹函數(shù)調(diào)用中序遍歷二叉樹函數(shù)調(diào)用查找函數(shù)進(jìn)行查找2、 建立二叉排序樹的函數(shù)void Create(BiTNode *B)定義指向當(dāng)前結(jié)點的指針p，新結(jié)點的指針q，初始時p為空輸入不是回車時執(zhí)行以下操作輸入結(jié)點數(shù)據(jù)若該數(shù)據(jù)是第一個數(shù)據(jù)第一個數(shù)據(jù)存到根節(jié)點，p指針指向根結(jié)點若該數(shù)據(jù)不是第一個數(shù)據(jù)申請新結(jié)點q，將該數(shù)據(jù)存入q的data域令新結(jié)點q的lchild域和rchild域為空p指向根結(jié)點當(dāng)p指針?biāo)附Y(jié)點和q指針?biāo)附Y(jié)點中的數(shù)據(jù)不同時執(zhí)行以下操作如果p結(jié)點數(shù)據(jù)小于新結(jié)點q中的數(shù)據(jù),執(zhí)行以下操作如果p的右孩子為空，令p的右孩子為q將p的右孩子賦p如果p結(jié)點數(shù)據(jù)大于新結(jié)點q中的數(shù)據(jù),執(zhí)行以下操作如果p的左孩子為空，令p的左孩子為q將p的左孩子賦p3、 查找函數(shù)void Search(BiTNode *B,int key)定義指向當(dāng)前結(jié)點的指針p，初始時p指向根結(jié)點當(dāng)p不為空且p所指結(jié)點的數(shù)據(jù)不為待查找數(shù)據(jù)時，執(zhí)行以下操作如果當(dāng)前結(jié)點中的數(shù)據(jù)小于待查找數(shù)據(jù)，則令p指向它的右孩子如果當(dāng)前結(jié)點中的數(shù)據(jù)大于待查找數(shù)據(jù)，則令p指向它的左孩子循環(huán)結(jié)束后，若p為空則待查找數(shù)據(jù)不存在;否則待查找數(shù)據(jù)存在4、 中序遍歷二叉樹樹的函數(shù)void Display(GLNode *G,SeqStack &K)定義表示當(dāng)前結(jié)點的指針p，并令p指根結(jié)點。當(dāng)棧不為空或當(dāng)前結(jié)點指針p不為空時，執(zhí)行以下操作while(K.top!=-1|p!=NULL)a. 如果當(dāng)前結(jié)點指針p為空，執(zhí)行以下操作：出棧，棧頂元素所指的結(jié)點作為當(dāng)前結(jié)點p輸出當(dāng)前結(jié)點p中的數(shù)據(jù)令當(dāng)前結(jié)點p的rchild域所指的結(jié)點作為當(dāng)前結(jié)點pb. 如果當(dāng)前結(jié)點指針p不為空，執(zhí)行以下操作：當(dāng)前結(jié)點指針p入棧令當(dāng)前結(jié)點p的rchild域所指的結(jié)點作為當(dāng)前結(jié)點p四 使用說明、測試分析及結(jié)果1、 程序使用說明：（1） 本程序運行環(huán)境為Visual C+ 6.0；（2） 根據(jù)界面提示進(jìn)行操作：輸入多個數(shù)據(jù)時以空格分隔，每次輸入按回車表示輸入結(jié)束2、 測試結(jié)果與分析：請輸入頂點數(shù)據(jù):53 25 76 20 48 14 60 84 33 78中序遍歷結(jié)果為:14 20 25 33 48 53 60 76 78 84輸入待查找數(shù)據(jù):33待查找數(shù)據(jù)存在選擇操作(A.新二叉排序樹;B.繼續(xù)查找;C.結(jié)束操作):B輸入待查找數(shù)據(jù):54待查找數(shù)據(jù)不存在選擇操作(A.新二叉排序樹;B.繼續(xù)查找;C.結(jié)束操作):C謝謝使用!Press any key to continue由上測試結(jié)果分析得，該程序功能滿足題目要求。3、 調(diào)試過程中遇到的問題及解決方法本次實驗的錯誤的主要發(fā)生在二叉排序樹查找，對進(jìn)行循環(huán)操作的條件判斷不夠完整，輸出數(shù)據(jù)的條件判斷不正確，使運行中出現(xiàn)錯誤。原因是在p為空時，仍判斷p中數(shù)據(jù)是否與待查找數(shù)據(jù)相等。另外，本次實驗中的其它小錯誤都很快修改正確。4、 運行界面五、實驗總結(jié)本次實驗提前作了預(yù)習(xí)，老師在課堂上有詳細(xì)的講解，所以此次實驗比較順利，我在11月23日完成了本次實驗。本次實驗，我很感謝老師和同學(xué)對我的指點。通過本次實驗，對二叉排序樹有了更深的認(rèn)識，學(xué)會了如何利用二叉排序樹查找數(shù)據(jù)，對一些細(xì)節(jié)更加理解，收獲了很多。教師評語：實驗成績：指導(dǎo)教師簽名： 批閱日期： 代碼：# include# include/typedef struct node/二叉樹結(jié)點的類型描述char data;/data用于存儲二叉樹中的字母struct node *lchild;/lchild為指向該結(jié)點左孩子的指針struct node *rchild;/rchild為指向該結(jié)點下一層的指針BiTNode;/typedef struct/順序棧的類型描述BiTNode *pin40;/指針數(shù)組，用于存儲廣義表結(jié)點指針int top;/棧頂指針SeqStack;/void Create(BiTNode *B)/建立二叉排序樹的函數(shù)int m;char r;BiTNode *p,*q;/定義指向當(dāng)前結(jié)點的指針p,新結(jié)點的指針qp=NULL;/初始時p為空printf(請輸入頂點數(shù)據(jù):);while(r!=n)/輸入回車表示循環(huán)結(jié)束scanf(%d%c,&m,&r);/輸入結(jié)點數(shù)據(jù)if(p=NULL)/第一個數(shù)據(jù)置到根節(jié)點，p指針指向根結(jié)點B-data=m;p=B;else/對于其它數(shù)據(jù)執(zhí)行以下操作q=(BiTNode *)malloc(sizeof(BiTNode);/申請新結(jié)點qq-data=m;/令該數(shù)據(jù)存入當(dāng)前結(jié)點的data域q-lchild=NULL;q-rchild=NULL;/令新結(jié)點q的lchild域和rchild域為空p=B;while(p-data!=q-data)/當(dāng)p指針?biāo)附Y(jié)點和q指針?biāo)附Y(jié)點中的數(shù)據(jù)不同時執(zhí)行以下操作if(p-datadata)/如果p結(jié)點數(shù)據(jù)小于新結(jié)點q中的數(shù)據(jù),執(zhí)行以下操作if(p-rchild=NULL)/如果p的右孩子為空，令p的右孩子為qp-rchild=q;p=p-rchild;/將p的右孩子賦pelse/如果p結(jié)點數(shù)據(jù)大于新結(jié)點q中的數(shù)據(jù),執(zhí)行以下操作if(p-lchild=NULL)/如果p的左孩子為空，令p的左孩子為qp-lchild=q;p=p-lchild;/將p的左孩子賦p/void Search(BiTNode *B,int key)/查找函數(shù)BiTNode *p;/定義指向當(dāng)前結(jié)點的指針pp=B;/初始時p指向根結(jié)點while(p!=NULL&p-data!=key)/當(dāng)p不為空且p所指結(jié)點的數(shù)據(jù)不為待查找數(shù)據(jù)時，執(zhí)行以下操作if(p-datarchild;else/如果當(dāng)前結(jié)點中的數(shù)據(jù)大于待查找數(shù)據(jù)，則令p指向它的左孩子p=p-lchild;if(p=NULL) printf(待查找數(shù)據(jù)不存在n,key);/循環(huán)結(jié)束后，若p為空則待查找數(shù)據(jù)不存在;否則待查找數(shù)據(jù)存在else printf(待查找數(shù)據(jù)存在n,key);printf(n);/void Inorder(BiTNode *B,SeqStack &K)/二叉樹的中序遍歷函數(shù)printf(中序遍歷結(jié)果為:);/提示以下結(jié)果為中序遍歷結(jié)果BiTNode *p;/p指針指向當(dāng)前結(jié)點p=B;/當(dāng)前結(jié)點為根結(jié)點while(K.top!=-1|p!=NULL)/當(dāng)棧不為空或當(dāng)前結(jié)點指針p不為空時，執(zhí)行以下操作if(p=NULL)/如果當(dāng)前結(jié)點指針p為空，執(zhí)行以下操作p=K.pinK.top;/出棧，棧頂元素所指的結(jié)點作為當(dāng)前結(jié)點pK.top-;printf(%d ,p-data);/輸出當(dāng)前結(jié)點p中的數(shù)據(jù)p=p-rchild;/令當(dāng)前結(jié)點p的rchild域所指的結(jié)點作為當(dāng)前結(jié)點pelse/如果當(dāng)前結(jié)點指針p不為空，執(zhí)行以下操作K.top+;/當(dāng)前結(jié)點指針p入棧K.pinK.top=p;p=p-lchild;/令當(dāng)前結(jié)點p的rchild域所指的結(jié)點作為當(dāng)前結(jié)點pprintf(n);/int main()int key;char a=A,b=B,c;BiTNode *B;/定義根結(jié)點指針SeqStack K;/定義棧并初始化棧K.top=-1;while(a=A)/A表示創(chuàng)建新的二叉排序樹B=(BiTNode *)malloc(sizeof(BiTNode);/申請根結(jié)點B-rchild=NULL;B-lchild=NULL;/令根結(jié)點B的lchild域和rchild域為空Create(B);/創(chuàng)建二叉排序樹Inorder(B,K);/中序遍歷二叉樹中的數(shù)據(jù)while(b=B)/B表示查找數(shù)據(jù)操作printf(輸入待查找數(shù)據(jù):);scanf(%d,&key);/輸入待查找數(shù)據(jù)getchar();Search(B,key);/進(jìn)行查找printf(選擇操作(A.新二叉排序樹;B.繼續(xù)查找;C.結(jié)束操作):);scanf(%c,&c);/根據(jù)提示，選擇下一步操作