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