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

《大数据结构课程设计实验2打印树形结构.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实用文档数据结构课程设计实验报告实验二树和图部分选题为：6.4.6—打印树形结构1、需求分析（1）创建二叉树。按照用户需要的二叉树，构建二叉树（2）将创建的二叉树以凹入表形式打印出来。（3）对二叉树以中序遍历方式遍历（4）通过结点的深度标志位控制打印时结点的横向位置2、概要设计为了实现以上功能，可以从以下3个方面着手设计。（1）主界面设计为了实现二叉树相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本程序。本系统主控菜单运行界面如下所示。（2）存储结构设计本程序采用二叉链式存储类型（BITNode）存储二叉

2、树的节点信息。二叉树的链表中的结点包含四个域：数据域（data）、左孩子指针域（lchild）、有孩子指针域（rchild）和结点深度标志域（depth）。实用文档（1）系统功能设计本程序设计了3个功能子菜单，其描述如下：①二叉树的初始化。由函数CreatTree（）实现。该功能按照自上而下从左往右的顺序输入二叉树结点，构造二叉树。②打印树形结构。由函数RDL（）实现。该函数实现二叉树的中序遍历，并同时格式化输出结点的数据信息。③退出操作。由exit（0）函数实现。1、模块设计①模块设计本程序包含两个模块：主程序模块和二叉树操作模块。其调用关系如下图所

3、示：主程序模块二叉树操作模块②系统子程序及功能设计本系统共设置3个子程序，各程序的函数名及功能说明如下：a.BiTreeCreatTree()//建立二叉树，并返回根指针b.voidRDL(BiTreeT)//使用RDL的中序遍历方式遍历二叉树，并输出打印结果c.voidmain()//主函数。调用二叉树操作模块③函数主要调用关系图本系统3个子程序之间的主要调用关系如图所示。实用文档main（）RDL(BitreeT)CreatTree()1、详细设计（1）数据类型定义typedefstructBiTNode{//定义二叉树结点chardata;str

4、uctBiTNode*lchild;//左孩子指针structBiTNode*rchild;//有孩子指针intdepth;//结点深度，用于打印控制横向的位置}BiTNode,*BiTree;（2）系统主要子程序详细设计①建立二叉树模块BiTreeCreatTree(){//建立二叉树，并返回根指针intfront,rear;front=1;rear=0;charch;//由于接收输入的字符charc;BiTreeT,s;T=NULL;//初始置空二叉树实用文档printf("创建二叉树，请输入结点信息:(空结点请输入:#，结束请输入:@)");

5、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++;Q[rear]=s;//新结点进入队列if(rear==1)//为第一个结点{T=s;}else{实用文档if(s!=NULL&&Q[front]!=NU

6、LL)//孩子和双亲结点均不为空结点{if(rear%2==0)Q[front]->lchild=s;//rear偶数时,为父结点的左孩子elseQ[front]->rchild=s;//rear奇数时,为父结点的右孩子s->depth=Q[front]->depth+1;}if(rear%2==1)front++;//结点的两个孩子均已处理}ch=getchar();//继续下一个输入}returnT;}②中序遍历并输出二叉树模块voidRDL(BiTreeT){//使用RDL的中序遍历方式，便于打印结果if(T){RDL(T->rchild);//

7、递归遍历右子树for(inti=0;idepth;i++){实用文档printf("t");//输出格式控制}printf("%4c",T->data);//输出结点信息RDL(T->lchild);//递归遍历左子树}}1、测试分析（1）实验中遇到的问题以及对设计与实现的回顾讨论和分析①二叉树建立时，在输入格式中，以Enter键入作为结束标志，结果导致二叉树不能建立，原因是因为菜单键中的Enter存在于缓冲区并输入到二叉树中，直接结束了。后经排查，发现了问题，将结束符用特定的’@’作为结尾，成功实现建立功能②同样是在二叉树的建立过程中，

8、原先在CreatTree（）函数中，并未使用一个单独的字符接收菜单中的回车字符，导致二叉树根结