《数据结构》课程设计报告样本001

数据结构课程设计0《数据结构》课程设计报告设计题目：二叉树的遍历姓名：陈诗雨学号：2008k230103专业：软件工程班级：KT923-1指导教师：马春江2011年1月10日数据结构课程设计1目录一、问题描述...............................................................................................................2问题描述：创建二叉树并遍历...............................................................................................2基本要求：...............................................................................................................................2二、需求分析...............................................................................................................2三、概要设计...............................................................................................................21．创建二叉树.........................................................................................................................22．二叉树的非递归前序遍历示意图.....................................................................................23．二叉树的后序非递归遍历示意图.....................................................................................3四、数据结构设计.......................................................................................................31．二叉树结点数据类型定义为：...................................................................................32．二叉树数据类型定义为：...........................................................................................3五、算法设计...............................................................................................................41、创建二叉树.........................................................................................................................42、非递归前序遍历.................................................................................................................53、非递归后序遍历.................................................................................................................54、求二叉树的高度.................................................................................................................65、求二叉树每一层的结点数...........................................................................................76、求两节点最近共同祖先.....................................................................................................76、算法流程图.........................................................................................................................8六、程序测试与实现...................................................................................................91、函数之间的调用关系.........................................................................................................92、主程序.................................................................................................................................93、测试数据...........................................................................................................................114、测试结果...........................................................................................................................11七、调试分析.............................................................................................................12八、遇到的问题及解决办法.....................................................................................13九、心得体会.............................................................................................................13数据结构课程设计2一、问题描述问题描述：创建二叉树并遍历基本要求：1、分别运用非递归的方式完成对二叉树的先序和后序遍历2、输出二叉树的高度3、输出每一层的结点数4、查找结点P和结点Q的最近共同祖先二、需求分析1．本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2．程序运行后显现提示信息，等候用户输入0—6以进入相应的操作功能。3．用户输入数据完毕，程序将输出运行结果。4．测试数据应为字符型数据。三、概要设计1．创建二叉树输入数据不低于15个，用递归方法建立二叉树。2．二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图数据结构课程设计33．二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图四、数据结构设计1．二叉树结点数据类型定义为：templatetypenameTstructBiNode{BiNodeT*rchild,*lchild;//指向左右孩子的指针Tdata;//结点数据信息};2．二叉树数据类型定义为：templatetypenameTclassBiTree{templatetypenameTfriendostream&operator(ostream&os,BiTreeT&bt);public:BiTree();//无参构造函数BiTree(intm){};//有参空构造函数BiTree(Tary[],intnum,Tnone);//有参构造函数~BiTree();//析构函数voidpreorder();//递归前序遍历voidinorder();//递归中序遍历voidpostorder();//递归后续遍历voidlevelorder();//层序遍历intcount();//计算二叉树的结点数intdepth();//计算二叉树的深度数据结构课程设计4voiddisplay(ostream&os);//打印二叉树，有层次voidLevelNum();//计算每一层结点数voidPreOrder();//非递归前序遍历voidPostOrder();//非递归后序遍历voidcreat();//创建二叉树TleastCommanAncestor(Tva,Tvb);//求树中任意两结点最近共同祖先protected://以下函数供上面函数调用//对应相同功能voidcreat(BiNodeT*&root);//创建voidrelease(BiNodeT*&root);//删除BiNodeT*Build(Tary[],intnum,Tnone,intidx);//用数组创建二叉树voidPreOrder(BiNodeT*root);//前序遍历voidPostOrder(BiNodeT*root);//后续遍历voidLevelNum(BiNodeT*root);//层序遍历voidpreorder(BiNodeT*root);//递归前序遍历voidinorder(BiNodeT*root);//递归中序遍历voidpostorder(BiNodeT*root);//递归后续遍历voidlevelorder(BiNodeT*root);//层序遍历intcount(BiNodeT*root);//计算结点数intdepth(BiNodeT*root);//计算深度voiddisplay(ostream&os,BiNodeT*root,intdep);//打印staticboolleastCommanAncestor(BiNodeT*root,Tva,Tvb,BiNodeT*&result,BiNodeT*parrent);//求最近共同祖先private:BiNodeT*rootptr;};五、算法设计1、创建二叉树//实现外部递归调用voidBiTreeT::creat(){creat(rootptr);}//类体内递归创建二叉树templatetypenameTvoidBiTree