安徽理工大学数据结构课程设计说明书 题目: 二叉树的遍历集成 院 系： 计算机科学与工程学院 专业班级： 学 号： 学生姓名： 指导教师： 2015年 01 月 9 日安徽理工大学课程设计（论文）任务书 计算机科学与工程 学院 信息安全教研室学 号学生姓名专业（班级）设计题目 二叉树遍历的集成设计技术参数系统平台：windows 7开发工具：VC6.0+设计要求（1） 实现二叉树的各种遍历。包括先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。（2） 要求能查找任一结点在某种遍历序列中的前驱和后继。（3） 界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划2015年1月5日 分配程序任务，小组内每人做不同模块2015年1月6日 完成先序中序后序三个遍历递归算法2015年1月7日 完成先序中序后序三个遍历非递归算法2015年1月7日 完成线索化二叉树并查找节点的前驱后继2015年1月8日 完成主函数，采用友好的选择菜单页面2015年1月9日 完成设计报告，并打印参考资料1严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社,1997.4指导教师签字教研室主任签字 2014年 12 月 18 日 目录1.需求分析12、 总体设计12.1 程序目录12.2 算法流程33、 详细设计33.1 界面设计33.2 详细代码设计43.3 调试分析104、 总结14参考文献15代码详述15 41.需求分析 “数据结构”是计算机程序设计的重要理论技术基础,它不仅是计算机学科的核心,而且也成为其他理工类学科必修课程,所谓”数据结构”是相互之间存在一种或多种特定关系的数据元素的集合.数据元素之间的相互关系成为结构,结构一般有线性结构,树形结构,图状结构,本程序所做的就是树形结构的二叉树的遍历算法和线索化查找. 本程序使用VC6.0+编写,具体实现功能有二叉树的遍历,包括先序遍历,中序遍历,后序遍历的递归算法以及非递归算法.另外本程序还有可线索化二叉树的功能,由此可以得到二叉树某个节点的前驱和后继.题目要求为:1.实现二叉树的各种遍历。包括先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。 2.要求能查找任一结点在某种遍历序列中的前驱和后继。3.界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。 由小组一起制作,本人做小组汇总工作,并在基础上加了查找某个节点是否存在二叉树,以及求二叉树总节点数等一些简单功能2、 总体设计2.1 程序目录(1) typedef struct node 二叉树的定义,包含数据域data,左孩子lchild,右孩子rchild,若二叉树为空,则头结点指向空指针,并且data数据域为字符型数据.(2) BiTree CreatBiTree1(BiTree &T) 创建一颗二叉树,需要按照先序遍历输入相应字符才能构造出二叉树,其中用星号”*”来代表空字符.(3) void Preorder1(BiTree T) 先序遍历递归算法,调用此函数可以获得输入二叉树的先序序列(4)void Preorder2(BiTree T) 先序遍历非递归算法,和上面一样,调用此函数可以获得二叉树先序序列(5) void Inorder1(BiTree T) 中序遍历递归算法,调用此函数可以获得输入二叉树的中序序列(6) void Inorder2(BiTree T) 中序遍历非递归算法,和上面一样,调用此函数可以获得二叉树中序序列(7) void Postorder1(BiTree T) 后序遍历递归算法,调用此函数可以获得输入二叉树的后序序列(8) void Postorder2(BiTree &T)和typedef struct stacknode 后序遍历非递归算法,和其中用到的哨兵结构体.调用此函数可以获得二叉树后序序列(9) void Levelorder(BiTree T,int NodeNum) 层序遍历二叉树,需要手动输入节点数,然后即可进行二叉树的层序遍历,输出遍历结果(10) void InThreading(BiTree p) 线索化二叉树中需要用到的线索化前驱和后继(11) void InOrderThreading(BiTree &Thrt,BiTree T) 以中序遍历来线索化二叉树,让空节点分别指向当前节点的前驱后继(12) BiTree Inprenode(BiTree p)和BiTree Inpostnode(BiTree p) 线索化后用此函数查找二叉树的前驱和后继(13) BiTree search(BiTree BT,char x) 查找某个二叉树节点,其中x为要查找节点的data域的值(14) main( ) 主函数利用while()和switch()语句构造可视化友好界面2.2 算法流程 小组分工设计独立的函数,比如三种遍历,层序遍历,二叉树线索化等,然后再综合起来,用主函数调用即可Postorder1Inorder2Preorder2Postorder2Inorder1Preorder1CreatBiTree1mainsearchInThreadingLevelorderInOrderThreadingInprenodeInpostnode3、 详细设计3.1 界面设计（1）打开程序后首先是按照先序序列输入二叉树，其中用“*”号表示空节点。图1 二叉树输入界面（2）输入完二叉树后进入功能选择页面，选择对应的编号，实行相应的操作图2 二叉树功能选择页面3.2 详细代码设计（1）创建一个二叉树，用户按照二叉树先序遍历顺序输入相应data域数据，使用getchar（）读入并赋给c，利用T节点，以及左右递归，即可建立出一颗二叉树。BiTree CreatBiTree1(BiTree &T) char ch; if(ch=getchar()=*) T=NULL; /读入星号，返回空指针 else T=(BiTNode *)malloc(sizeof(BiTNode);/生成结点if(!T)return 0;T-data=ch;T-LTag=0;T-RTag=0; CreatBiTree1(T-lchild); /构造左子树 CreatBiTree1(T-rchild); /构造右子树 return(T); （2）先序递归算法，读取头节点后，输出，接下来使用递归算法，不断地向下延伸读取，输出即可。void Preorder1(BiTree T) if(T) printf(%c,T-data); /访问结点 Preorder1(T-lchild); /先序遍历左子树 Preorder1(T-rchild); /先序遍历右子树 (3)先序遍历非递归算法，设置一个stack的栈用来存储读取的二叉树序列,利用栈先进后出的特性,输出栈即为先序遍历.void Preorder2(BiTree T)BiTree stackMax,p;int top;if( T!=NULL)top=0;p=T;while(p!=NULL|top0)while(p!=NULL)printf(%c,p-data);stacktop=p;top+;p=p-lchild;if(top0)top-; p=stacktop;p=p-rchild;(4) 中序遍历递归算法和先序遍历思想差不多,只是在遍历完左边后再输出头节点.void Inorder1(BiTree T) if(T) Inorder1(T-lchild); /中序遍历左子树 printf(%c,T-data); /访问结点 Inorder1(T-rchild); /中序遍历右子树(5) 中序遍历非递归算法,同理也是利用栈的特性来存储读取出来的data域的值,修改下出栈方式即可.void Inorder2(BiTree T) BiTree stackMax,p;int top;if( T!=NULL)top=0;p=T;while(p!=NULL|top0)while(p!=NULL)stacktop=p;top+;p=p-lchild;if(top0)top-; p=stacktop; printf(%c,p-data);p=p-rchild;(6) 后序遍历递归算法和先序遍历思想差不多,只是在遍历完最后后再输出头节点.void Postorder1(BiTree T) if(T) Postorder1(T-lchild); /后序遍历左子树 Postorder1(T-rchild); /后序遍历右子树 printf(%c,T-data); /访问结点(7) 后序遍历非递归算法,首先设置一个typedef struct stacknode的结构体为监查哨兵,输出过的节点都做上标记,防止二次输出.typedef structBiTree ptr;int tag;stacknode; /设置哨兵void Postord