C++课程设计（论文）二叉树的应用.doc

课程设计报告书二叉树的应用2010-10Hunan Normal UniversityELECTRONIC & INFORMATION ENGINEERING DEPARTMENT课程设计题目二叉树的应用指导教师姓名指导老师职称学生姓名所属班级任务要求二叉树的中序、前序、后序的递归与非递归遍历算法，按层次遍历的非递归遍历算法的实现，应包含建树的实现，树与二叉树的转换的实现主要实施步骤1、 构造二叉树，树以及相关的数据结构2、 建立二叉树3、 二叉树的不同遍历4、 树的遍历5、 树与二叉树的转换6、 届面的设计结论通过这次的课程设计，进一步的加强了对二叉树及树的了解，尝试了种新的建树的方法，通过类似于建查找二叉树：大的是兄弟，小的孩子来建树，这样不会限制树的维度，只根据于用户输入的数据来建，降低了用户输入的难度。另外，也发现将二叉树用于其它的系统的数据存储，查找时会比较容易，以后可试着研究把二叉树作为一种有效的存储手段。湖南师范大学工学院电子与信息工程系课程设计登记表注：此表格内容中的任务要求为指导教师提供的课程设计要求，主要实施步骤是指课程设计的时间安排，结论是指通过课程设计得出的有关结论及课程设计不足之处或进一步开发方向。目 录1引言4 1.1 课程设计目标41.2编程工具（编程环境）介绍41.3实施时间及主要实施步骤42.需求分析43系统总体设计54数据结构设计55详细设计与实现6 5.1功能模块1 65.1.1详细设计6 5.1.2算法流程65.1.3界面设计及测试结果75.2功能模块8 5.2.1详细设计85.2.2算法流程85.2.3界面设计及测试结果105.3功能模块12 5.3.1详细设计125.3.2算法流程125.3.3界面设计及测试结果146算法分析157、测试结果158结论229参考文献221 引言1.1 课程设计目标1、 建树的实现2、 二叉树的中序、前序、后序的递归与非递归遍历算法的实现3、 按层次遍历的非递归遍历算法的实现4、 树与二叉树的转换的实现1.2 编程工具（编程环境）介绍在Windeow X P 下用的 Dev-c+ 4.9.9.2 编程工具C+是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。1.3 实施时间及主要实施步骤 实施时间：9月13号9月24号 主要实施步骤：1、构造二叉树，树以及相关的数据结构 2、建立二叉树3、二叉树的不同的遍历 4、树的遍历 5、树与二叉树的转换 6、届面的设计2 需求分析本程序的功能是采用查找二叉树的方法建树，并对二叉树进行递归前序遍历、中序遍历和后序遍历，用栈实现非递归的前序、中序和后序遍历，还有对二叉树的层次遍历，以及树的建立，树的广度优先和深度优先遍历，树与二叉树的转换。本程序要求用户以字符输入，以#结束输入，采用查找二叉树的方法建树。本程序输出结果以用户要求为准，可打印出二叉树的递归与非递归的先序、中序和后序遍历以及层次遍历，还有树的广度优先和深度优先遍历以及树转换成二叉树后的先序遍历。演示程序以用户与计算机对话的方式进行，即在计算机终端上显示提示信息后，由用户在键盘上输入相应动作的序号和相应的输入数据。测试数据：第一组：j ld e b a h i u x f d h n 第二组：7 4 3 2 8 9 0 第三组：* ） （ ？ < > % ! = + 3 系统总体设计系统共分为三个模块：first,arytree,ntreefirst模块是作为与用户交流的第一个接口，通过它将选择是对树或二叉树进行操作。arytree模块是对二叉树的全部操作，它又分为建树（maketree）模块、先序遍历（xianxu）模块、中序遍历（zhongxu）模块、后序遍历（houxu）模块、层次遍历（cenchi）模块，它们分别完成二叉树的建立，以及递归和非递归的先序遍历、中序遍历、后序遍历和层次遍历算法。ntree模块是对树的全部操作，它又分为建树（makentree）模块、深度优先遍历（shendu）模块、广度优先遍历（guangdu）模块、树转换成二叉树（change）模块，它们分别完成树的建立，以及深度优先、广度优先和树转换成二叉树算法。4 数据结构设计二叉树的数据结构：1、 二叉树结点：JieDian:classdata:charleftchild:JieDian *rightchild:JieDian *2、 二叉树结构：Tree:structcurrent:JieDian *end:JieDian *houxu(JieDian *):intmaketree():intxianxu(JieDian *):intzhongxu(JieDian *):intcenchi():voidhouxu():voidxianxu():voidzhongxu():voidTree():Constructor3、 二叉树队列：Treequeue:structaddress:JieDian *next:Treequeue *4、 二叉树栈结点：StackNode:structtreeaddress:JieDian *next:StackNode *5、 二叉树栈：Stack:structhead:StackNode *tail:StackNode *pop():JieDian *push(JieDian *):voidStack():Constructor6、 树结点：Ntreenode:structdata:charbrother:Ntreenode *child:Ntreenode *7、 树结构：Ntree:structcurrentn:Ntreenode *endn:Ntreenode *change(Tree *tree):intguangdu(Ntreenode *):intmakentree():intshendu(Ntreenode *):intNtree():Construdtor8、 树栈结点：StackNodes:strudttreeaddress:Ntreenode *next:StackNodes *9、 树栈：Stacks:structhead:Stacknodes *tail:Stacknodes *pop():Ntreenode *push(Ntreenode *):voidStacks():Constructor10、树队列：Ntreequeue:structaddress:Ntreenode *next:StackNodes *5 详细设计与实现5.1 功能模块1详细设计5.1.1 详细设计 1) 模块名称first2) 功能说明调用one模块输出系统首界面提供给用户选择想要的操作对象：树和二叉树，选择树后会调用tree模块或选择二叉树调用arytree模块 3) 输入参数的名称、数据类型、顺序位置、格式无输入参数4) 输出参数的名称、数据类型、顺序位置、格式无返回参数，打印输出画面为5) 所调用的其他功能构件one,ntree,arytree6) 被调用的其他功能构件ntree,arytree5.1.2 算法流程调用ntree模块选择序号输入调用arytree模块退出102void first()int i;one();while(1) cin>>i; if(i>=0&&i<=2) break; else cout<<"您输入的数据有误，请重新输入:"continue; switch(i) case 1:arytree();break; case 2:ntree();break; case 0:system("PAUSE");exit(0);break; 5.1.3 界面设计及测试结果对本功能模块的界面设计做详细阐述，并给出测试的结果5.2 功能模块2详细设计5.2.1 详细设计 1) 模块名称 arytree2) 功能说明调用各子模块完成二叉树的建树及根据用户的要求完成二叉树的先序、中序和后序遍历。3) 输入参数的名称、数据类型、顺序位置、格式无输入参数4) 输出参数的名称、数据类型、顺序位置、格式各种遍历的结果5) 所调用的其他功能构件two,Tree,6) 被调用的其他功能构件first5.2.2 算法流程先用Tree类型建立一个二叉树后根据用户输入的操作选择，对二叉树进行相应的操作建一个二叉树输入对应操作的序号退出先序遍历二叉树后序遍历二叉树中序遍历二叉树返回first模块01294层次遍历二叉树3void arytree() Tree tree; tree.maketree(); while(1) two(); int n; cin>>n; switch(n) case 1:cout<<"递归先序遍历二叉树：" tree.xianxu(tree.current); cout<<endl; cout<<"非递归先序遍历二叉树：" tree.xianxu(); break; case 2:cout<<"递归中序遍历二叉树：" tree.zhongxu(tree.current); cout<<endl; cout<<"非递归中序遍历二叉树：" tree.zhongxu(); break; case 3:cout<<"递归后序遍历二叉树：" tree.houxu(tree.current); cout<<endl; cout<<"非递归后序遍历二叉树：" tree.houxu(); break; case 4:cout<<"层次遍历二叉树：" tree.cenchi(); break; case 9:first();break; case 0:system("PAUSE");exit(0);break; if(n>=1&&n<=4) continue; else break; 5.2.3 界面设计及测试结果.5.3 功能模块3详细设计5.3.1 详细设计1) 模块名称 ntree2) 功能说明调用各子模块完成树的建树及根据用户的要求完成树的广度优先以及深度优先遍历，和树转换成二叉树。3) 输入参数的名称、数据类型、顺序位置、格式等无输入参数4) 输出参数的名称、数据类型、顺序位置、格式等、树的广度优先遍历与深度优先遍历的结果及树转换成二叉树后的先序遍历结果5) 所调用的其他功能构件three,NTree6) 被调用的其他功能构件first5.3.2 算法流程建一个树输入对应操作的序号退出广度优先遍历二叉树树转换成二叉树深度优先遍历二叉树返回first模块01293void ntree() NTree ntree; ntree.makentree(); Tree *tree; while(1) int m; three(); cin>>m; switch(m) case 1:cout<<"树的深度优先遍历：" ntree.shendu(ntree.currentn); break; case 2:cout<<"树的广度优先遍历：" ntree.guangdu(); break; case 3:ntree.change(tree); break; case 9:first();break; case 0:system("PAUSE");exit(0);break; if(m>=1&&m<=3) continue; else break; 5.3.3 界面设计及测试结果6 算法分析创建二叉树 , 时间复杂度 O(n) ， 空间复杂度 O(n)树对二叉树的转换, 这里不确定树的维度因此时间复杂度O(m*m*n),空间复杂度 O(n),m是指树的维度先序遍历二叉树（递归）, 时间复杂度 O(2 * n) ， 空间复杂度 O(1)n 是这里的总结点个数,因为这里要访问到每个叶子结点的子结点，所以是O(2*n)，但是这里的递归调用的时候还要很多保护场景操作所要的时间先序遍历二叉树（非递归）, 时间复杂度O(n*n) ， 空间复杂度 O(n)中序遍历二叉树（递归）, 时间复杂度 O(n) ， 空间复杂度 O(1)中序遍历二叉树（非递归）, 时间复杂度 O(n*n) ， 空间复杂度O(n)后序遍历二叉树（递归）, 时间复杂度O(n) ， 空间复杂度 O(1)后序遍历二叉树（非递归）, 时间复杂度 O(n*n) ， 空间复杂度O(n)层遍历二叉树（非递归）, 时间复杂度 O(n) ， 空间复杂度 O(n)7 。测试结果第一组测试数据：j l d e b a h I u x f d h n 第二组：7 4 3 2 8 9 0 第三组：* ） （ ？ < > % ! = + 8 结论通过这次的课程设计，进一步的加强了对二叉树及树的了解，尝试了种新的建树的方法，通过类似于建查找二叉树：大的是兄弟，小的孩子来建树，这样不会限制树的维度，只根据于用户输入的数据来建，降低了用户输入的难度。另外，也发现将二叉树用于其它的系统的数据存储，查找时会比较容易，以后可试着研究把二叉树作为一种有效的存储手段。但在这次的课程设计中也发生了自己的许多不足，缺乏动手能力使得在实际编写时小错误不断，自己的有一些想法也难以真正的得以实现。9 参考文献钱能.C+程序设计教程（第二版）.北京：清华大学出版社，2005。严蔚敏 吴伟民.数据结构（C语言版）.北京：清华大学出版社，1997。