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

《二叉排序树的基本操作的实现》由会员分享，可在线阅读，更多相关《二叉排序树的基本操作的实现（9页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

5、int key;Bstree tree=NULL;初始化空树scanf(%d,&key);while(key!=0)tree=Insert(tree,key);逐个插入节点scanf(%d,&key); return tree; 2)二叉排序插入函数如下： Bstree Insert(Bstree tree,int key) Bstree p=tree;Bstree s,f;while (p!=NULL) f=p;if(key=p-key) return tree;if(keykey) p=p-lchild; else p=p-rchild; s=(Bstree)malloc(sizeof(B

6、stnode); s-key=key;s-lchild=NULL;新节点为二叉排序树的根s-rchild=NULL;if(tree=NULL) return s;if(keykey) f-lchild=s;else f-rchild=s; return tree;3)二叉排序树查询函数如下：Bstree Search(Bstree tree,int key)Bstree p=tree;int flag=0;while(p!=NULL) if(p-key=key) printf(查询到该节点!);flag=1;return(p); break; if (keykey) p=p-lchild;el

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

8、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 .删除二叉树的节点在主菜单下，用户选择5,可以通过输入要删除的关键字来删除该节点的全部 信息。运行的结果如图 8.图8删除二叉排序树的

9、节点VI.原程序清单#include#include#include/* 二叉排序树的数据结构*/typedef struct Bstnodeint key;struct Bstnode *lchild,*rchild;Bstnode,* Bstree;Bstree Create();创建二叉排序树Bstree Insert(Bstree tree,int key); 插入Bstree Search(Bstree tree,int key); 查找void Traverse(Bstree tree);遍历Bstree Delete(Bstree tree,int key); / 删除/*创建二

10、叉排序树*/BstreeCreate。int key;初始化空树Bstree tree=NULL; scanf(%d,&key); while(key!=0)tree=Insert(tree,key); scanf(%d,&key);return tree;逐个插入节点/*插入 */Bstree Insert(Bstree tree,int key)Bstree p=tree;Bstree s,f;while (p!=NULL)f=p;if(key=p-key) return tree; if(keykey) p=p-lchild; else p=p-rchild;s=(Bstree)mall

11、oc(sizeof(Bstnode);s-key=key;s-lchild=NULL;s-rchild=NULL;if(tree=NULL) return s;if(keykey) f-lchild=s;else f-rchild=s;return tree;新节点为二叉排序树的根/*查找 */Bstree Search(Bstree tree,int key) Bstree p=tree;int flag=0;while(p!=NULL)if(p-key=key) printf(查询到该节点！);flag=1;return(p);break;if (keykey) p=p-lchild;el

12、se p=p-rchild;if(flag=0)printf（查询不到关键字为的节点！ ,key）;return NULL;遍历 */* void Traverse(Bstree tree) if(tree)Traverse(tree-lchild);printf(%4d,tree-key);Traverse(tree-rchild);/*删除 */Bstree Delete(Bstree tree,int key) Bstree p=tree;Bstree f,s,q;f=NULL;key的节点while(p)查找关键字为if(p-key=key) break;f=p;if(p-keykey

13、) p=p-lchild;else p=p-rchild;if (p=NULL) return tree;if (p-lchild=NULL)|(p-rchild=NULL)if(f=NULL)if(p-lchild=NULL) tree=p-rchild;else tree=p-lchild;else if (p-lchild=NULL)if(f-lchild=p) f-lchild=p-rchild;else f-rchild=p-rchild;else if(f-lchild=p) f-lchild=p-lchild;else f-lchild=p-lchild;free(p);else q=p;s=p-lchild;while(s-