數(shù)據(jù)結(jié)構(gòu) 創(chuàng)建二叉排序樹(shù)與查找.doc

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