二叉树课程设计.doc

课程设计说明书设计名称：课程设计任务书题 目：基本操作二叉树 学生姓名： 专 业： 计算机应用技术 班 级：09计算机应用技术学 号：30910 指导教师： 周灵 日 期： 20111 年 1 月 9日 课程设计任务书专业09计算机应用技术 年级 09级 班 专科函授 一、 设计题目 1、基本操作二叉树二、 主要内容 建立二叉树，并对树进行操作。 基本功能要求： 1、利用完全二叉树的性质建立一棵二叉树。（层数不小于4层）。2、统计树叶子结点的个数。3、求二叉树的深度。4、能够输出用两种或两种以上的方法对二叉树进行遍历的遍历序列。三、 具体要求1、根据题目要求，那出总体设计方案，查找相关资料，解决设计中的难点，并画出程序的流程图。 2、针对题目的具体要求，根据前期的设计方案，实施编码，同时编写相应的文档。 3、完成编码后，根据题目要求测试程序是否及格，同时优化程序。四、 进度安排 12.26- 12.28 资料查找、系统分析，概要设计。 12.29- 1.6 系统详细设计、功能设计。 1.7- 1.9 算法实现、编程调试。 1.10- 1.11 归纳文档资料，按要求填写“课程设计说明书”；元月12日 上交课程设计材料。五、 完成后应上交的材料1、课程设计说明书（所使用的数据结构说明、程序流程图、功能模块图、核心算法等）。2、相关源程序文件。六、 总评成绩指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日 目 录一 绪论 - 5二 需求分析 - 5三 概要设计 -6四 详细设计 - 7五 源程序 - 7六 程序运行结果 - 12七 总结 - 13参考文献 - - 13一、绪论二叉树是树形结构的一个重要的类型，二叉树是n（n=0）个结点的有限集，它或者是空集（n=0），或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的存储结构和算法比较简单，特别适合计算机处理。即使一般形式的树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。二、需求分析 建立二叉树，并对树进行操作。 基本功能要求： 1、利用完全二叉树的性质建立一棵二叉树。（层数不小于4层）。2、统计树叶子结点的个数。3、求二叉树的深度。4、能够输出用两种或两种以上的方法对二叉树进行遍历的遍历序列。三、概要设计本程序采用了各种同的方法对同一个输入进行排序，且每一个元素其本身亦是一个结构体，又可以进行扩充，使其可以存储其他的相关的信息。通过二叉树的建立来实现二叉树各种遍历、叶子结点的个数、二叉树的深度。由题目要求，画出程序流程图如下：二叉树 A/ B C / D E F/ / K G H四、详细设计#include /定义数据元素类型 typedef int Element; /定义二叉树节点 typedef struct bitree Element data; struct bitree *left, *right; Bitree; /定义队列节点，层序遍历 typedef struct queueNode Bitree * data; struct queueNode *next; QueueNode; typedef struct queue QueueNode *front, *rear; Queue; /创建队列 void createQueue(Queue *Q) *Q = (Queue *) malloc(sizeof(Queue); if(!*Q) exit(Memory error.n); (*Q)-front = (*Q)-rear = NULL; /入队操作 void EnQueue(Queue *Q, Bitree *data) QueueNode * qn = (QueueNode*) malloc(sizeof(QueueNode); if(!qn) exit(Memory error.n); qn-data = data; qn-next = NULL; if(IsQueueEmpty(Q) Q-front = Q-rear = qn; else Q-rear-next = qn; Q-rear = qn; /出队操作 void DeQueue(Queue *Q, Bitree *T) if(!IsQueueEmpty(Q) QueueNode *qn = Q-front; (*T) = qn-data; Q-front = qn-next; free(qn); qn = NULL; /判断队列是否为空 int IsQueueEmpty(Queue *Q) if(!Q-front) return 1; return 0; /二叉树的创建 void createBitree(Bitree *T) Element data; scanf(%d, &data); if(data != 0) (*T) = (Bitree*)malloc(sizeof(Bitree); if(!*T) exit(Memory error.n); (*T)-data = data; (*T)-left = (*T)-right = NULL; createBitree(&(*T)-left); createBitree(&(*T)-right); /根据前序和中序遍历结果生成二叉树(总是假设给定的序列是有效的，这里不进行错误检测) /param p 递归前序子序列的起始位置 /param m 递归中序子序列的起始位置 /param length 递归子序列的长度 void creByPreMid(Bitree *T, int p, int m, int length, int *pre, int *mid) int i=0; for(;(idata = prep; (*T)-left = (*T)-right = NULL; /若有左子树则创建左子树 if(i0) creByPreMid(&(*T)-left, p+1, m, i, pre, mid); /若有右子树则创建右子树 if(iright, p+1+i, m+i+1, length-i-1, pre, mid); /删除树 void delBitree(Bitree *T) if(*T) delBitree(&(*T)-left); delBitree(&(*T)-right); free(*T); *T = NULL; /二叉树的前序遍历 void preOrder(Bitree *T) if(T) printf(%d , T-data); preOrder(T-left); preOrder(T-right); /二叉树的中序遍历 void midOrder(Bitree *T) if(T) midOrder(T-left); printf(%d , T-data); midOrder(T-right); /二叉树的后序遍历 void afterOrder(Bitree *T) if(T) afterOrder(T-left); afterOrder(T-right); printf(%d , T-data); /二叉树的层序遍历 /思路：利用队列，如果树不为空，将根节点入队 / 然后循环队头元素出队，并作一下处理：判断出队的节点是否有左孩子，有则将左孩子入队，判断出队的节点是否有右孩子，有则将又孩子入队。 / 重复以上过程直到队列为空 void layOrder(Bitree *T) Queue *Q = NULL; createQueue(&Q); if(!T) return; EnQueue(Q, T); while(!IsQueueEmpty(Q) DeQueue(Q, &T); if(T-left) EnQueue(Q, T-left); if(T-right) EnQueue(Q, T-right); printf(%d , T-data); /释放队列空间 if(IsQueueEmpty(Q) free(Q); Q = NULL; int main() Bitree *T = NULL; createBitree(&T); printf(The preOrder result is: ); preOrder(T); printf(nn); printf(The midOrder result is: ); midOrder(T); printf(nn); printf(The afterOrder result is: ); afterOrder(T); printf(nn); printf(The layOrder result is: ); layOrder(T); printf(nn); delBitree(&T); printf(After delete the tree, the preOrder result is: ); preOrder(T); printf(nn); /假定前序和中序序列如下 int pre6 = 5, 6, 7, 1, 2, 3; int mid6 = 7, 1, 6, 2, 5, 3; creByPreMid(&T, 0, 0, 6, pre, mid); printf(After creByPreMid, the preOrder result is: ); preOrder(T); printf(nn); return 0; 七、 总结通过这次做数据结构的课程设计，我发现真正掌握一个知识点并不只是要从书上看，还要查一些相关资料，并且理论与现实结合在一起。这次做的是关于二叉树基本操作课程设计，刚开始以为并不是很难，