《二叉排序树的操作》课程设计报告.doc

内蒙古科技大学本科生课程设计论文数据结构与算法题 目：二叉排序树的操作学生姓名：贺英杰学 号：1367159108专 业：软件工程班 级：13-1班指导教师：周李涌日 期：2015年1月6日内蒙古科技大学课程设计任务书课程名称数据结构与算法课程设计设计题目二叉排序树的操作指导教师周李涌时间2015.1.52015.1.9一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。二叉排序树的操作以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 创建二叉排序树v 输出二叉排序树v 在二叉排序树中查找给定值v 在二叉排序树中插入新结点v 在二叉排序树中删除给定值 并设计主函数测试该类（或类模板）。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+语言描述，殷人昆 主编，清华大学出版社 2007.6目录目录2第一章需求分析3第二章 总体设计4第三章 抽象数据类型定义53.1 二叉树BT抽象数据类型的设计53.2 BT抽象数据类型的设计6第四章 详细设计74.1工程视图74.2类图视图74.3函数的调用关系84.4主程序流程图94.5主要算法的流程图9第五章 测试13第六章 总结20附录：程序代码21第一章 需求分析二叉排序树的操作以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 创建二叉排序树v 输出二叉排序树v 在二叉排序树中查找给定值v 在二叉排序树中插入新结点v 在二叉排序树中删除给定值 并设计主函数测试该类（或类模板）。第二章 总体设计系统的功能结构：设置二叉排序树根结点、添加二排序叉树结点、删除二排序叉树结点、查找给定的二叉树结点、输出二排序叉树、退出。二叉排序树系统功能结构退出删除二排序叉树结点设置二叉排序树根结点添加二排序叉树结点查找给定的二叉树结点输出二排序叉树功能说明：l 设置二叉排序树根结点：为新创建的二叉排序树创建根节点。l 添加二排序叉树结点：需要输入创建节点的数目，然后创建一定数目的二叉排序树结点。l 删除二排序叉树结点：给定一个数据(字母)，然后查找，找到后删除，否则，告知未找到，l 查找给定的二叉树结点：给定一个数据(字母)，然后查找，并给出提示。l 输出二排序叉树：按照先序遍历并输出二叉排序树的结点数据。l 退出：退出程序。第三章 抽象数据类型定义定义格式如下：第1章第2章第3章3.1 二叉树BT抽象数据类型的设计ADT BT数据对象root：先定义一个二叉树结点的结构体：typedef struct bstchar data;struct bst *left;struct bst *right;struct bst *father;BSTree,*BST;root是指向二叉树结点的指针；数据关系：R=<(V或者C)P(V或者C)>|V,CD, <(V或者C)P(V或者C)>表示由运算符P结合起来的表达式E基本操作：BST InitRoot()操作结果：为空二叉排序树创建一个根节点，输入一个字符型数据，将这个字符型数据存入结点的数据域中同时给左右孩子指针和父指针置空，并返回一个结点的基址给指针。void Inserter(root, key)初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据，有则返回主菜单，没有则就二叉排序树的构造方法返回要插入旳数据应该插入位置的父节点地址，创建一个新结点，将这个字符型数据存入结点的数据域中，并将左右孩子指针置空，父指针指向父节点地址，然后返回主菜单。BSTree *SearchKey(root,key)初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，没有则就返回该数据按照二叉排序树规则，应该插入位置的父节点地址。void DeleteKey(root,key);初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，调用BSTree *SearchKey(root,key)函数，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，然后就此节点的特征分为四类：删除叶子节点；删除只有右孩子的节点；删除只有左孩子的节点；删除左右孩子都有的节点，根据结点类型进入不同删除模块，删除结点，修改相应二叉树结点指针，返回主菜单；没有则就返回提示语句“没有找到该数据”。void ChainTree_LDR(root)初始条件：二叉排序树不为空，存在根节点；操作结果：按照中序遍历并输出有序的数据序列。 ADT BT3.2 BT抽象数据类型的设计class BTprivate:BST root;public:BT() :root(NULL) BST InitRoot();void Inserter(BSTree *t,char key);BSTree *SearchKey(BSTree *t,char key);void DeleteKey(BSTree *t,char key);void ChainTree_LDR(BSTree *bt);第四章 详细设计4.1工程视图 4.2类图视图4.3函数的调用关系main 主程序显示菜单创建根节点插入结点查找结点删除结点中序遍历二叉排序树4.4主程序流程图算法：主程序主要用运了switch结构，使得主程序更加方便的调用成员函数，各个成员函数间的关系也清晰明了。输入与功能相对应的序号执行功能是否存在开始结束否是 4.5主要算法的流程图 BST InitRoot()操作结果：为空二叉排序树创建一个根节点，输入一个字符型数据，将这个字符型数据存入结点的数据域中同时给左右孩子指针和父指针置空，并返回一个结点的基址给指针。开始 输入数据创建根节点 结束输入返回主界面 是否存在结束返回主界面输入数据开始开始void Inserter(root, key)初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据，有则返回主菜单，没有则就二叉排序树的构造方法返回要插入旳数据应该插入位置的父节点地址，创建一个新结点，将这个字符型数据存入结点的数据域中，并将左右孩子指针置空，父指针指向父节点地址，然后返回主菜单。是输入数据 是否存在否创建结点 结束返回主界面开始BSTree *SearchKey(root,key)初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，没有则就返回该数据按照二叉排序树规则，应该插入位置的父节点地址。 否是 返回父地址返回地址void DeleteKey(root,key);初始条件：二叉排序树不为空，存在根节点；操作结果：输入一个字符型数据，调用BSTree *SearchKey(root,key)函数，先寻找二叉排序树中是否有此数据的，有则返回次数据项的地址给指针变量，然后就此节点的特征分为四类：删除叶子节点；删除只有右孩子的节点；删除只有左孩子的节点；删除左右孩子都有的节点，根据结点类型进入不同删除模块，删除结点，修改相应二叉树结点指针，返回主菜单；没有则就返回提示语句“没有找到该数据”。删除是否存在结束返回主界面输入数据开始否是结束输入返回主界面按序输出中序遍历开始void ChainTree_LDR(root)初始条件：二叉排序树不为空，存在根节点；操作结果：按照中序遍历并输出有序的数据序列。第五章 测试1.主界面：2.设置二叉排序树根节点：在主界面输入1，进入“设置二叉排序树根节点”功能，按提示输入根节点数据，结束到主界面。3.添加二叉排序树结点：在主界面时，输入2，进入“添加二叉排序树结点”功能。先进行判空操作，若二叉排序树为空，给出提示：否则按提示输入要添加的结点数目，并依此添加节点数据：4输出二叉排序树：在主界面时，输入5。先进行判空操作，若二叉排序树为空，给出提示：否则中序遍历并输出二叉排序树：5.删除二叉排序树结点： 在主界面，输入3，进入删除界面。先进行判空操作，若二叉排序树为空，给出提示：否则按照提示输入要删除的结点数据：（1）若输入数据在二叉排序树中没有：（2）若输入数据在二叉排序树中存在，则删除：如图所示结点L已删除：6.查找给定二叉排序树结点： 在主界面，输入4，进入查找界面。先进行判空操作，若二叉排序树为空，给出提示：然后按照提示输入要查找的结点数据：（1） 有的话：（2） 没有的话：7.退出程序：在主界面，输入0，退出程序。第六章 总结这次课程设计花费了将近20天时间，这次课程设计在有了前几次课设的经验，困难减少了不少，但也是很艰辛的 ，从最初定稿到最后完成换了三版代码，从一开始的二叉链表加递归操作，递归函数返回值总是出错，到第二次的二叉链表加非递归操作时的操作繁琐，直到最后用了三叉链表加非递归操作，前前后后修改，换思路继续修改，好多回，又逢各种考试堆叠到一起，确实也是苦不堪言。非常感谢周李涌老师的指导，没有老师陪我一坐就是两个小时的帮我纠正错误，估计现在也完不成这收尾工作。今年有意的培养自己在编程方面的兴趣，果然是很有成效的，这次的课设独立完成使我很是振奋，嗯。没啥可说的了，还是那句话，有付出有回报。附录：程序代码#include<stdio.h>#include<stdlib.h>#include<process.h>#include<iostream>#include<iomanip>#include<ctime>using namespace std;typedef struct bstchar data;struct bst *left;struct bst *right;struct bst *father;BSTree,*BST;class BTprivate:BST root;public:BT() :root(NULL) BT();BST InitRoot();void Inserter(BSTree *t,char key);BSTree *SearchKey(BSTree *t,char key);void DeleteKey(BSTree *t,char key);void ChainTree_LDR(BSTree *bt);BSTree* BT:InitRoot()BST node;if(node=new BSTree)cout<<" 输入根节点的数据:"cin>>node->data;node->left=NULL;node->right=NULL;node->father=NULL;return node;/初始化根节点void BT:Inserter(BSTree *t,char key)BSTree *p,*parent,*head;if(!(p=new BSTree)cout<<"申请内存是出错!"exit(0);p->data=key;p->left=NULL;p->right=NULL;p->father=NULL;head=t;while(head)parent=head;if(key<head->data)head=head->left;else if(key>head->data)head=head->right;else if(key=head->data)cout<<"该数据已存在!"break;if(key<parent->data)parent->left=p;p->father=parent;else if(key>parent->data)parent->right=p;p->father=parent;BST BT:SearchKey(BSTree *t,char key)BSTree *parent=NULL,*head;head=t;while(head)parent=head;if(key=head->data)parent=head;break;else if(key<head->data)head=head->left;else if(key>head->data)head=head->right;return parent;void BT:DeleteKey(BSTree *t,char key)BSTree *p=NULL,*q=NULL,*r=NULL;p=SearchKey(t,key); if(p->data=key)if(p->left=NULL&&p->right=NULL) /删除叶子节点if(p->father->left->data=key)r=p;p->father->left=NULL;else if(p->father->right->data=key)p->father->right=NULL;free(p);elseif(p->left=NULL&&p->right!=NULL)/删除只有右孩子的节点if(t->data=key)q=t;t->right->father=NULL;t=q->right;free(q);else if(p->father->left=p)q=p;p->right->father=p->father;p->father->left=p->right;free(q);else if(p->father->right=p)q=p;p->right->father=p->father;p->father->right=p->right;free(q);elseif(p->left!=NULL&&p->right=NULL)/删除只有左孩子的节点if(t->data=key)q=t;t->left->father=NULL;t=t->left;free(q);else if(p->father->left=p)q=p;p->left->father=p->father;p->father->left=p->right;free(q);else if(p->father->right=p)q=p;p->left->father=p->father;p->father->right=p->right;free(q);elseif(p->left!=NULL&&p->right!=NULL)/删除左右孩子都有的节点BSTree *b;q=p->right;while(q)b=q;q=q->left;p->data=b->data;if(b->right!=NULL)b->right->father=b->father;b->father->right=b->right;else if(b->right=NULL)b->father->right=NULL;free(b);else if(p->data!=key) cout<<"没有找到该数据!"void BT:ChainTree_LDR(BSTree *bt)if(bt)ChainTree_LDR(bt->left);cout<<setw(3)<<bt->data;ChainTree_LDR(bt->right);return;/先序递归遍历二叉树int main()system("color 0E");BT a;BSTree *root=NULL;int select1,n,i;char key,key1,key2;dolong t;time(&t);cout<<endl;cout<<" 当前时间："cout<<ctime(&t)<<endl;cout<<"n >>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<< "cout<<"n >>>> 1.设置二叉排序树根结点 <<<< "cout<<"n >>>> 2.添加二排序叉树结点 <<<< "cout<<"n >>>> 3.删除二排序叉树结点 <<<< "cout<<"n >>>> 4.查找给定二叉树结点 <<<< "cout<<"n >>>> 5.输出二排序叉树 <<<< "cout<<"n >>>> 0.退出 <<<< "cout<<"n 请选择:"cin>>select1;switch(select1)case 1:cout<<endl;root=a.InitRoot();break;case 2:cout<<endl;if(root=NULL)cout<<" 空树!禁止操作!"cout<<endl;elsecout<<" 请输入你要添加的结点数目:"cin>>n;fflush(stdin);for(i=0;i<n;i+)cout<<" 请输入你要添加的结点数据:"cin>>key;a.Inserter(root,key);fflush(stdin);break;case 3:cout<<endl;if(root=NULL)cout<<" 空树!禁止操作!"cout<<endl;elsecout<<" 请输入你要删除的结点数据:"fflush(stdin);cin>>key1;a.DeleteKey(root,key1);cout<<endl;break;case 4:cout<<endl;if(root=NULL)cout<<" 空树!禁止操作!"cout<<endl;elseBSTree *key;cout<<" 请输入你要查找的结点数据:"fflush(stdin);cin>>key2;key=a.SearchKey(root,key2);if(key->data=key2)cout<<"二叉树中有此数据!"cout<<endl;elsecout<<"二叉树中没有此数据!"cout<<endl;break;case 5:cout<<endl;if(root=NULL)cout<<" 空树!禁止操作!"cout<<endl;elsea.ChainTree_LDR(root);cout<<endl;break;case 0:exit(0);break;system("pause");cout<<endl;cout<<endl;cout<<endl;cout<<endl;while(select1!=0);return 0;