二叉排序树的基本操作的实现

二叉排序树的基本操作的实现一 设计要求1.问题描述 从磁盘读入一组数据，建立二叉排序树并对其进行查找、、遍历、插入、删除等基本操作。2.需求分析建立二叉排序树并对其进行查找，包括成功和不成功两种情况。二 概要设计为了实现需求分析中的功能，可以从以下 3 方面着手设计。1.主界面设计为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主控制子程序以实现二叉排序树的各项功能。本系统的主控制菜单运行界面如图 1 所示。图 1 二叉排序树的基本操作的主菜单2.存储结构的设计本程序主要采二叉树结构类型来表示二叉排序树。其中二叉树节点由 1 个表示关键字的分量组成，还有指向该左孩子和右孩子的指针。3.系统功能设计本程序设置了 5 个子功能菜单，其设计如下。1)建立二叉排序树。根据系统提示，输入节点的关键字，并以 0 作为结束的标识符。该功能由 Bstree Create()函数实现。2)插入二叉排序新的节点信息。每次只能够插入一个节点信息，如果该节点已经存在，则不插入。该功能由 Bstree Insert(y)函数实现。3)查询二叉排序树的信息。每次进行查询，成功则显示“查询到该节点”，不成功则“显示查询不到该节点“该功能由 Bstree Search()函数实现。4)删除二叉排序树的节点信息。可以对二叉排序树中不需要的节点进行删除，删除的方式是输入关键字，查询到该节点后删除。该功能由 Bstree Delete()函数实现。 5)遍历二叉排序树。遍历二叉排序树可以显示该二叉排序树的全部节点信息。该功能由 void Traverse()实现。三 模块设计1.模块设计本程序包含两个模块：主程序模块和二叉排序树操作模块。其调用关系如图 2 图 2 模块调用示意图2.系统子程序及其功能设计本系统共设计了 5 个子程序，个程序的的函数名及其功能说明如下：1)Bstree Create(); //创建二叉排序树2)Bstree Insert(Bstree tree,int key); //插入3)Bstree Search(Bstree tree,int key); //查找4)void Traverse(Bstree tree); //遍历5)Bstree Delete(Bstree tree,int key); //删除信息3.函数主要的调用关系图本系统 9 个子程序见的主要调用关系图 3.四 详细设计1.数据类型定义本系统采用二叉树结构存储节点信息，节点定义如下： typedef struct Bstnode{int key;struct Bstnode *lchild,*rchild;}Bstnode,* Bstree;2.主要子程序的详细设计1)二叉排序树的创建函数，主要用来建立二叉排序树。 Bstree Create...