数据结构课程设计_二叉排序树

1、641二叉排序树基本操作的实现专业:*学号:*日期：2011-9-17问题描述二，需求分析三，概要设计四，详细设计五，测试分析六，源程序清单七，用户使用手册八，心得体会问题描述从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化输出操作。二、需求分析1. 读入给定的数据，构造二叉排序树，实现初始化。2. 给定数据的格式为，第一行为元素个数，遇 0 退出程序。3. 提供菜单功能，选项包括查找、插入、删除和打印等。三、概要设计1. 数据结构：struct nodeint num;node *chl,*chr;分别定义了指向左右子树的指针。2. 函数介绍void Insert(const

2、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. 函数形参部分形参使用引用的方式进行传递，还有些使用的是指针的指针，这样 保传入的指针指向的容可以被修改，并且函数返回之后可以继续

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);else Insert(temp,&(*root)-chl);/ 插入函数，使用递归的方式进行插入，并动态创建对象void Delete(const int &key,node *p)if( *p=NULL )cout 删除错误，不存在该元素！ num=key )if( (*p)-

4、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(

5、(*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

6、( p-numkey )return Find(key,p-chl,net,depth); elsereturn Find(key,p-chr,net,depth);/查找函数，参数*net用以指向当前比较的指针，但却没有具体实现输出 其指向的信息，觉得即便输出对本程序意义不大，所以没有具体关注。depth 为查找需要的次数。void Prin t(c onst node *p) if( p=NULL ) return;coutp-num chl);Prin t(p-chr); /只提供了中序遍历输出的情况，其他情况没考虑五、测试分析1.测试环境：Code： Blocks 10.05.2.输入

7、过程:课本提供数据:11 33 44 55 58 79 88菜单插入jk选项菜单插入查找曲 DocuMents and 5ehlnc?user面Ibiziry sortXlinMcbiicl)iT)aEy sort.| |两种查找情况 一貝非予树演TF中序遍历二叉排序榊1 33 4d G5 5S ?9 ae5-退出菜单2 查找4.删除-二賈序树示一一4.1BX遍历5-退出栗单jj人诜项；2匸恳C:KDocuaents and SettincsXus&riqbinary sac-tbinDeluc13iiiaxy rtI |的入查找元素i删除操作插入操作c C: Docu*euts and St

8、tl incXuseiX面IbiziBiy sort XbinXDELucKtiiiiaE； sart二叉排序树演示菜单插入艮岀菜单輸入选项|33 2 44 55 5B ?9 80Ld六、源程序清单#in elude #in elude #in elude #i nclude #in elude using n amespaee std;struet no deint num;node *chl,*chr;；bool flagdel;ifstream in (sort.txt);void In sert(e onst int &temp ,node *root)if( *root=NULL )

9、*root = new no de;(*root)-ehl = (*root)-ehr = NULL; (*root)-num = temp;else if( (*root)-num vtemp )In sert(temp，&(*root)-chr);elseIn sert(temp，&(*root)-ehl);void Delete(const int &key,node *p)if( *p=NULL )endl;coutnum=key )if( (*p)-chl=NULL )temp = *p;*p = (*p)-chr;delete temp;else if( (*p)-chr=NULL

10、 )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 Fi

11、nd(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

12、 choice,num,depth;node *net;bool suc;coutendlttendl;- 二 叉 排 序 树 演示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 插入成功！

13、 endl; break;case 2: cout 输入查找元素： num; if( *root=NULL ) cout 二叉树为空，查找失败！ endl; else depth = 0; net = NULL; suc = Find(num,*root,net,depth);if( suc ) cout 查找成功。 endl;else cout 查找失败，没有该元素。 endl;cout 查找深度 : depthendl; break;case 3: cout 中序遍历二叉排序树 endl; if( *root=NULL )cout 二叉树为空！ endl; elsePrint(*root)

14、; 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