數(shù)據(jù)結(jié)構(gòu)_二叉排序樹實(shí)驗(yàn)報告

1、一、實(shí)驗(yàn)?zāi)康?、鞏固和加深對數(shù)據(jù)結(jié)構(gòu)課程基本知識的理解，綜合數(shù)據(jù)結(jié)構(gòu)課程里學(xué)的理論知識，完成對 排序二叉樹程序的設(shè)計。2、 理解和掌握二叉樹的各種基本數(shù)據(jù)結(jié)構(gòu)的定義、存儲結(jié)構(gòu)和相應(yīng)的算法，并能夠用c語言 實(shí)現(xiàn)。3 、理解排序二叉樹的建立過程。二、實(shí)驗(yàn)內(nèi)容采用llink-rlink方式存儲二叉排序樹，編寫能夠通過鍵盤輸入建立二叉排序樹，并在建立完立即在屏幕顯示中序遍歷結(jié)果的程序。三、實(shí)驗(yàn)環(huán)境1、 硬件配置：Pentium （ R） Dual-Core9 CUP E6500 2.93GHz，1.96 的內(nèi)存2、軟件環(huán)境： Microsoft Windows XP Professional Serv

2、ice Pack 3， Microsoft Visual C+6.0四、需求分析1、輸入的形式和輸入值的范圍：根據(jù)題目要求與提示輸入一些數(shù)字，且數(shù)與數(shù)之間用空格隔 開并用0作為結(jié)束符。2、輸出的形式：建立好的排序二叉樹的中序遍歷結(jié)果。3、程序所能達(dá)到的功能：能夠通過鍵盤輸入建立二叉排序樹，并在建立完立即在屏幕顯示中 序遍歷結(jié)果的程序4、 測試數(shù)據(jù)：輸入 45 24 53 12 28 90并用空格將數(shù)隔開，以0作為結(jié)束符，如：輸入 45 24 53 12 28 90輸出的中序遍歷結(jié)果為：12 24 28 45 53 90五、概要設(shè)計為了實(shí)現(xiàn)上述操作，應(yīng)以結(jié)構(gòu)體為存儲結(jié)構(gòu)。實(shí)現(xiàn)如下：struct

3、nodeint key;/關(guān)鍵字的值struct n ode *lchild,*rchild;左右指針BSTNode,*BSTree;1、基本操作：(1) struct nodeint key;/ 關(guān)鍵字的值struct n ode *lchild,*rchild;左右指針BSTNode,*BSTree;。(2) void CreateBST(BSTree *bst)創(chuàng)建二叉排序樹(3) void inorder(BSTree bt)遞歸法中序遍歷二叉排序樹(4) void InsertBST(BSTree *bst,int key)二叉排序樹的插入結(jié)點(diǎn)2、本程序包含二個模塊：(1) 主程序模

4、塊；(2) 創(chuàng)建二叉排序樹、二叉排序樹的插入結(jié)點(diǎn)、遞歸法中序遍歷二叉排序樹(3) 模塊調(diào)用圖：主程序模塊創(chuàng)建二叉排序樹二叉排序樹的插入結(jié)點(diǎn)遞歸法中序遍歷二叉排序樹3、流程圖流程圖如下:結(jié)束六、詳細(xì)設(shè)計1、存儲類型，元素類型，結(jié)點(diǎn)類型：struct nodeint key;/關(guān)鍵字的值struct n ode *lchild,*rchild;左右指針BSTNode,*BSTree;元素類型為整形和指針形。2、每個模塊的分析：(1) 主程序模塊：main ()BSTree bt;printf("please insert the numbers(以 0 作為結(jié)束標(biāo)志):n");

5、CreateBST(&bt); /*構(gòu)造排序二叉樹 */printf("n中序遍歷結(jié)果是:");in order(bt); /*中序遍歷排序二叉樹 */prin tf("n");getchar();(2) 創(chuàng)建二叉排序樹函數(shù)模塊void CreateBST(BSTree *bst)int key;*bst=NULL;scan f("%d", &key);while(key!=0)In sertBST(bst,key);scan f("%d",&key);二叉排序樹的插入結(jié)點(diǎn)函數(shù)模塊void

6、InsertBST(BSTree *bst,int key)BSTree s;if(*bst=NULL)s=(BSTree)malloc(sizeof(BSTNode);s->key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;else if(key<(*bst)->key)將s插入左子串將s插入右子串In sertBST(&(*bst)->lchild),key);else if(key>(*bst)->key)In sertBST(&(*bst)->rchild),key);遞歸法中

7、序遍歷二叉排序樹void in order(BSTree bt)if(bt!=NULL)ino rder(bt->lchild);prin tf("%3d",bt->key);ino rder(bt->rchild);3）函數(shù)調(diào)用關(guān)系圖 main ()CreateBST(BSTree *bst)In sertBST(BSTree *bst,i nt key)in order(BSTree bt)3、完整的程序：#i nclude"stdio.h"#i nclude"malloc.h"typedef struct no

8、deint key;/關(guān)鍵字的值struct n ode *lchild,*rchild;左右指針BSTNode,*BSTree;void In sertBST(BSTree *bst,i nt key) /二叉排序樹的插入結(jié)點(diǎn)BSTree s;if(*bst=NULL)s=(BSTree)malloc(sizeof(BSTNode);s->key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;else if(key<(*bst)->key)InsertBST(&(*bst)->lchild),key);將 s 插

9、入左子串else if(key>(*bst)->key)In sertBST(&(*bst)->rchild),key);void CreateBST(BSTree *bst) /將s插入右子串創(chuàng)建二叉排序樹int key;*bst=NULL;scan f("%d", &key); while(key!=O)In sertBST(bst,key); scan f("%d",&key);void ino rder(BSTree bt)/if(bt!=NULL)ino rder(bt->lchild);prin

10、 tf("%3d",bt->key);ino rder(bt->rchild);遞歸法中序遍歷二叉排序樹main ()BSTree bt;prin tf("please insert the nu mbers(CreateBST(&bt); /*以0作為結(jié)束標(biāo)志):n");構(gòu)造排序二叉樹*/printf("n中序遍歷結(jié)果是：”)；in order(bt); /*中序遍歷排序二叉樹 */prin tf("n");getchar();七、程序使用說明及測試結(jié)果1、程序使用說明(1) 本程序的運(yùn)行環(huán)境為 VC6

11、.0。(2) 進(jìn)入演示程序后即顯示提示信息：請輸入數(shù)字，并以0作為結(jié)束標(biāo)志，回車；即得中序遍歷排序二叉樹結(jié)果2、測試結(jié)果：例如：輸入：45 24 53 12 28 90輸出：12 24 28 45 53 903、調(diào)試中的錯誤及解決辦法。調(diào)試過程中，遇到了許多的問題，如開始生成一棵二叉排序樹的時候，參考書本上的構(gòu)造二叉 排序樹的算法，但是將樹的地址傳遞給函數(shù)的參數(shù)的時候，運(yùn)行程序的過程中有問題，后來講形式 參數(shù)改為 BSTree *bst，本來BSTree bst就相當(dāng)于定義了一個 struct node型的指針，在加*為指向指針的指針。運(yùn)行界面先輸入 45 24 53 12 28 90 后，回車:八、實(shí)驗(yàn)小結(jié)：這次實(shí)驗(yàn)的過程中還是遇到了些許問題，創(chuàng)建二叉排序樹、二