数据结构课程设计-二叉排序树.doc

6.4.1二叉排序树基本操作的实现 专业：*姓名：*学号：*日期：2011-9-17一， 问题描述二， 需求分析三， 概要设计四， 详细设计五， 测试分析六， 源程序清单七， 用户使用手册八， 心得体会一、 问题描述从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化输出操作。二、 需求分析1. 读入给定的数据，构造二叉排序树，实现初始化。2. 给定数据的格式为，第一行为元素个数，遇0退出程序。3. 提供菜单功能，选项包括查找、插入、删除和打印等。三、 概要设计1.数据结构：struct nodeint num;node *chl,*chr;分别定义了指向左右子树的指针。2.函数介绍void Insert(const int &temp,node *root);void Delete(const int &key,node *p);bool Find(const int &key,node *p,node *net,int &depth);void Print(const node *p);bool Menu(node *root);函数如其名，功能也亦如其名。另外为了防止边界情况，如空树或者没有指定元素的非法删除以及查找，所以会在函数内部直接进行判断，以及状态返回判断等。3. 函数形参部分形参使用引用的方式进行传递，还有些使用的是指针的指针，这样保传入的指针指向的内容可以被修改，并且函数返回之后可以继续指向原有内容。四、 详细设计void Insert(const int &temp,node *root)if( *root=NULL )*root = new node;(*root)-chl = (*root)-chr = NULL;(*root)-num = temp;else if( (*root)-numchr);elseInsert(temp,&(*root)-chl);/ 插入函数，使用递归的方式进行插入，并动态创建对象。void Delete(const int &key,node *p)if( *p=NULL )cout删除错误，不存在该元素！num=key )if( (*p)-chl=NULL )temp = *p;*p = (*p)-chr;delete temp;else if( (*p)-chr=NULL )temp = *p;*p = (*p)-chl;delete temp;elsetemp = (*p)-chl;node *front=NULL;while( temp-chr )front = temp;temp = temp-chr;front-num = temp-num;if( front!=temp )front-chr = temp-chl;elsefront-chl = temp-chl;delete temp;else if( (*p)-numkey )Delete(key,&(*p)-chl);elseDelete(key,&(*p)-chr);/ 删除函数。按照规则，分三种情况进行删除，最后还会销毁指针指向的对象。如果某个元素不在其中，那么最后指向的指针必然为空。另外之前没考虑到删除失败的状态返回情况，所以后面使用了一个全局变量来作为补救标记。bool Find(const int &key,node *p,node *net,int &depth)if( p=NULL )return false;depth+;net = p;if( p-num=key )return true;else if( p-numkey )return Find(key,p-chl,net,depth);elsereturn Find(key,p-chr,net,depth);/ 查找函数，参数 *net用以指向当前比较的指针，但却没有具体实现输出其指向的信息，觉得即便输出对本程序意义不大，所以没有具体关注。depth为查找需要的次数。void Print(const node *p)if( p=NULL )return;coutnumchl);Print(p-chr);/ 只提供了中序遍历输出的情况，其他情况没考虑。五、 测试分析1. 测试环境：Code：Blocks 10.05.2. 输入过程：课本提供数据：711 33 44 55 58 79 88两种查找情况 删除操作 插入操作 六、 源程序清单#include #include #include #include #include using namespace std;struct nodeint num;node *chl,*chr;bool flagdel;ifstream in(sort.txt);void Insert(const int &temp,node *root)if( *root=NULL )*root = new node;(*root)-chl = (*root)-chr = NULL;(*root)-num = temp;else if( (*root)-numchr);elseInsert(temp,&(*root)-chl);void Delete(const int &key,node *p)if( *p=NULL )cout删除错误，不存在该元素！num=key )if( (*p)-chl=NULL )temp = *p;*p = (*p)-chr;delete temp;else if( (*p)-chr=NULL )temp = *p;*p = (*p)-chl;delete temp;elsetemp = (*p)-chl;node *front=NULL;while( temp-chr )front = temp;temp = temp-chr;front-num = temp-num;if( front!=temp )front-chr = temp-chl;elsefront-chl = temp-chl;delete temp;else if( (*p)-numkey )Delete(key,&(*p)-chl);elseDelete(key,&(*p)-chr);bool Find(const int &key,node *p,node *net,int &depth)if( p=NULL )return false;depth+;net = p;if( p-num=key )return true;else if( p-numkey )return Find(key,p-chl,net,depth);elsereturn Find(key,p-chr,net,depth);void Print(const node *p)if( p=NULL )return;coutnumchl);Print(p-chr);bool Menu(node *root)int choice,num,depth;node *net;bool suc;coutendltt-二叉排序树演示-endl;coutendlendltttt菜单endlendl;coutt 1.插入 t2.查找endlendl;coutt 3.遍历 t4.删除endlendl;coutt 5.退出菜单endlendlendl;coutchoice;if( choice=5 )return false; coutendlendl;switch( choice )case 1:cout输入要插入的数字：num;Insert(num,&(*root);cout插入成功！endl;break;case 2:cout输入查找元素：num;if( *root=NULL )cout二叉树为空，查找失败！endl;elsedepth = 0;net = NULL;suc = Find(num,*root,net,depth);if( suc )cout查找成功。endl;elsecout查找失败，没有该元素。endl;cout查找深度 : depthendl;break;case 3:cout中序遍历二叉排序树endl;if( *root=NULL )cout二叉树为空！endl;elsePrint(*root);break;case 4:cout输入要删除的数字：num;flagdel = true;Delete(num,&(*root);if( flagdel ) cout删除成功！endlendl;break; case 5: return false;default:cout错误选择。endl;coutendlendl;return true;int main()int i;int num,depth;bool first=true;couttttt*初始化*endlnum,num )first = false;node *root= NULL;depth=0;vector ve(num+1);coutendl依