北京联合大学信息学院课程设计报告书课程名称：数据结构实训题目：二叉家族树的建立与输出专业：计算机科学与技术实训题目二叉家族树的建立与输出王大爷的祖父王威育有两个儿子，大儿子叫王喜，是王大爷的父亲，二儿子叫王嘉，是王大爷的叔叔。王大爷有一个弟弟叫王石，还有两个堂弟妹，分别叫王磊、王燕。王大爷本人有两个儿子和一个孙女，分别叫王波、王涌和王晓蕊。王石有一个儿子叫王海。王磊有一个儿子和一个孙子，分别叫王涛和王晓帆。王大爷本人叫王硕。王大爷家的家谱按各成员的年龄顺序及父子关系构成的二叉家族树见右图。实训目的请设计算法，帮助王大爷建立他家的二叉家族族谱树，并将家族族谱树以层次遍历的方式输出。题目主要要求利用二叉树的创建和遍历算法来实现。设计思想采用二叉树的链式存储结构（二叉链表）及队列的顺序存储二叉链表主要是方便查找结点的左右子树，便于遍历二叉树队列的顺序存储主要是为了二叉树的层次遍历而设置的用队列解决把根节点存入队列尾部循环如果队列不空从队列头取出一个元素作为当前元素输出当前元素把当前元素的两个子节点存储入队列尾部继续循环如果队列空退出循环模块划分及主要算法或流程图软件分为10个函数，二叉树的遍历主要运用递归算法①voidInitQueue(Queue&q)//初始化队列q②intEmptyQueue(Queue&q)//判断队列q是否非空；③voidInsqQueue(Queue&q,QDataTypex)//依次进队元素，把根节点存入队列尾部④OutsqQueue(Queue&q,Tree&p)//出队一个元素，输出该元素；⑤voidDestroyList_SqQueue(Queue&q)//释放队列。⑥voidCreateTree(Tree&r)//创建二叉树⑦voidPreorder(Treer)//先序遍历二叉树⑧voidmidorder(Treer)//中序遍历二叉树⑨voidpostorder(Treer)//后序遍历二叉树⑩voidTravelTree(Treer)//层次遍历二叉树①②③④⑥⑩这几个函数总用重要，一旦出现一些错误，将影响整个程序的正常运行不足、改进和成功分析不足：队列的容量有限制，没有用循环队列；输入时按照先序遍历的方式输入，所以要求输入顺序必须正确，否则得到的其他遍历也不正确。改进：二叉树结点的数据的内容用字符数组来存储成功的地方：二叉树的层次遍历应用队列知识其他说明开发环境：MicrosoftVisualStudio6.0程序清单//Tree.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include"stdio.h"#include"malloc.h"#include"string.h"#defineMAX100//顺序队列的容量//typedefstringTDataType;typedefstructTreeNode{chardata[20];//用字符数组来记录结点的内容structTreeNode*lchild,*rchild;//左右孩子为指针类型}TreeNode,*Tree;typedefTreeQDataType;typedefstruct{QDataTypedata[MAX];intfront,rear;//队头指针，队尾指针}Queue;//（1）初始化队列qvoidInitQueue(Queue&q){q.front=0;q.rear=0;}//（2）判断队列q是否非空；intEmptyQueue(Queue&q){if(q.rear==q.front)return1;elsereturn0;}//（3）依次进队元素，把根节点存入队列尾部voidInsqQueue(Queue&q,QDataTypex){if(q.rear==MAX){printf("overflow");}q.rear++;q.data[q.rear]=x;}//(4)出队一个元素，输出该元素；OutsqQueue(Queue&q,Tree&p){if(EmptyQueue(q)){printf("underflow");return0;}else{p=q.data[q.front+1];//从队列头取出一个元素作为当前元素//printf("%c",x);q.front++;}if(EmptyQueue(q)){q.fro