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

《二叉排序树的基本操作的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二叉排序树的基本操作的实现I.设计要求1.问题描述从磁盘读入一组数据，建立二叉排序树并对其进行查找、、遍历、插入、删除等基本操作。2.需求分析建立二叉排序树并对其进行查找，包括成功和不成功两种情况。II.概要设计为了实现需求分析中的功能，可以从以下3方面着手设计。1.主界面设计为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主控制子程序以实现二叉排序树的各项功能。本系统的主控制菜单运行界面如图1所示。图1二叉排序树的基本操作的主菜单2.存储结构的设计本程序主要采二叉树结构类型来表示二叉排序树。其中

2、二叉树节点由1个表示关键字的分量组成，还有指向该左孩子和右孩子的指针。3.系统功能设计本程序设置了5个子功能菜单，其设计如下。1)建立二叉排序树。根据系统提示，输入节点的关键字，并以0作为结束的标识符。该功能由BstreeCreate()函数实现。2)插入二叉排序新的节点信息。每次只能够插入一个节点信息，如果该节点已经存在，则不插入。该功能由BstreeInsert(y)函数实现。3)查询二叉排序树的信息。每次进行查询，成功则显示“查询到该节点”，不成功则“显示查询不到该节点“该功能由BstreeSearc

3、h()函数实现。4)删除二叉排序树的节点信息。可以对二叉排序树中不需要的节点进行删除，删除的方式是输入关键字，查询到该节点后删除。该功能由BstreeDelete()函数实现。5)遍历二叉排序树。遍历二叉排序树可以显示该二叉排序树的全部节点信息。该功能由voidTraverse()实现。III.模块设计1.模块设计本程序包含两个模块：主程序模块和二叉排序树操作模块。其调用关系如图2主程序模块二叉排序树操作模块图2模块调用示意图1.系统子程序及其功能设计本系统共设计了5个子程序，个程序的的函数名及其功能说明如

4、下：1)BstreeCreate();//创建二叉排序树2)BstreeInsert(Bstreetree,intkey);//插入3)BstreeSearch(Bstreetree,intkey);//查找4)voidTraverse(Bstreetree);//遍历5)BstreeDelete(Bstreetree,intkey);//删除信息2.函数主要的调用关系本系统9个子程序见的主要调用关系图3.Main()Main()Insert()Search()Traverse()Delete()I.详细设

5、计1.数据类型定义本系统采用二叉树结构存储节点信息，节点定义如下：typedefstructBstnode{intkey;structBstnode*lchild,*rchild;}Bstnode,*Bstree;2.主要子程序的详细设计1)二叉排序树的创建函数，主要用来建立二叉排序树。BstreeCreate(){intkey;Bstreetree=NULL;//初始化空树scanf("%d",&key);while(key!=0){tree=Insert(tree,key);//逐个插入节点scanf(

6、"%d",&key);}returntree;}1)二叉排序插入函数如下：BstreeInsert(Bstreetree,intkey){Bstreep=tree;Bstrees,f;while(p!=NULL){f=p;if(key==p->key)returntree;if(keykey)p=p->lchild;elsep=p->rchild;}s=(Bstree)malloc(sizeof(Bstnode));s->key=key;s->lchild=NULL;s->rchild=NULL;i

7、f(tree==NULL)returns;//新节点为二叉排序树的根if(keykey)f->lchild=s;elsef->rchild=s;returntree;}2)二叉排序树查询函数如下：BstreeSearch(Bstreetree,intkey){Bstreep=tree;intflag=0;while(p!=NULL){if(p->key==key){printf("查询到该节点！");flag=1;return(p);break;}if(keykey)p=p->lchild;

8、elsep=p->rchild;}if(flag==0){printf("查询不到关键字为%d的节点！",key);returnNULL;}}I.测试分析1.二叉排序树的建立首先进入主菜单，如图1。在主菜单下，用户根据菜单的选项输入1，然后按照提示建立二叉排序树，并以0未结束符。运行的结果如图4.图4二叉排序树的建立2.遍历二叉树的节点信息在主菜单下，用户选择4，可以打印出全部的节点信息。运行的结果如图5.图5遍