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

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