二叉排序树的基本操作的实现————————————————————————————————作者: ————————————————————————————————日期:二叉排序树的基本操作的实现一设计要求1.问题描述从磁盘读入一组数据,建立二叉排序树并对其进行查找、、遍历、插入、删除等基本操作。
2.需求分析建立二叉排序树并对其进行查找,包括成功和不成功两种情况。
二概要设计为了实现需求分析中的功能,可以从以下3方面着手设计。
1.主界面设计为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主控制子程序以实现二叉排序树的各项功能。
本系统的主控制菜单运行界面如图1所示。
图1二叉排序树的基本操作的主菜单2.存储结构的设计本程序主要采二叉树结构类型来表示二叉排序树。
其中二叉树节点由1个表示关键字的分量组成,还有指向该左孩子和右孩子的指针。
3.系统功能设计本程序设置了5个子功能菜单，其设计如下。
1)建立二叉排序树。
根据系统提示,输入节点的关键字,并以0作为结束的标识符。
该功能由Bｓtｒee Creａte（)函数实现。
2)插入二叉排序新的节点信息。
每次只能够插入一个节点信息，如果该节点已经存在,则不插入。
该功能由Bstree Inｓerｔ(y)函数实现。
3)查询二叉排序树的信息。
每次进行查询,成功则显示“查询到该节点”,不成功则“显示查询不到该节点“该功能由Ｂsｔree Seaｒcｈ()函数实现。
4)删除二叉排序树的节点信息。
可以对二叉排序树中不需要的节点进行删除，删除的方式是输入关键字，查询到该节点后删除。
该功能由ＢｓtreeＤelete()函数实现。
5)遍历二叉排序树。
遍历二叉排序树可以显示该二叉排序树的全部节点信息。
该功能由ｖoｉd Ｔraveｒse()实现。
三模块设计1.模块设计本程序包含两个模块:主程序模块和二叉排序树操作模块。
其调用关系如图2图2模块调用示意图2. 系统子程序及其功能设计本系统共设计了5个子程序,个程序的的函数名及其功能说明如下：1) Bstr ｅe Cr ｅa ｔe （); /／创建二叉排序树2) Bs ｔｒee I ｎsert(Bst ｒｅｅ ｔree,i ｎt key); ／/插入3) Bst ｒee Search （Bstree tree ，i ｎt key); ／／查找4) vo ｉｄ Ｔraverse （Ｂst ｒｅe tree); //遍历5) Bst ｒee Delete(Ｂs ｔｒee tr ｅe,i ｎt ｋe ｙ)； //删除信息3. 函数主要的调用关系图本系统9个子程序见的主要调用关系图3.四 详细设计1. 数据类型定义本系统采用二叉树结构存储节点信息,节点定义如下：ｔypede ｆ struct Bstno ｄe{ﻩint ｋey;ﻩs ｔｒuc ｔ B ｓt ｎｏde ＊lchild,*ｒchild;}Ｂstnode,＊ Bst ｒｅe;2. 主要子程序的详细设计1) 二叉排序树的创建函数，主要用来建立二叉排序树。
Bs ｔree Cre ａt ｅ(){ｉnt key; 主程序模二叉排序树Main(Main()Inser Searc Trave DeletﻩBsｔrｅe tree=NULＬ; //初始化空树sｃａnf("%ｄ＂,&ｋey)；ﻩwｈｉle（keｙ!=0)ﻩ{ﻩｔree＝Ｉnserｔ(tree,kｅy）；//逐个插入节点ﻩscaｎf("%ｄ",&key）；ﻩ}ﻩreturｎtｒee;}2)二叉排序插入函数如下：Bｓｔree Iｎsert(Bstreｅｔrｅｅ，int key)｛Bsｔreeｐ=treｅ;ﻩBｓｔｒｅe s,f;while (p!=ＮＵLL）ﻩ｛ﻩf=p;ﻩiｆ(key＝＝p->kｅy)retｕrn tree;ﻩｉf(kｅy＜p->key）ｐ＝p-＞ｌｃhild;ﻩelsｅp=p->ｒchiｌd;}s=（Ｂstree)ｍaｌloc(ｓｉzeoｆ(Ｂstnode）);ﻩs-＞keｙ＝ｋey；ﻩs->lchild=NＵＬL;ｓ－>ｒcｈiｌd=ＮUＬL;ﻩｉf（trｅe=＝NULL)return s;//新节点为二叉排序树的根ﻩif(kｅy<f->key)f->lｃhild=s;eｌsｅｆ->ｒchilｄ=s;ﻩretｕrn ｔrｅe；}3)二叉排序树查询函数如下:Bstree Search(Bsｔｒｅｅtree，ｉntｋey){Ｂstrｅｅp＝trｅe;ｉnt flag=０；whiｌe(ｐ!=NUＬL）｛ﻩﻩiｆ(ｐ－＞key=＝ｋey)ﻩ{printf(＂查询到该节点!");ﻩｆlａg=１;ﻩﻩｒeturｎ(p);ﻩbrｅak;}if (ｋey<p-＞key) p=p->lｃｈｉld;ﻩeｌｓｅp＝p->rcｈild;}iｆ(ｆlaｇ=＝0）ﻩ{ﻩprｉntf（"查询不到关键字为%d的节点！",ｋeｙ）;ﻩﻩreturn NULL;ﻩ}｝五测试分析1.二叉排序树的建立首先进入主菜单，如图１。
在主菜单下,用户根据菜单的选项输入1，然后按照提示建立二叉排序树，并以0未结束符。
运行的结果如图4．图4二叉排序树的建立2.遍历二叉树的节点信息在主菜单下，用户选择4，可以打印出全部的节点信息。
运行的结果如图5.图5遍历二叉排序树3.插入节点信息信息在主菜单下，用户选择2,可以插入一个新的节点信息。
运行的结果如图6.图６插入新的节点4.查询二叉树的节点信息在主菜单下，用户选择３，首先通过输入关键字查询相关信息。
运行的结果如图７.图７查询节点信息5.删除二叉树的节点在主菜单下,用户选择5，可以通过输入要删除的关键字来删除该节点的全部信息。
运行的结果如图8.图８删除二叉排序树的节点6.退出在主菜单下，用户输入6并回车，即退出“二叉树基本操作程序”。
六原程序清单＃ｉnclｕde<stｄio．h>#inｃlude<ｓtｄlib.h＞#inｃlude＜malloｃ.h＞/**＊＊*＊二叉排序树的数据结构********/tyｐｅdeｆstｒuｃt Bｓtnode｛ﻩiｎt key;stｒuct Bstｎｏde＊lｃhｉld,＊ｒcｈｉlｄ;}Bstｎode，* Bｓｔree;Bstree Ｃｒeate（)；//创建二叉排序树Bｓtree Inserｔ(Ｂｓtreeｔree,int key); //插入BstｒeeＳeａrcｈ（Bstｒee ｔree,int key); /／查找void Traveｒse(Bstree tｒee）; //遍历Ｂｓtree Dｅlｅte(Bstｒｅe tree,int key); //删除/*******＊＊***＊********创建二叉排序树******＊*******/BｓｔreｅCrｅａte()｛ｉnｔkey;ﻩＢstree treｅ=NULL; /／初始化空树ﻩscａnf（"%d",&key);ﻩwhilｅ（key!=0){treｅ=Insert(tｒee,key）; /／逐个插入节点ﻩｓcanｆ("%d",&key）;ﻩ｝ﻩretｕrｎｔree;｝/****＊***＊*＊＊＊＊＊＊**＊插入＊*＊**＊******＊****＊**＊/Bstree Iｎseｒｔ(Bstree tree,iｎt ｋey){Bstrｅe p=tｒee;ﻩBsｔｒeｅs,f；ﻩwhile (ｐ！=NULL)ﻩ{ﻩﻩf=ｐ;ﻩｉf(key=＝p－>keｙ) reｔurn trｅｅ;ﻩｉf(keｙ＜ｐ->ｋｅy) ｐ=p->lｃhild;ﻩelse p=p->rｃhiｌd;ﻩ}ｓ＝(Bstreｅ)mａlloc(sizeｏf(Ｂstnoｄe)）;s－>key＝kｅy;ﻩs-＞lｃhilｄ=NUＬL;ﻩs->ｒｃhilｄ=NULL;ﻩｉf（treｅ==NULＬ）return s; /／新节点为二叉排序树的根if(ｋey<f－>key) f->lchilｄ=s;ﻩelse ｆ-＞ｒchｉld=ｓ；ﻩretｕrｎtree;}／＊*＊**＊*＊＊＊*＊**查找**＊********＊＊*/Bstree Seaｒｃh(Ｂｓｔｒee tｒｅe,int keｙ）{ﻩBsｔreeｐ=treｅ;inｔflag=0;while(p!=ＮULL)ﻩ{ﻩif(p->key==key){ﻩprinｔf（＂查询到该节点!")；ﻩﻩfｌaｇ=1;ﻩﻩreturｎ(p）;ﻩﻩｂreaｋ;ﻩ}if (ｋｅy<p-＞keｙ）ｐ＝p-＞ｌｃhｉld；ﻩﻩelse p=p-＞rｃhilｄ;ﻩ}if(fｌag==0）ﻩ{ﻩﻩprｉntf（"查询不到关键字为%d的节点!",key);ﻩﻩｒetｕrnＮUＬL;ﻩ｝｝/＊****＊＊*＊******遍历**＊*******＊*＊*＊****＊*／vｏid Trａvｅrse（Bstree tｒeｅ）{iｆ（tree）ﻩ{ﻩTraverse（tｒeｅ->lchｉld);pｒinｔf("%4d＂,tree->ｋｅｙ);ﻩＴraversｅ(tｒee－>ｒｃhild);ﻩ}}/**＊*＊**＊*****＊＊删除*＊**＊**＊*＊*******＊*/ＢstreｅDelｅte(Bstｒee tree,int key)｛ﻩBsｔreeｐ=trｅe;Bstrｅｅf，s,q；ｆ=NUＬL;ﻩｗhｉle（p){ //查找关键字为ｋeｙ的节点ﻩｉｆ(p－>key==key) ｂrｅａk;ﻩf=p;ﻩiｆ(p-＞key＞ｋey) ｐ＝p-＞lchilｄ;ﻩelse p=p->rｃｈild;}ﻩif（p==NＵLL)ｒｅｔurn trｅe;iｆ((p-＞ｌｃhilｄ==NULＬ)||(p－＞rchiｌｄ==NULL))｛if（f==ＮULL)ﻩif(p->ｌｃhiｌd==NULL)treｅ=ｐ-＞ｒchild;ﻩelｓe trｅe＝p-＞lｃhilｄ;ﻩeｌse if (p－＞lchilｄ==ＮULＬ)ﻩﻩif(f-＞ｌchild＝＝p) f->lchiｌd=ｐ－>rｃhild;ﻩﻩelsｅｆ->rｃhiｌd=p->rchild;ﻩelse ｉf（f->ｌchilｄ==p) f－>lcｈiｌｄ=ｐ-＞lchiｌd;else f－>ｌchiｌｄ=p->lchiｌｄ;ﻩfree（p）;}ﻩelse{ｑ=p;s=p->ｌchild;ﻩｗhiｌe(s->rchiｌd)ﻩ{ﻩﻩﻩq＝ｓ；s=ｓ－>rchild;ﻩ}if(ｑ=＝p) q->lcｈild=s－>lｃｈild;ﻩｐ－>key=s－>key；ﻩfrｅｅ(ｓ);ﻩ｝ｒetuｒn tｒee;}/*********＊***＊*******＊***＊************＊＊**＊/voｉd main（)｛ｓysｔeｍ(＂cｏlor １E");ﻩBstree tｒｅe,p；iｎt key1，key２,ｋey3;ﻩint select,ｆｌag;ｐrｉｎtf("##＃#########＃#############＃#＃##＃＃##＃##＃##＃#＃＼n＂)；ﻩpｒiｎtf("｜* 欢迎您使用本系统*|\n"）;ﻩpriｎtf("|＊*＊***＊**＊*＊***＊＊**＊**＊**＊****＊***＊*******｜\ｎ＂）；pｒintf（"｜* １.创建二叉排序树*|＼n＂）;ﻩpriｎtf（"|＊ 2.插入＊|\n＂);priｎｔｆ(＂|*3．查找*｜＼n＂); ﻩpriｎtｆ("|* 4.遍历＊|\n"）；ｐrｉntf("|＊ 5.删除*|＼n＂);printf(＂|＊６．退出*|＼n");priｎtf（"**＊*＊*＊***＊**＊******＊*******＊＊**＊＊＊******＊*＊\n");whilｅ(select!＝６)ﻩ{ﻩｐrintf("选择的功能:＂）;ｓcaｎf（＂%d",＆selecｔ);switｃｈ(select）ﻩ {ﻩﻩｃaｓe 1: printｆ("请输入节点信息(0为结束符）:\n");ﻩｔrｅe＝Crｅａte();ｐrintｆ("\n＂);ﻩﻩﻩbreak;casｅ2:printf（＂插入一个新的节点:"）;ﻩﻩｓcaｎf("%ｄ＂,&keｙ1）;Iｎserｔ(ｔree,keｙ１);ﻩprｉnｔf（"插入后得序列为:＼n＂);ﻩﻩTｒavｅrse(treｅ）；ﻩprｉntf("\n");bｒeak；ﻩcase３: pｒiｎｔf（"输入查找的数据:"）;ﻩﻩscanf("%d"，＆key２);p=Search(tree,kｅy2);ﻩｐrｉｎｔf(＂\n")；ﻩbreak;case ４: pｒintｆ("遍历所得序列为:＼n"）;ﻩﻩTraveｒsｅ(trｅe);pｒinｔf(＂＼n＂);ﻩﻩbreak;ﻩ case5:printｆ("输入删除的数据:"）;ﻩﻩﻩsｃanｆ("％d",＆ｋeｙ3);tｒee=Deletｅ（trｅe,keｙ3)；prinｔf("删除后遍历所得序列：\n"）;ﻩTraｖｅrｓe(trｅｅ);pｒintf("＼n＂);brｅaｋ;case 6: prｉntｆ("谢谢您的使用，再见！\n"）;flag=0;bｒeａk；defａult:priｎｔf（＂输入错误，请重新输入＼ｎ＂);brｅak;ﻩ}ﻩ}｝七用户手册运行程序进入本系统后,及显示系统的主菜单。