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

二叉排序树的基本操作的实现I. 设计要求1. 问题描述 从磁盘读入一组数据，建立二叉排序树并对其进行查找、遍历、插入、删除等基本操作。2. 需求分析建立二叉排序树并对其进行查找，包括成功和不成功两种情况。II. 概要设计为了实现需求分析中的功能，可以从以下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()实现。III. 模块设计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.Main()Main()Insert()Search( )Traverse ()Delete ()IV. 详细设计1. 数据类型定义本系统采用二叉树结构存储节点信息，节点定义如下： typedef struct Bstnodeint key;struct Bstnode *lchild,*rchild;Bstnode,* Bstree;2. 主要子程序的详细设计1) 二叉排序树的创建函数，主要用来建立二叉排序树。 Bstree Create() 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(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; 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; else p=p-rchild; if(flag=0)printf(查询不到关键字为%d的节点！,key);return NULL; V. 测试分析1. 二叉排序树的建立首先进入主菜单，如图1。在主菜单下，用户根据菜单的选项输入1，然后按照提示建立二叉排序树，并以0未结束符。运行的结果如图4. 图4二叉排序树的建立2. 遍历二叉树的节点信息在主菜单下，用户选择4，可以打印出全部的节点信息。运行的结果如图5. 图5遍历二叉排序树3. 插入节点信息信息在主菜单下，用户选择2，可以插入一个新的节点信息。运行的结果如图6.图6插入新的节点4. 查询二叉树的节点信息在主菜单下，用户选择3，首先通过输入关键字查询相关信息。运行的结果如图7. 图7查询节点信息5. 删除二叉树的节点在主菜单下，用户选择5，可以通过输入要删除的关键字来删除该节点的全部信息。运行的结果如图8. 图8删除二叉排序树的节点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); /删除/*创建二叉排序树*/Bstree Create() 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)malloc(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; else p=p-rchild; if(flag=0)printf(查询不到关键字为%d的节点！,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;while(p) /查找关键字为key的节点if(p-key=key) break; f=p; if(p-keykey) 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-rchild)q=s;s=s-rchild; if(q=p) q-lchild=s-lchild;p-key=s-key; free(s);return tree;/*/void main() system(color 1E);Bstree tree,p;int key1,key2,key3;int select,flag;printf(#n);printf(|* 欢迎您使用本系统 *|n);printf(|*|n);printf(|* 1.创建二叉排序树 *|n);printf(|* 2.插入 *|n);printf(|* 3.查找 *|n);printf(|* 4.遍历 *|n);printf(|* 5.删除 *|n);printf(|* 6.退出 *|n);printf(*n);while(select!=6) printf(选择的功能：); scanf(%d,&select); switch(select) case 1: printf(请输入节点信息(0为结束符):n); tree=Create(); printf(n); break; case 2: printf(插入一个新的节点:); scanf(%d,&key1);Insert(tree,key1); printf(插入后得序列为:n); Traverse(tree); printf(n); break; case 3: printf(输入查找的数据:); scanf(%d,&key2); p=Search(tree,key2); printf(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; default:printf(输入错误,请重新输入n);brea