二叉树和云计算.doc

北京联合大学 信息学院 课程设计报告书 课程名称：数据结构实训 题目：二叉家族树的建立与输出 专业：计算机科学与技术 实训题目 二叉家族树的建立与输出 王大爷的祖父王威育有两个儿子，大儿子叫王喜，是王大爷的父亲，二儿子叫王嘉，是王大爷的叔叔。王大爷有一个弟弟叫王石，还有两个堂弟妹，分别叫王磊、王燕。王大爷本人有两个儿子和一个孙女，分别叫王波、王涌和王晓蕊。王石有一个儿子叫王海。王磊有一个儿子和一个孙子，分别叫王涛和王晓帆。王大爷本人叫王硕。王大爷家的家谱按各成员的年龄顺序及父子关系构成的二叉家族树见右图。 实训目的 请设计算法，帮助王大爷建立他家的二叉家族族谱树，并将家族族谱树以层次遍历的方式输出。 题目主要要求 利用二叉树的创建和遍历算法来实现。 设计思想 采用二叉树的链式存储结构（二叉链表）及队列的顺序存储 二叉链表主要是方便查找结点的左右子树，便于遍历二叉树 队列的顺序存储主要是为了二叉树的层次遍历而设置的 用队列解决 ? ? ? 把根节点存入队列尾部 循环 ? ? ? ? 如果队列不空 ? ? ? ? ? ? 从队列头取出一个元素作为当前元素 ? ? ? ? ? ? 输出当前元素 ? ? ? ? ? ? 把当前元素的两个子节点存储入队列尾部 ? ? ? ? ? ? 继续循环 ? ? ? 如果队列空 ? ? ? ? ? ? 退出循环void InitQueue(Queue q) //初始化队列q ②int EmptyQueue(Queue q) //判断队列q是否非空； ③void InsqQueue(Queue q,QDataType x) //依次进队元素，把根节点存入队列尾部 ④OutsqQueue(Queue q,Tree p) //出队一个元素，输出该元素； ⑤void DestroyList_SqQueue(Queue q) //释放队列。 ⑥void CreateTree(Tree r)//创建二叉树 ⑦void Preorder(Tree r) //先序遍历二叉树 ⑧void midorder(Tree r) //中序遍历二叉树 ⑨void postorder(Tree r) //后序遍历二叉树 ⑩void TravelTree(Tree r) //层次遍历二叉树 ①②③④⑥⑩这几个函数总用重要，一旦出现一些错误，将影响整个程序的正常运行 不足、改进和成功分析 不足：队列的容量有限制，没有用循环队列；输入时按照先序遍历的方式输入，所以要求输入顺序必须正确，否则得到的其他遍历也不正确。 改进：二叉树结点的数据的内容用字符数组来存储 成功的地方：二叉树的层次遍历应用队列知识 其他说明 开发环境：Microsoft Visual Studio 6.0 程序清单 // Tree.cpp : Defines the entry point for the console application. // #include stdafx.h #includestdio.h #includemalloc.h #includestring.h #define MAX 100 //顺序队列的容量 //typedef string TDataType; typedef struct TreeNode { char data[20]; //用字符数组来记录结点的内容 struct TreeNode*lchild,*rchild; //左右孩子为指针类型 }TreeNode,*Tree; typedef Tree QDataType; typedef struct { QDataType data[MAX]; int front,rear; //队头指针，队尾指针 }Queue; //（1）初始化队列q void InitQueue(Queue q) { q.front=0; q.rear=0; } //（2）判断队列q是否非空； int EmptyQueue(Queue q) { if(q.rear==q.front) return 1; else return 0; } //（3）依次进队元素，把根节点存入队列尾部 void InsqQueue(Queue q,QDataType x) { if(q.rear==MAX){printf(overflow); } q.rear++; q.data[q.rear]=x; } //(4)出队一个元素，输出该元素； OutsqQueue(Queue q,Tree p) { if(EmptyQueue(q)) { printf(underflow); return 0; } else { p=q.data[q.