打印树形结构

SLY数据结构课程设计报告1设计题目三：6.4.4打印树形结构P1361.设计要求1.1问题描述按凹入表形式打印树形结构，如图所示：图3.1凹入表形式打印树形结构1.2需求分析（1）创建二叉树。按照用户需要的二叉树，构建二叉树（2）对二叉树以先序遍历方式遍历（3）将创建的二叉树以凹入表形式打印出来。（4）通过结点的深度标志位控制打印时结点的横向位置2.概要设计2.1主界面设计打印树形结构的界面设计并不复杂，有提示功能选择的信息即可。运行界面如图所示。ABFEDCCFEADBSLY数据结构课程设计报告2图3.2打印树形结构主界面图2.2存储结构设计本程序采用二叉链式存储类型（Node）存储二叉树的节点信息。二叉树的链表中的结点包含四个域：数据域（data）、左孩子指针域（lchild）、有孩子指针域（rchild）和结点深度标志域（depth）。结点示意图如下：图3.3结点示意图2.3系统功能设计本程序设计了4个功能子菜单，其描述如下：①二叉树的初始化。由函数CreatTree（）实现。该功能按照自上而下从左往右的顺序输入二叉树结点，构造二叉树。②打印树形结构。由函数prev（）实现。该函数实现二叉树的先序遍历，并同时格式化输出结点的数据信息。③退出操作。由exit（0）函数实现。④主界面显示3模块设计3.1模块设计本程序包含2个模块，主程序模块和二叉树操作模块，调用关系如图所示。3.4模块调用示意图主程序模块二叉树操作模块程序退出模块主界面显示模块lchildrchilddepthdataSLY数据结构课程设计报告33.2系统子程序及功能设计本系统共设置5个函数，各函数及功能说明如下。a.BiTreeCreatTree()//建立二叉树，并返回根指针b.voidprev(BiTreeT)//使用prev的先序遍历方式遍历二叉树，并输出打印结果c.voidview()//界面显示d.voidexitApplication()//程序退出函数e.voidmain()//主函数。调用二叉树操作模块3.3函数主要调用关系图本系统函数之间的主要调用关系如图所示。3.5函数调用关系图4详细设计4.1数据类型定义typedefstructNode//定义二叉树结点{chardata;structNode*lchild;//左孩子指针structNode*rchild;//右孩子指针intdepth;//结点深度，用于打印控制横向的位置}Node,*BiTree;main()exitApplication()view()prev()CreateTree()SLY数据结构课程设计报告44.2系统主要子程序详细设计（1）主函数模块设计主函数。调用函数并逐步功能实现和打印。voidmain(){intn;intloop=1;BiTreeT;view();scanf(%d,&n);//接收一个数值，判断执行什么操作while(loop){switch(n){case1://初始化一个树T=CreatTree();if(T){printf(初始化成功！\n);}break;case2://打印树if(T){printf(按凹入表形式打印结果如下：\n);prev(T);}else{printf(请先初始化!\n);}SLY数据结构课程设计报告5break;case3://退出程序exitApplication();break;default://非法输入的处理printf(输入错误!请重新输入!谢谢!\n);break;}printf(\n请选择需要使用的功能：);scanf(%d,&n);}}（2）计算模块设计①建立二叉树模块BiTreeCreatTree()//建立二叉树，返回指针{intfront,rear;front=1;rear=0;charch;//用于接收输入的字符charc;BiTreeT,s;T=NULL;//初始置空二叉树printf(创建一个二叉树(!为结束符;^为空字符):\n);c=getchar();//用于消除菜单键的回车ch=getchar();while(ch!='!')//如果不是以!字符结尾的就可以继续循环{s=NULL;//s为新结点if(ch!='^')//如果是非空结点SLY数据结构课程设计报告6{s=(BiTree)malloc(sizeof(BiTree));s-data=ch;s-lchild=NULL;//左子树置空s-rchild=NULL;//右子树置空s-depth=0;//将根结点深度置为0}rear++;Q[rear]=s;//新结点进入队列if(rear==1)//为第一个结点{T=s;}else{if(s!=NULL&&Q[front]!=NULL)//孩子和双亲结点均不为空结点{if(rear%2==0){Q[front]-lchild=s;//rear偶数时，为父结点的左孩子}else{Q[front]-rchild=s;//rear奇数时，为父结点的右孩子}s-depth=Q[front]-depth+1;//存储各个结点度,记录各个结点的深度}if(rear%2==1){front++;//结点的两个孩子都已经处理了}}SLY数据结构课程设计报告7ch=getchar();//继续下一个输入}returnT;}②先序遍历并输出二叉树模块voidprev(BiTreeT)//使用prev的先根遍历方式，便于打印结果{if(T!=NULL){prev(T-rchild);//递归遍历右子树for(inti=0;i(T-depth);i++){printf(\t);//输出格式控制}printf(%4c\n,T-data);//打印根结点prev(T-lchild);//递归遍历左子树}}(3).界面模块voidview()//界面显示{printf(\n\t\t\t欢迎使用打印树形结构操作程序\n);printf(\t\t\t\t1.初始化二叉树\n);printf(\t\t\t\t2.打印树形结构\n);printf(\t\t\t\t3.退出程序\n);printf(请选择需要使用的功能:);}5测试分析系统运行主界面如图所示。按照提示输入功能编号，选择1:输入结点信息(即初始化一个二叉树)‘^’为空结点，‘!’为结束输入，选择2：按凹入表形式打印结果，选择3：退SLY数据结构课程设计报告8出操作，祝顺利毕业！！3.6欢迎界面3.7功能选择为1界面3.8二叉树初始化成功界面SLY数据结构课程设计报告93.9功能选择2打印界面SLY数据结构课程设计报告103.10功能选择3界面，退出程序6用户手册（1）本程序执行文件为“打印树形结构.exe”。（2）功能选择1可先选择建立二叉树功能后才能使用打印树形结构的功能，如二叉树未能正确建立，则打印树形结构的功能将无法使用。（3）二叉树的输入过程中，空结点使用“^”，结束输入“!”按回车即可。输入格式为，自上而下，从左往右输入二叉树的结点。（4）功能选择2即为打印刚刚初始化的二叉树，按凹入表形式打印。（5）功能选择3即为退出程序，完成本次打印操作。7调试报告（1）、理解了什么是先根遍历、中序遍历和后序遍历的含义：根据课本的题意：采用先序遍历方法，先序遍历二叉树的操作定义为：若二叉树唯恐则为空操作；否则①访问根节点；②先序遍历左子树；③先序遍历右子树；（2）、在树的建立过程中虽然用的是递归算法但还是出现了错误，就是没有正确的领悟到结束的条件，在一个节点的结束时没有把它的左右孩子都置为空，后来经过仔细的思考才明白，只有把结点的左右孩子都置空才算把这个结点结束。（3）、在遍历时因为用的是递归所以没有出现什么错误，一开始对遍历的递归不是很相信，不太相信那样就可以把一棵树遍历出来，经过这个实验以后就没有怀疑了。（4）、通过这个实验以后加深了对树这种新的结构的了解和理解。8程序清单#includestdio.h#includestdlib.h#defineMAXSIZE20typedefstructNode//定义二叉树结点{chardata;SLY数据结构课程设计报告11structNode*lchild;//左孩子指针structNode*rchild;//右孩子指针intdepth;//结点深度，用于打印控制横向的位置}Node,*BiTree;BiTreeQ[MAXSIZE];//队列Q为指针类型BiTreeCreatTree()//建立二叉树，返回指针{intfront,rear;front=1;rear=0;charch;//用于接收输入的字符charc;BiTreeT,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;//将根结点深度置为0}rear++;SLY数据结构课程设计报告12Q[rear]=s;//新结点进入队列if(rear==1)//为第一个结点{T=s;}else{if(s!=NULL&&Q[front]!=NULL)//孩子和双亲结点均不为空结点{if(rear%2==0){Q[front]-lchild=s;//rear偶数时，为父结点的左孩子}else{Q[front]-rchild=s;//rear奇数时，为父结点的右孩子}s-depth=Q[front]-depth+1;//存储各个结点度,记录各个结点的深度}if(rear%2==1){front++;//结点的两个孩子都已经处理了}}ch=getchar();//继续下一个输入}returnT;}voidprev(BiTreeT)//使用prev的先根遍历方式，便于打印结果{SLY数据结构课程设计报告13if(T!=NULL){prev(T-rchild);//递归遍历右子树for(inti=0;i(T-depth);i++){printf(\t);//输出格式控制}printf(%4c\n,T-data);//打印根结点prev(T-lchild);//递归遍历左子树}}voidview()//界面显示{printf(\n\t\t\t欢迎使用打印树形结构操作程序\n);printf(\t\t\t\t1.初始化二叉树\n);printf(\t\t\t\t2.打印树形结构\n);printf(\t\t\t\t3.退出程序\n);printf(请选择需要使用的功能:);}voidexitApplication(){printf(谢谢使用，欢迎下次再来！\n);exit(0);}voidmain(){intn;intloop=1;BiTreeT;view();SLY数据结构课程设计报告14scanf(%d,&n);//接收一个数值，判断执行什么操作while(loop){switch(n){case1://初始化一个树T=CreatTree();if(T){printf(初始化成功！\n);}break;case2://打印树if(T){printf(按凹入表形式打印结果如下：\n);prev(T);}else{printf(请先初始化!\n);}break;case3://退出程序exitApplication();break;default://非法输入的处理printf(输入错误!请重新输入!谢谢!\n);break;}printf(\n请选择需要使用的功能：);SLY数据结构课程设计报告15scanf(%d,&n);}}