二叉排序樹的基本操作

1、數(shù)據(jù)結(jié)構(gòu)課程設計專 業(yè)：XXX班 級：XXX學 號：XXX姓 名：XXX日期： 年 月 日一、 需求分析動態(tài)查找表在查找過程中可改變表的狀態(tài)，即可插入或刪除數(shù)據(jù)，它適合用在表的內(nèi)容要經(jīng)常變化的情況下，如飛機航班的旅客信息表。二、 概要設計1、 主界面設計 為了實現(xiàn)對二叉排序樹各功能的管理，設計一個多菜單的菜單，方便用戶使用本系統(tǒng)。本系統(tǒng)主控菜單運行界面如下圖所示。2、 存儲結(jié)構(gòu)設計本系統(tǒng)選取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)3、 系統(tǒng)功能設計本系統(tǒng)設置了5個資功能的設計，如下：（1） 建立二叉排序樹可以一次輸入多個數(shù)據(jù)，建立二叉排序樹。但是只能建立一次，一旦選擇輸入后就會被鎖定，不能再次輸入。通

2、過CreateBST(BiTree & T)函數(shù)實現(xiàn)。（2） 查找需求的數(shù)據(jù)輸入一個數(shù)據(jù)進行查找，用SearchBST (BiTree T, KeyType key)函數(shù)來實現(xiàn)（3） 插入一個數(shù)據(jù)根據(jù)給定的數(shù)據(jù)進行查找，若沒有，則插入，用InsertBST(BiTree &T, TElemType e)函數(shù)來實現(xiàn)（4） 刪除數(shù)據(jù)選擇一個數(shù)據(jù)進行刪除操作DeleteBST(BiTree &T, KeyType key)（5） 遍歷輸出二叉排序樹通過三種順序進行遍歷，可以選擇先，中，后序的方式，PreOrderTraverse(BiTree T)，InOrderTraverse(BiTree T)

3、， PostOrderTraverse(BiTree T)三、 詳細設計1、 數(shù)據(jù)類型定義本系統(tǒng)采用鏈式結(jié)構(gòu)存儲信息。結(jié)點定義如下：typedef structKeyType key;TElemType;2、 系統(tǒng)主要子函數(shù)詳細設計建立二叉排序樹：Status CreateBST(BiTree & T)int k;TElemType a10;cout請輸入要輸入的個數(shù)：k;cout請依次輸入這些數(shù)，回車結(jié)束：endl;for(int i=0;iai.key;InitDSTable(T);for(int m=0;mk;m+)InsertBST(T, am);return TRUE;遍歷輸出：vo

4、id Visit(TElemType a) cout data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); void InOrderTraverse(BiTree T) if (T) InOrderTraverse(T-lchild); Visit(T-data); InOrderTraverse(T-rchild); void PostOrderTraverse(BiTree T) if (T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); Visit

5、(T-data); 四、 測試分析(一) 在建立二叉排序樹上，應該輸入一次，這樣才能有序有效，故，采用一開即閉的操作(二) 輸入時，應該先給出循環(huán)次數(shù)，這樣便于操作(三) 進行2至5的操作時，必須先建立二叉排序樹五、 使用說明1) 本程序執(zhí)行文件為“test.exe”。2) 進入本系統(tǒng)之后，隨即顯示系統(tǒng)主菜單。用戶可以鍵入對應功能的數(shù)字選項，執(zhí)行對應的功能3) 本程序沒有直接修改的功能，可以通過查找，刪除，插入完成此功能4) 根據(jù)提示進行各項操作六、 測試結(jié)果1. 在主菜單下，用戶輸入1并回車，然后按照提示建立二叉排序樹，運行結(jié)果如下圖：2. 在主菜單下，用戶輸入2并回車，然后按照提示查詢數(shù)據(jù)

6、，運行結(jié)果如下圖：3. 在主菜單下，用戶輸入3并回車，然后按照提示插入數(shù)據(jù)，運行結(jié)果如下圖：4. 在主菜單下，用戶輸入4并回車，然后按照提示刪除數(shù)據(jù)，運行結(jié)果如下圖：5. 在主菜單下，用戶輸入5并回車，然后按照提示遍歷輸出，運行結(jié)果如下圖：6. 在主菜單下，用戶輸入0并回車，然后按照提示進行退出，運行結(jié)果如下圖：代碼：#include#includeusing namespace std;#define FALSE 0#define TRUE 1#define NULL 0#define OVERFLOW -2#define EQ(a,b) (a)=(b)#define LT(a,b) (a)

7、data.key) return T; else if (LT(key, T-data.key) return SearchBST(T-lchild, key); else return SearchBST(T-rchild, key); Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) if (!T) p = f; return FALSE; else if (EQ(key, T-data.key) p = T; return TRUE; else if (LT(key, T-data.key) return Searc

8、hBST(T-lchild, key, T, p); else return SearchBST(T-rchild, key, T, p); Status InsertBST(BiTree &T, TElemType e) BiTree p,s; if (!SearchBST(T, e.key, NULL, p) s = (BiTree)malloc(sizeof(BiTNode); s-data = e; s-lchild = s-rchild = NULL; if (!p) T = s; else if (LT(e.key, p-data.key) p-lchild=s; else p-r

9、child = s; return TRUE; else return FALSE; Status Delete(BiTree &p) BiTree q, s; if (!p-rchild) q = p; p = p-lchild; free(q); else if (!p-lchild) q = p; p = p-rchild; free(q); else q = p; s = p-lchild; while (s-rchild) q = s; s = s-rchild; p-data = s-data; if (q != p) q-rchild = s-lchild; else q-lch

10、ild = s-lchild; free(s); return TRUE; / DeleteStatus DeleteBST(BiTree &T, KeyType key) if(T) if (EQ(key, T-data.key) return Delete(T); else if (LT(key, T-data.key) return DeleteBST(T-lchild, key); else return DeleteBST(T-rchild, key); else return FALSE;Status CreateBST(BiTree & T)int k;TElemType a10

11、0;cout請輸入要輸入的個數(shù)：k;cout請依次輸入這些數(shù)，回車結(jié)束：endl;for(int i=0;iai.key;InitDSTable(T);for(int m=0;mk;m+)InsertBST(T, am);return TRUE;void Visit(TElemType a) cout data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); void InOrderTraverse(BiTree T) if (T) InOrderTraverse(T-lchild); Visit(T-data); InOrd

12、erTraverse(T-rchild); void PostOrderTraverse(BiTree T) if (T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); Visit(T-data); void Interface1()cout*歡迎進行二叉排序樹的操作*endl;coutendl;cout* 1、創(chuàng)建 * 2、查找 *endl;cout* 3、插入 * 4、刪除 *endl;cout* 5、遍歷 * 0、退出 *endl;coutendl;cout*endl;coutendl;void Interface2(

13、)cout*歡迎進行遍歷操作*endl;coutendl;cout* 1、先序 *endl;cout* 2、中序 *endl;cout* 3、后序 *endl;cout* 0、退出 *endl;coutendl;cout*endl;coutendl;int main()Interface1();int flag=0;int choice;int on_off=1;BiTree BST;InitDSTable(BST);while(1)cout選擇你要進行的操作（0-5）：choice;switch(choice)case 1:system(cls);Interface1();if(on_off

14、)flag=CreateBST(BST);on_off=0;else cout已經(jīng)創(chuàng)建，不可重復操作！endl;coutendl;break;case 2:system(cls);Interface1(); if(flag=1)KeyType search;BiTree L;InitDSTable(L);coutsearch;L=SearchBST(BST,search);if(L)cout這個數(shù)為：data.keyendl;else cout查無該數(shù)據(jù)！endl;else cout二叉排序樹尚未建立，先建立它！endl;coutendl;break;case 3:system(cls);In

15、terface1(); if(flag=1)TElemType insert;int mark1;cout請輸入要插入的數(shù)據(jù)insert.key;mark1=InsertBST(BST,insert);if(mark1) cout數(shù)據(jù)庫沒有該數(shù)據(jù)，插入成功！endl;else cout數(shù)據(jù)庫已有該數(shù)據(jù)！endl;else cout二叉排序樹尚未建立，先建立它！endl;coutendl;break;case 4:system(cls);Interface1(); if(flag=1)KeyType remove;intmark2;cout請輸入要刪除的數(shù)據(jù)remove;mark2=Delete

16、BST(BST,remove);if(mark2) cout刪除成功！endl;else cout刪除不成功！endl;else cout二叉排序樹尚未建立，先建立它！endl;coutendl;break;case 5:system(cls); if(flag=1)int sign=1;while(sign)Interface2();int serial_number;cout請輸入一個順序（1-3）：serial_number;switch(serial_number)case 1:system(cls);cout先序遍歷的結(jié)果為：endl;PreOrderTraverse(BST);coutendl;coutendl;break;case 2:system(cls);cout中序遍歷的結(jié)果為：endl;InOrderTraverse(BST);coutendl;coutendl;break;case 3:system(cls);cout后序遍歷的結(jié)果為：endl;PostOrderTraverse(BST);coutendl;coutendl;break;cas