二叉排序树的基本操作

1、数据结构课程设计专 业：XXX班 级：XXX学 号：XXX姓 名：XXX日期： 年 月 日一、 需求分析动态查找表在查找过程中可改变表的状态，即可插入或删除数据，它适合用在表的内容要经常变化的情况下，如飞机航班的旅客信息表。二、 概要设计1、 主界面设计 为了实现对二叉排序树各功能的管理，设计一个多菜单的菜单，方便用户使用本系统。本系统主控菜单运行界面如下图所示。2、 存储结构设计本系统选取二叉链表作为二叉排序树的存储结构3、 系统功能设计本系统设置了5个资功能的设计，如下：（1） 建立二叉排序树可以一次输入多个数据，建立二叉排序树。但是只能建立一次，一旦选择输入后就会被锁定，不能再次输入。通

2、过CreateBST(BiTree & T)函数实现。（2） 查找需求的数据输入一个数据进行查找，用SearchBST (BiTree T, KeyType key)函数来实现（3） 插入一个数据根据给定的数据进行查找，若没有，则插入，用InsertBST(BiTree &T, TElemType e)函数来实现（4） 删除数据选择一个数据进行删除操作DeleteBST(BiTree &T, KeyType key)（5） 遍历输出二叉排序树通过三种顺序进行遍历，可以选择先，中，后序的方式，PreOrderTraverse(BiTree T)，InOrderTraverse(BiTree T)

3、， PostOrderTraverse(BiTree T)三、 详细设计1、 数据类型定义本系统采用链式结构存储信息。结点定义如下：typedef structKeyType key;TElemType;2、 系统主要子函数详细设计建立二叉排序树：Status CreateBST(BiTree & T)int k;TElemType a10;cout请输入要输入的个数：k;cout请依次输入这些数，回车结束：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); 四、 测试分析(一) 在建立二叉排序树上，应该输入一次，这样才能有序有效，故，采用一开即闭的操作(二) 输入时，应该先给出循环次数，这样便于操作(三) 进行2至5的操作时，必须先建立二叉排序树五、 使用说明1) 本程序执行文件为“test.exe”。2) 进入本系统之后，随即显示系统主菜单。用户可以键入对应功能的数字选项，执行对应的功能3) 本程序没有直接修改的功能，可以通过查找，删除，插入完成此功能4) 根据提示进行各项操作六、 测试结果1. 在主菜单下，用户输入1并回车，然后按照提示建立二叉排序树，运行结果如下图：2. 在主菜单下，用户输入2并回车，然后按照提示查询数据

6、，运行结果如下图：3. 在主菜单下，用户输入3并回车，然后按照提示插入数据，运行结果如下图：4. 在主菜单下，用户输入4并回车，然后按照提示删除数据，运行结果如下图：5. 在主菜单下，用户输入5并回车，然后按照提示遍历输出，运行结果如下图：6. 在主菜单下，用户输入0并回车，然后按照提示进行退出，运行结果如下图：代码：#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请输入要输入的个数：k;cout请依次输入这些数，回车结束：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、创建 * 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已经创建，不可重复操作！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这个数为：data.keyendl;else cout查无该数据！endl;else cout二叉排序树尚未建立，先建立它！endl;coutendl;break;case 3:system(cls);In

15、terface1(); if(flag=1)TElemType insert;int mark1;cout请输入要插入的数据insert.key;mark1=InsertBST(BST,insert);if(mark1) cout数据库没有该数据，插入成功！endl;else cout数据库已有该数据！endl;else cout二叉排序树尚未建立，先建立它！endl;coutendl;break;case 4:system(cls);Interface1(); if(flag=1)KeyType remove;intmark2;cout请输入要删除的数据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先序遍历的结果为：endl;PreOrderTraverse(BST);coutendl;coutendl;break;case 2:system(cls);cout中序遍历的结果为：endl;InOrderTraverse(BST);coutendl;coutendl;break;case 3:system(cls);cout后序遍历的结果为：endl;PostOrderTraverse(BST);coutendl;coutendl;break;cas