课程设计--- 二叉排序树的实现

1、课程设计（论文）任务书 软件 学院软件+道路与铁道 专业 2 班 一、课程设计(论文)题目 二叉排序树的实现 二、课程设计(论文)工作自 2012 年 12 月 17日起至2012年 12 月 23日止。三、课程设计(论文) 地点: 15#520 四、课程设计(论文)内容要求：1本课程设计的目的 (1) （1）要求学生达到熟练掌握c 语言的基本知识和技能；(2) 基本掌握面向对象程序设计的基本思路和方法；(3) 能够利用所学的基本知识和技能，解决简单的程序设计问题。 2课程设计的任务及要求1）基本要求：（1）（1）要求利用tc 的编程思想来完成系统的设计；（2）要求在设计的过程中，建立清晰的结

2、构体层次；（3）在系统的设计中，至少要做到基本管理要求。 （4）学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。2）创新要求： 在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面等。3）课程设计论文编写要求（1）要按照书稿的规格打印与写课程设计论文 （2）论文包括目录、功能描述、设计思路、具体实现、运行调试与分析讨论、设计体会与小结、参考文献、附录（源代码）等 （3）课程设计论文装订按学校的统一要求完成4）答辩与评分标准： （1）考勤与学习态度：20分； （2）设计思路：20分；（3）代码实现：20分；（4）调试与分析：20

3、分；（5）回答问题：10分；（6）论文规范性：10分。5）参考文献1严蔚敏，吴伟民，数据结构北京 清华大学出版社2谭浩强，c+程序设计 北京清华大学出版社3谭锋，章伟聪，visual c+程序设计实训教程北京 科学出版社6）课程设计进度安排1准备阶段(2学时):选择设计题目、了解设计目的要求、查阅相关资料2程序模块设计分析阶段（2学时）：程序总体设计、详细设计3代码编写调试阶段（6学时）：程序模块代码编写、调试、测试4撰写课程设计论文阶段（2学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名： 谢岳松 2012年 12 月 24 日课程设计(论文)评审意见（1）考勤与态度 （20分）

4、：优（）、良（）、中（）、一般（）、差（）； （2）设计思路（20分）：优（）、良（）、中（）、一般（）、差（）； （3）代码实现（20分）：优（）、良（）、中（）、一般（）、差（）；（4）调试与分析（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（10分）：优（）、良（）、中（）、一般（）、差（）；（6）论文规范性 （10分）：优（）、良（）、中（）、一般（）、差（）；评阅人： 职称： 讲师 2012 年12月26日 目录绪论- 1 -一、功能描述- 2 -二、设计思路- 2 -三、具体实现- 6 -四、运行调试及结果分析- 14 -五、设计体会与小结- 16 -六、参考

5、文献17七、附录(核心代码)17第- 22 -页 绪论数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。 通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力。 数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实

6、世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，我们都会有不同程度上的提高。一、 功能描述1)以回车(n)为输入结束标志,输入数列l，生成一棵二叉排 序树t； 2)对二叉排序树t作中序遍历，输出结果； 3)输入元素x,查找二叉排序树t,若存在含x的结点,则删除该结点,并作中序遍历(执行操 作2)；否则输出信息“无x”；二、 设计思路算法设计思想二插链表作存储结

7、构： 建立二插排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。 删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。在进行算法设计时，应将题目分为五个函数模块：1、中序遍历，符合升序输出void inorder(no

8、de *&root) if(root!=null) inorder(root-left); coutdataright); 2、在查找树中插入元素void insert(node *&ptr,int item) if(ptr=null) ptr=new node(item); else if(itemdata) insert(ptr-left,item); else insert(ptr-right,item); 3、在查找树中查找元素 node *find(node *&ptr,int item) if(ptr=null) return null; if(ptr-data=item) ret

9、urn ptr; else if(itemdata) find(ptr-left,item); else find(ptr-right,item); 4、在查找树中查找肯定存在的元素,并返回其引用node *&findy(node *&ptr,int item) if(ptr-data=item) return ptr; else if(itemdata) findy(ptr-left,item); else findy(ptr-right,item); node* rl()return left; node* rr()return right;5、删除指定值为所在结点void dele(no

10、de *&ptr) if(ptr-rl()=null&ptr-rr()=null) ptr=null; else if(ptr-rr()=null) ptr=ptr-rl(); else ptr=ptr-rr(); private: int data; node *left; node *right; ;三、 具体实现1.调入文件#include 2.主函数int main() int t,i=0,j; cout 谢岳松-218-二叉排序树的实现 endl; cout1.二叉排序树t的输入:endl; coutt; cout输入tj; node *x=new node(j); for(;ij;

11、 x-insert(x,j); coutinorder(x); /作中序遍历 coutn; cout2.二叉排序树t的元素查找和删除:endl; coutn输入操作(当输入-1时程序结束):j; while(j!=-1) node *t=x-find(x,j); /定位结点 if(t!=null) node *&y=x-findy(x,j); x-dele(y); coutinorder(x); else cout无j; coutn输入操作(当输入-1时程序结束):j; return 0;3.程序编码#include using namespace std;class nodepublic:n

12、ode(int i):data(i), lchild (null), rchild (null) void inorder(node *&root) /中序遍历，符合升序输出 if(root!=null) inorder(root- lchild); coutdata rchild); void insert(node *&ptr,int item) /在查找树中插入元素 if(ptr=null) ptr=new node(item); else if(itemdata) insert(ptr- lchild,item); else insert(ptr- rchild,item); node

13、 *find(node *&ptr,int item) /在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 if(ptr=null) return null; if(ptr-data=item) return ptr; else if(itemdata) find(ptr- lchild,item); else find(ptr- rchild,item); node *&findy(node *&ptr,int item) /在查找树中查找肯定存在的元素,并返回其引用 if(ptr-data=item) return ptr; else if(itemdata) findy(pt

14、r- lchild,item); else findy(ptr- rchild,item); node* rl()return lchild; node* rr()return rchild; void dele(node *&ptr) /删除值为item所在结点 if(ptr-rl()=null&ptr-rr()=null) ptr=null; else if(ptr-rr()=null) ptr=ptr-rl(); else ptr=ptr-rr(); private: int data; node * lchild; /左孩子结点 node * rchild; /右孩子结点;int ma

15、in() int t,i=0,j; cout 谢岳松-218-二叉排序树的实现 endl; cout1.二叉排序树t的输入:endl; coutt; cout输入tj; node *x=new node(j); for(;ij; x-insert(x,j); coutinorder(x); /作中序遍历 coutn; cout2.二叉排序树t的元素查找和删除:endl; coutn输入操作(当输入-1时程序结束):j; while(j!=-1) node *t=x-find(x,j); /定位结点 if(t!=null) node *&y=x-findy(x,j); x-dele(y); co

16、utinorder(x); else cout无j; coutn输入操作(当输入-1时程序结束):j; return 0;四、 运行调试及结果分析输入节点数输入二叉树数，并输出中序遍历当输入25时，二叉树中无该数据，输出无25输入-1表示退出五、 设计体会与小结基于我对编程的极大兴趣，我对这次的课程设计非常重视。通过这次实验我也着实又感受了一次编程的乐趣，从中也学到了不少知识。在这段时间里，我遇到过的问题主要就是c语言和c+语言有些混淆，一些用法记不太清楚。在石红芹老师的指导帮助下，同学们课余时间的讨论中，这些问题都一一得到了解决。在程序的调试能力上，无形中得到了许多的提高。这样无形中就提高了

17、自己编写的程序的质量。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础六、 参考文献1严蔚敏，吴伟民，数据结构北京 清华大学出版社2谭浩强，c+程序设计 北京清华大学出版社3谭锋，章伟聪，visual c+程序设计实训教程北京 科学出版社七、 附录(核心代码)#include using namespace std;class nodepublic:node(int i):data(i), lchild (null), rchild (null) void

18、inorder(node *&root) /中序遍历，符合升序输出 if(root!=null) inorder(root- lchild); coutdata rchild); void insert(node *&ptr,int item) /在查找树中插入元素 if(ptr=null) ptr=new node(item); else if(itemdata) insert(ptr- lchild,item); else insert(ptr- rchild,item); node *find(node *&ptr,int item) /在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 if(ptr=null) return null; if(ptr-data=item) return ptr; else if(itemdata) find(ptr- lchild,item); else find(ptr- rchild,item); node *&findy(node *&ptr,int item) /在查找树中查找肯定存在的元素,并返回其引用 if(ptr-data=item) return ptr; else if(itemdata) findy(ptr- lchild,item); else findy(ptr