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

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

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

3、，删除的方式是输入关键字，查询到该节点后删除。该功能由BstreeDelete()函数实现。5)遍历二叉排序树。遍历二叉排序树可以显示该二叉排序树的全部节点信息。该功能由voidTraverse。实现。III .模块设计1 .模块设计本程序包含两个模块：主程序模块和二叉排序树操作模块。其调用关系如图210 / 9图2模块调用示意图2 .系统子程序与其功能设计本系统共设计了5个子程序，个程序的的函数名与其功能说明如下:1) BstreeCreate。；创建二叉排序树2) BstreeInsert(Bstreetree,intkey);/插入3) BstreeSearch(Bstreetree,i

4、ntkey);/查找4) voidTraverse(Bstreetree);遍历5) BstreeDelete(Bstreetree,intkey);/删除信息3 .函数主要的调用关系本系统9个子程序见的主要调用关系图3.IV .详细设计1 .数据类型定义本系统采用二叉树结构存储节点信息，节点定义如下：typedefstructBstnodeintkey;structBstnode*lchild,*rchild;Bstnode,*Bstree;2 .主要子程序的详细设计1)二叉排序树的创建函数，主要用来建立二叉排序树。BstreeCreate()int key;Bstree tree=NULL

5、;初始化空树scanf("%d",&key);while(key!=0)tree=Insert(tree,key);逐个插入节点scanf("%d",&key);returntree;2)二叉排序插入函数如下：BstreeInsert(Bstreetree,intkey)Bstreep=tree;Bstrees,f;while(p!=NULL)f=p;if(key=p->key)returntree;if(key<p->key)p=p->lchild;elsep=p->rchild;s=(Bstree)mal

6、loc(sizeof(Bstnode);s->key=key;s->lchild=NULL;新节点为二叉排序树的根s->rchild=NULL;if(tree=NULL)returns;if(key<f->key)f->lchild=s;elsef->rchild=s;returntree;3) 二叉排序树查询函数如下：BstreeSearch(Bstreetree,intkey)Bstreep=tree;intflag=0;while(p!=NULL)if(p->key=key)printf("查询到该节点!");flag=

7、1;return(p);break;if(key<p->key)p=p->lchild;elsep=p->rchild;if(flag=0)printf("查询不到关键字为d的节点！",key);returnNULL;V.测试分析1.二叉排序树的建立首先进入主菜单，如图1。在主菜单下，用户根据菜单的选项输入1,然后按照提示建立二叉排序树，并以0未完毕符。运行的结果如图4.(*欢迎您使用本系统建人找历电 普查一-i 2 3 4 _5 6叉排序树密飘爨相去回为结束符:113314555879880选择的功能：图4二叉排序树的建立2.遍历二叉树的节点信息5

8、.在主菜单下，用户选择4,可以打印出全部的节点信息。运行的结果如图5 :54为-例44t 能序能 胃33功 的 择历11择79图5遍历二叉排序树3.插入节点信息信息6.在主菜单下，用户选择2,可以插入一个新的节点信息。运行的结果如图5:5 啜力 1列44点：552 J的列44:肥序能番能答33功士得33功3的一后的叶历11择人入11择图6插入新的节点4 .查询二叉树的节点信息在主菜单下，用户选择3,首先通过输入关键字查询相关信息。运行的结果如图7.55 Sfl &7；5656的节点！：67'门HB图7查询节点信息4 433居天下一 的查到的查座 11择人不怪 选星选帮好5 .删

9、除二叉树的节点在主菜单下，用户选择5,可以通过输入要删除的关键字来删除该节点的全部信息。运行的结果如图8.图8删除二叉排序树的节点VI.原程序清单#include<stdio.h>#include<stdlib.h>#include<malloc.h>/*二叉排序树的数据结构*/typedefstructBstnodeintkey;structBstnode*lchild,*rchild;Bstnode,*Bstree;BstreeCreate();创建二叉排序树BstreeInsert(Bstreetree,intkey);插入BstreeSearch(B

10、streetree,intkey);查找voidTraverse(Bstreetree);遍历BstreeDelete(Bstreetree,intkey);/删除/*创建二叉排序树*/BstreeCreate。intkey;初始化空树Bstreetree=NULL;scanf("%d",&key);while(key!=0)tree=Insert(tree,key);scanf("%d",&key);returntree;逐个插入节点/*插入*/BstreeInsert(Bstreetree,intkey)Bstreep=tree;Bs

11、trees,f;while(p!=NULL)f=p;if(key=p->key)returntree;if(key<p->key)p=p->lchild;elsep=p->rchild;s=(Bstree)malloc(sizeof(Bstnode);s->key=key;s->lchild=NULL;s->rchild=NULL;if(tree=NULL)returns;if(key<f->key)f->lchild=s;elsef->rchild=s;returntree;新节点为二叉排序树的根/*查找*/Bstree

12、Search(Bstreetree,intkey)Bstreep=tree;intflag=0;while(p!=NULL)if(p->key=key)printf("查询到该节点！");flag=1;return(p);break;if(key<p->key)p=p->lchild;elsep=p->rchild;if(flag=0)printf（"查询不到关键字为d的节点！",key）;returnNULL;遍历 */*voidTraverse(Bstreetree)if(tree)Traverse(tree->l

13、child);printf("%4d",tree->key);Traverse(tree->rchild);/*删除*/BstreeDelete(Bstreetree,intkey)Bstreep=tree;Bstreef,s,q;f=NULL;key的节点while(p)查找关键字为if(p->key=key)break;f=p;if(p->key>key)p=p->lchild;elsep=p->rchild;if(p=NULL)returntree;if(p->lchild=NULL)|(p->rchild=NUL

14、L)if(f=NULL)if(p->lchild=NULL)tree=p->rchild;elsetree=p->lchild;elseif(p->lchild=NULL)if(f->lchild=p)f->lchild=p->rchild;elsef->rchild=p->rchild;elseif(f->lchild=p)f->lchild=p->lchild;elsef->lchild=p->lchild;free(p);elseq=p;s=p->lchild;while(s->rchild)

15、q=s;s=s->rchild;if(q=p)q->lchild=s->lchild;p->key=s->key;free(s);returntree;/*/voidmain()system("color1E");Bstreetree,p;intkey1,key2,key3;intselect,flag;printf("#'n");printf("|*欢迎您使用本系统*|'n")printf("|*|n");printf("|*1.创建二叉排序树*|n&quo

16、t;);printf("|*2.插入*|n");printf("|*3.查找*|n");printf("|*4.遍历*|n");printf("|*5.删除*|n");printf("|*6.退出*|n");printf("*n");while(select!=6)printf("选择的功能：");scanf("%d",&select);case 1:case 2:switch(select)printf("请输入节点

17、信息(0为完毕符):n");tree=Create();printf("n");break;printf("插入一个新的节点：")；scanf("%d",&key1);Insert(tree,key1);printf("插入后得序列为：n");Traverse(tree);printf("n");break;case 3: printf("输入查找的数据：")；scanf("%d”,&key2);p=Search(tree,key2);pr

18、intf("n");break;case 4: printf("遍历所得序列为：n");Traverse(tree);printf("n");break;case 5: printf("输入删除的数据：")；scanf("%d",&key3);tree=Delete(tree,key3);printf("删除后遍历所得序列：n");Traverse(tree);printf("n");break;case 6: printf("谢谢您的使用，再见！n");flag=0;break;defaul