《二叉排序树的基本操作》由会员分享，可在线阅读，更多相关《二叉排序树的基本操作（8页珍藏版）》请在金锄头文库上搜索。
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); InOrderTraverse(T-rchild); void PostOrderTraverse(BiTree T)
