大数据结构课程设计试验2打印树形结构

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

2、子指针域Ichild 、有孩子指针 域rchild 和结点深度标志域depth.3系统功能设计本程序设计了 3个功能子菜单,其描述如下： 二叉树的初始化.由函数 CreatTree 实现.该功能根据自上而下从左往 右的顺序输入二叉树结点,构造二叉树. 打印树形结构.由函数 RDL实现.该函数实现二叉树的中序遍历,并同 时格式化输出结点的数据信息. 退出操作.由exit 0函数实现.3、模块设计 模块设计本程序包含两个模块：主程序模块和二叉树操作模块.其调用关系如下列图所示:主程序模块二叉树操作模块 系统子程序及功能设计本系统共设置3个子程序,各程序的函数名及功能说明如下:a. BiTree C

3、reatTree()b. void RDL(BiTree T)打印结果/建立二叉树,并返回根指针/使用RDL的中序遍历方式遍历二叉树,并输出c. void main()/主函数.调用二叉树操作模块函数主要调用关系图本系统3个子程序之间的主要调用关系如下图4、详细设计(1) 数据类型定义typedef struct BiTNode 定义二叉树结点char data;struct BiTNode *lchild; 左孩子指针struct BiTNode *rchild; 有孩子指针int depth;/结点深度,用于打印限制横向的位置BiTNode,*BiTree;(2) 系统主要子程序详细设计

4、建立二叉树模块BiTree CreatTree()建立二叉树,并返回根指针int fron t,rear;fron t=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

5、->lchild=NULL;/ 左右孩子置空 s->rchild=NULL;s->depth=0;/ 深度置为 0 rear+;Qrear=s;/ 新结点进入队列 if(rear=1)/ 为第一个结点 T=s;else孩子和双亲结点均不为空结点偶数时, 为父结点的左孩子奇数时, 为父结点的右孩子if(s!=NULL&&Qfront!=NULL)/ if(rear%2=0) Qfront->lchild=s;/rear elseQfront->rchild=s;/rear s->depth=Qfront->depth+1; if(rear

6、%2=1)front+;/ 结点的两个孩子均已处理ch=getchar();/ 继续下一个输入 return T; 中序遍历并输出二叉树模块void RDL(BiTree T)使用RDL的中序遍历方式,便于打印结果if(T)RDL(T->rchild);/ 递归遍历右子树for(int i=0;i<T->depth;i+)printf("t");/ 输出格式限制printf("%4cn",T->data);/ 输出结点信息RDL(T->lchild);/ 递归遍历左子树5、测试分析(1) 实验中遇到的问题以及对设计与实现的回

7、忆讨论和分析 二叉树建立时,在输入格式中,以 Enter 键入作为结束标志,结果导致二叉树不能建立,原因是由于菜单键中的Enter存在于缓冲区并输入到二叉树中, 直接结束了.后经排查,发现了问题,将结束符用特定的作为结尾,成功实现建立功能 同样是在二叉树的建立过程中,原先在 CreatTree 函数中,并未使用一 个单独的字符接收菜单中的回车字符,导致二叉树根结点建立的时候其数据 为回车字符.经过参加字符c吸收回车字符,程序能够实现了. 树形结构的输出需要使用到遍历的思想,本次算法采用RDL的中序遍历思想, 由于右子树总是位于根结点的上方,故先应该遍历右子树,然后显示结点的 数据,再遍历左子树

8、. 打印算法包含于遍历函数中,并采用格式化的方法,从结点本身存储的depth 来限制横向输出的位置.2算法的时空分析在二叉树的建立过程中,花费的时间集中于 while ch!= ' 的循环中,其时 间复杂度为0n,其中n为结点的个数.3经验和体会通过此次试验,对于二叉树的建立以及遍历有了更深的理解, 能够使用不同方法 根据需求实现二叉树的遍历,同时对于队列的知识也是一次复习的时机,能够综 合利用所学,解决实际问题,受益颇深.4测试功能展示二叉树的建立在主菜单下,用户输入1并回车,然后根据提示建立二叉树,运行结果如下所示：打印树形结构在主菜单下,用户输入2并回车,可以以凹入表方式打印选项

9、1中已经建立的二 叉树,运行结果如下所示：下：计算机、在栓评程£庭结构谍程设tr'玄I印聘形结椅'DebuQ打印镐形结亏.耿汗回I 鼻羅耳- ALlLiI 欢送使用打印初 蔚：:羽巾诃殊TF衽叶 w 霍结构操作程序HMMBCMMM W H W M 酬涎 ME Jf KWiXXKXiK WEWEXXX KXSHK: 科光mrwi：iW占信息X空结点请输入沱,结束请输入®匸口翳豐IW盼C 边界数据的测试如下:,欢送使用tTE卩-MMMMMMWWMUM."WWMFW FS iHl IHJ H ' iiiMiM耳址光蕉懈 MEXJ<W 耳;M

10、XK豪 MEH 耳 X 疋 JOtJtK:捕厲耳耳WSKKiKlC:如下£性信息江空结点请输入叽 结束请输入®磁鱷使勰初丈MS成功,请选择需要使用的门能:下：计算机、在栓谍呈敎奈结构巒程设计打印树形结骨.Debu/打印閣形輕Lexh|回程番君形 dH "nvJ二 D.- - I r _r rut »« ixj u i»_f,6源程序清单#i nclude<stdio.h>#i nclude<stdlib.h>#defi ne MAXSIZE 20typedef struct BiTNode 定义二叉树结点 ch

11、ar 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"

12、;);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+;Qrear=s;/ 新结点进入队列 if(rear=1)/ 为第一个结点 T=s;else孩子和双亲结点均不为空结点偶数时, 为父结点

13、的左孩子奇数时, 为父结点的右孩子if(s!=NULL&&Qfront!=NULL)/if(rear%2=0)Qfront->lchild=s;/rear elseQfront->rchild=s;/rears->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;i<T-

14、>depth;i+)printf("t");/ 输出格式限制printf("%4cn",T->data);/ 输出结点信息 RDL(T->lchild);/ 递归遍历左子树void main()int menu; int loop=1;BiTree T;printf("* printf("* printf("* printf("* printf("*欢送使用打印树形结构操作程序 :*n");1. 二叉树的初始化 *n");2. 打印树形结构*n");3. 退

15、出操作 *n");欢送使用打印树形结构操作程序 :*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")