数据结构课程设计实验2打印树形结构.doc

数据结构课程设计实验报告实验二 树和图部分选题为：6.4.6打印树形结构1、 需求分析（1） 创建二叉树。按照用户需要的二叉树，构建二叉树（2） 将创建的二叉树以凹入表形式打印出来。（3） 对二叉树以中序遍历方式遍历（4） 通过结点的深度标志位控制打印时结点的横向位置2、 概要设计为了实现以上功能，可以从以下3个方面着手设计。（1） 主界面设计为了实现二叉树相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本程序。本系统主控菜单运行界面如下所示。（2） 存储结构设计本程序采用二叉链式存储类型（BITNode）存储二叉树的节点信息。二叉树的链表中的结点包含四个域：数据域（data）、左孩子指针域（lchild）、有孩子指针域（rchild）和结点深度标志域（depth）。（3） 系统功能设计本程序设计了3个功能子菜单，其描述如下： 二叉树的初始化。由函数CreatTree（）实现。该功能按照自上而下从左往右的顺序输入二叉树结点，构造二叉树。 打印树形结构。由函数RDL（）实现。该函数实现二叉树的中序遍历，并同时格式化输出结点的数据信息。 退出操作。由exit（0）函数实现。3、 模块设计 模块设计本程序包含两个模块：主程序模块和二叉树操作模块。其调用关系如下图所示：主程序模块二叉树操作模块 系统子程序及功能设计本系统共设置3个子程序，各程序的函数名及功能说明如下：a. BiTree CreatTree()/建立二叉树，并返回根指针b. void RDL(BiTree T)/使用RDL的中序遍历方式遍历二叉树，并输出打印结果c. void main()/主函数。调用二叉树操作模块 函数主要调用关系图本系统3个子程序之间的主要调用关系如图所示。main（）RDL(Bitree T)CreatTree()4、 详细设计（1） 数据类型定义typedef struct BiTNode/定义二叉树结点char data;struct BiTNode *lchild;/左孩子指针struct BiTNode *rchild;/有孩子指针int depth;/结点深度，用于打印控制横向的位置BiTNode,*BiTree;（2）系统主要子程序详细设计建立二叉树模块BiTree CreatTree()/建立二叉树，并返回根指针int front,rear;front=1;rear=0;char ch;/由于接收输入的字符char c;BiTree T,s;T=NULL;/初始置空二叉树printf(创建二叉树，请输入结点信息:(空结点请输入:#，结束请输入:)n);c=getchar();/用于消除菜单键的回车ch=getchar();/接收第一个字符while(ch!=)s=NULL;/s为新结点if(ch!=#)/为非空结点s=(BiTree)malloc(sizeof(BiTree);s-data=ch;s-lchild=NULL;/左右孩子置空s-rchild=NULL;s-depth=0;/深度置为0rear+;Qrear=s;/新结点进入队列if(rear=1)/为第一个结点T=s;elseif(s!=NULL&Qfront!=NULL)/孩子和双亲结点均不为空结点if(rear%2=0)Qfront-lchild=s;/rear偶数时,为父结点的左孩子elseQfront-rchild=s;/rear奇数时,为父结点的右孩子s-depth=Qfront-depth+1;if(rear%2=1)front+;/结点的两个孩子均已处理ch=getchar();/继续下一个输入return T;中序遍历并输出二叉树模块void RDL(BiTree T)/使用RDL的中序遍历方式，便于打印结果if(T)RDL(T-rchild);/递归遍历右子树for(int i=0;idepth;i+)printf(t);/输出格式控制printf(%4cn,T-data);/输出结点信息RDL(T-lchild);/递归遍历左子树5、 测试分析（1） 实验中遇到的问题以及对设计与实现的回顾讨论和分析 二叉树建立时，在输入格式中，以Enter键入作为结束标志，结果导致二叉树不能建立，原因是因为菜单键中的Enter存在于缓冲区并输入到二叉树中，直接结束了。后经排查，发现了问题，将结束符用特定的作为结尾，成功实现建立功能 同样是在二叉树的建立过程中，原先在CreatTree（）函数中，并未使用一个单独的字符接收菜单中的回车字符，导致二叉树根结点建立的时候其数据为回车字符。经过加入字符c吸收回车字符，程序能够实现了。 树形结构的输出需要使用到遍历的思想，本次算法采用RDL的中序遍历思想，因为右子树总是位于根结点的上方，故先应该遍历右子树，然后显示结点的数据，再遍历左子树。 打印算法包含于遍历函数中，并采用格式化的方法，从结点本身存储的depth来控制横向输出的位置。（2） 算法的时空分析在二叉树的建立过程中，花费的时间集中于while（ch!=）的循环中，其时间复杂度为O（n），其中n为结点的个数。（3） 经验和体会通过此次试验，对于二叉树的建立以及遍历有了更深的理解，能够使用不同方法按照需求实现二叉树的遍历，同时对于队列的知识也是一次复习的机会，能够综合利用所学，解决实际问题，受益颇深。（4） 测试功能展示 二叉树的建立在主菜单下，用户输入1并回车，然后按照提示建立二叉树，运行结果如下所示： 打印树形结构在主菜单下，用户输入2并回车，可以以凹入表方式打印选项1中已经建立的二叉树，运行结果如下所示： 边界数据的测试如下：6、 源程序清单#include#include#define MAXSIZE 20typedef struct BiTNode/定义二叉树结点char data;struct BiTNode *lchild;/左孩子指针struct BiTNode *rchild;/有孩子指针int depth;/结点深度，用于打印控制横向的位置BiTNode,*BiTree;BiTree QMAXSIZE;BiTree CreatTree()/建立二叉树，并返回根指针int front,rear;front=1;rear=0;char ch;/由于接收输入的字符char c;BiTree T,s;T=NULL;/初始置空二叉树printf(创建二叉树，请输入结点信息:(空结点请输入:#，结束请输入:)n);c=getchar();/用于消除菜单键的回车ch=getchar();/接收第一个字符while(ch!=)s=NULL;/s为新结点if(ch!=#)/为非空结点s=(BiTree)malloc(sizeof(BiTree);s-data=ch;s-lchild=NULL;/左右孩子置空s-rchild=NULL;s-depth=0;/深度置为0rear+;Qrear=s;/新结点进入队列if(rear=1)/为第一个结点T=s;elseif(s!=NULL&Qfront!=NULL)/孩子和双亲结点均不为空结点if(rear%2=0)Qfront-lchild=s;/rear偶数时,为父结点的左孩子elseQfront-rchild=s;/rear奇数时,为父结点的右孩子s-depth=Qfront-depth+1;if(rear%2=1)front+;/结点的两个孩子均已处理ch=getchar();/继续下一个输入return T;void RDL(BiTree T)/使用RDL的中序遍历方式，便于打印结果if(T)RDL(T-rchild);/递归遍历右子树for(int i=0;idepth;i+)printf(t);/输出格式控制printf(%4cn,T-data);/输出结点信息RDL(T-lchild);/递归遍历左子树void main()int menu;int loop=1;BiTree T;printf(*欢迎使用打印树形结构操作程序:*n);printf(*1.二叉树的初始化*n);printf(*2.打印树形结构*n);printf(*3.退出操作*n);printf(*欢迎使用打印树形结构操作程序:*n);printf(n请选择需要使用的功能:);scanf(%d,&menu);while(loop)switch(menu)case 1:T=CreatTree();if(T)printf(初始化成功!n);break;case 2:if(T)printf(按凹入表形式打印结果如下:n);RDL(T);elseprintf(请先初始化!n);break;case 3:printf(谢谢使用，下次再见!n);exit(0);break;default:printf(输入错误!请重新输入!谢谢!n);break;print