建立二叉树并对树进行操作数据结构课程设.doc

课题名:建立二叉树,并对树进行操作系别:信息与计算科学系年级:2009级专业:数学与应用数学班级:一班学号:2009031116、2009031112、2009123123、2009031102、2009031110姓名:唐永桥、杨文升、李兵、陈丕权、范庆勇指导老师:李学勇 2011-5-10 目录摘 要31、引言51.1设计目标51.2 相关知识52、总体设计102.1主要数据存储结构设计102.2模块的划分及其功能103、详细设计113.1存储结构的建立由scanf（）函数实现113.2重要函数123.3程序相关分析123.4结构体和全局变量定义123.5程序清单134、测试数据及结果分析195、总结216、参考文献221数据结构（C语言版），严蔚敏，清华大学出版社，2003221、 运行环境、开发工具运行环境：VC+ 6.0开发工具：电脑32、需求分析2.1设计目标二叉树是形象的说既树中每个节点最多只有两个分支，它是一个重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表。二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历。以及能够从输入的数据中得知二叉树的叶子节点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。2.2 相关知识1、 status CreateBiTree(BiTree *T)/ 先序创建二叉树 TelemType ch; scanf(%c,&ch); if(ch=ENDFLAG) *T=NULL; else if(!(*T=(BiTNode *)malloc(sizeof(BiTNode) printf(nOut of space.); getch(); exit(0); (*T)-data=ch; /生成根结点 CreateBiTree(&(*T)-lchild);/左子树 CreateBiTree(&(*T)-rchild);/右子树 return OK;TelemType的作用是输入n各任意的字符，而且在输入n个字符后，必须输入N=1个0，才能够得到本程序所有能够实现的功能。T=Null是将二叉树置为空。if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)/采用动态申请结点的方式，不仅实现起来方便，而且还节省大量的存储空间。(*T)-data=ch; /生成根结点 CreateBiTree(&(*T)-lchild);/左子树 CreateBiTree(&(*T)-rchild);/右子树2、前序遍历：先访问根结点，再访问左子树，最后访问右子树。具体实现如下：status PreOrderTraverse(BiTree T) if(T) printf(%c,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); return OK; 3、求叶子结点的个数：用m变量表示叶子结点的总个数。当树为空是此时讨论叶子结点个数无意义；当树非空时分为：一、左右子树都不存在时，m自加1，m的值就为1，即叶子结点的个数为1；二、左右子树存在，就用分别访问出左右子树中叶子结点的个数，两者相加就为二叉树叶子结点的个数。具体实现如下：/求二叉树的叶结点个数status NumberLeaves(BiTree T)/先序遍历得到叶结点的数目 /m=0; if(T) if(T-lchild=NULL&T-rchild=NULL) m+; NumberLeaves(T-lchild); NumberLeaves(T-rchild); return OK;4、中序遍历：先访问左子树，再访问根结点，最后访问右子树。具体实现如下：status InOrderTraverse(BiTree T) if(T) InOrderTraverse(T-lchild); printf(%c,T-data); InOrderTraverse(T-rchild); return OK; 5、后序遍历：先访问左子树，再访问右子树，最后访问根结点。具体实现如下：status PostOrderTraverse(BiTree T) if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c,T-data); return OK; 6、求二叉树的深度： 先定义2个整形变量m，n，并将其初值设为0。如果树为空，则深度0； 否则，先分别访问出左右子树的深度，再进行比较，将较大的+1的结果就是所求二叉树的深度。具体实现如下：status Max(int m, int n) /一个比较函数 if (m n) return m; else return n; /获取二叉树的高度status HighBitree(BiTree t) if (t = NULL) return 0; else return 1 + Max(HighBitree(t-lchild), HighBitree(t-rchild); 5、 主函数 包括：BiTree T，reateBiTree(&T)，NumberLeaves(T)，printf(%d,HighBitree(T)，PreOrderTraverse(T)，InOrderTraverse(T)，PostOrderTraverse(T)，ArrangementTraverse(T)/主函数void main() BiTree T; printf(请创建二叉树：n); CreateBiTree(&T); NumberLeaves(T); printf(叶节点个数为：); printf(%d,m); printf(n二叉树的高度为:); printf(%d,HighBitree(T); printf(n先序遍历:n); PreOrderTraverse(T); /* printf(n中序遍历:n); InOrderTraverse(T); printf(n后序遍历:n); PostOrderTraverse(T);*/ printf(n层次遍历n); ArrangementTraverse(T); printf(n);2程序设计2、概要设计2.1主要数据存储结构设计 本设计中，对二叉树采用链式存储结构，其结构定义如下：typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;每个结点中设置三个域，即值域data，左指针域*lchild和右指针域*child。 2.2模块的划分及其功能 本程序分为：6大模块。二叉树的建立链式存储结构，前序遍历，求叶子结点的个数计算，中序遍历，后序遍历，深度求解。1）二叉树的建立：定义二叉树的链式存储结构，输入数据生成二叉树。二叉树的前序遍历：利用二叉链表作为存储结构的前序遍历；先访问根结点，再依次访问左右子树。2） 二叉树的求叶子结点的个数计算：先分别求的左右子树中各叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。3） 二叉树的中序遍历：利用二叉链表作为存储结构的中序遍历；先访问左子树，再访问根结点，最后访问右子树。4） 二叉树的后序遍历：利用二叉链表作为存储结构的前序遍历；先访问左右子树，再访问根结点5） 求二叉树的深度：首先判断二叉树是否为空，若为空则此二叉树的深度为0.否则，就先求出左右子树的深度并进行比较，求较大的+1就为二叉树的深度。6） 主函数。核心算法的设计：二叉树是n各结点的有穷个集合，它或者是空集（n=0）,或者同时满足以下两个条件：（1）：有且仅有一个称为根的节点：（2）：其余节点分为两个互为相交的集合T1,T2，并且T1，T2都是二叉树，分别称为根的左子树和右子树。3、详细设计开 始 建立二叉树中序遍历求叶子结点数先序遍历后序遍历求树的深度 主函数3.1存储结构的建立由scanf（）函数实现 一、首先输入的是根结点； 二、然后输入的是根结点的左孩子； 三、再者输入的是根结点的右孩子； 四、接着输入的是根结点左孩子的左孩子； 五、输入的是根结点的左孩子的； 六、输入的是根结点的右孩子的左孩子； 七、输入的是根结点的右孩子的左孩子； 八、最后输入的是根结点的右孩子的右孩子。依次输入数据。 3.2重要函数主函数 void main()输入函数 printf()输出函数 scanf() 二叉树的先序建立函数 CreateBiTree（） 二叉树的先序遍历函数 PreOrderTraverse（） 二叉树的中序遍历函数 InOrderTraverse（） 二叉树的后序遍历函数 PostOrderTraverse（） 二叉树的层序遍历函数 ArrangementTraverse（） 求叶子节点函数 NumberLeaves（） 求深度函数 HighBitree（） 比较函数 Max（）3.3程序相关分析#include /*标准输入输出函数定义*/#include /*字符和字符串函数定义*/#include /*控制台进行数据输入和数据输出的函数*/#include /*常见数学函数定义*/（本程序中涉及很多关于字符串的函数，使用其函数，必须先定义）3.4结构体和全局变量定义#define OK 1#define ERROR -1#define ENDFLAG #/*表示节点没有左孩子或者没有右孩子用#代替*/typedef char TelemType;/*宏定义char类型*/typedef int status;/*宏定义int类型*/typedef struct BiTNodeTelemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree; /*二叉树的存储结构*/ int m=0; /*全局变量，表示叶子个数*/3.5程序清单/头文件#include stdio.h#include conio.h#include stdlib.h/预定义宏常量#define OK 1#define ERROR -1#define ENDFLAG #typedef char TelemType;typedef int status;/二叉树的存储结构typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/全局变量，表示叶子个数int m=0;/二叉树的创建status CreateBiTree(BiTree *T)/ 先序创建TelemType ch;scanf(%c,&ch); if(ch=ENDFLAG) *T=NULL; else if(!(*T=(BiTNode *)malloc(sizeof(BiTNode) printf(nOut of space.); getch(); exit(0); (*T)-data=ch; /生成根结点 CreateBiTree(&(*T)-lchild);/左子树 CreateBiTree(&(*T)-rchild);/右子树 return OK;/先序遍历status PreOrderTraverse(BiTree T)if(T)printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); return OK; /*/中序status InOrderTraverse(BiTree T) if(T) InOrderTraverse(T-lchild); printf(%c,T-data); InOrderTraverse(T-rchild); return OK; /后序status PostOrderTraverse(BiTree T) if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c,T-data); return OK; */* 用队列 层次遍历*/存储定义typedef char QElemType;/typedef int status;typedef struct Queue QElemType data;struct Queue *next; Queue;/头指针和尾指针typedef structQueue *front; Queue *rear; LinkQueue; /初始化队列status InitQueue(LinkQueue *q)q-front=q-rear =NULL; /-无头结点 return OK;/*判断队列是否为空*/ status QueueEmpty(LinkQueue *Q) return (Q-front=NULL)&(Q-rear=NULL); /*实际上只须判断队头指针是否为空即可*/ /入队void EnQueue(LinkQueue *q,QElemType e)Queue *p; p=(Queue *)malloc(sizeof(Queue);/*申请新结点*/ p-data=e; p-next=NULL;if(QueueEmpty(q)q-front=q-rear=p;else/*x插入非空队列的尾*/ q-rear-next=p; /*p链到原队尾结点后*/ q-rear=p;/*队尾指针指向新的尾*/ /出队QElemType DeQueue(LinkQueue *q)Queue *p;QElemType e;if(QueueEmpty(q) printf(Queue underflown);/*下溢*/ exit(1) ; p=q-front;/*指向对头结点*/ e=p-data;/*保存对头结点的数据*/ q-front=p-next;/*将对头结点从链上摘下*/if(q-rear=p)/*原队中只有一个结点，删去后队列变空，此时队头指针已为空*/ q-rear=NULL;free(p);/*释放被删队头结点*/ return e;/*返回原队头数据*/*层次遍历思想 递归a.根结点入队列b.原队左子树的左右孩子（非空）入队列c.原队右子数的左右孩子（非空）入队列*/层次遍历入队列status Arrange(BiTree T,LinkQueue *Q)if(T)EnQueue(Q,T-data);Arrange(T-lchild,Q);Arrange(T-rchild,Q); return OK;/从队列中输出各元素status ArrangementTraverse(BiTree T) char e; LinkQueue Q; InitQueue(&Q); if(T) Arrange(T,&Q);/递归调用 while(!QueueEmpty(&Q) e=DeQueue(&Q); printf(%c,e); return OK;/求二叉树的叶结点个数status NumberLeaves(BiTree T)/先序遍历得到叶结点的数目 /m=0; if(T) if(T-lchild=NULL&T-rchild=NULL) m+; NumberLeaves(T-lchild); NumberLeaves(T-rchild); return OK;/一个比较函数status Max(int m, int n) if (m n) return m; else return n; /获取二叉树的高度status HighBitree(BiTree t) if (t = NULL) return 0; else return 1 + Max(HighBitree(t-lchild), HighBitree(t-rchild); /主函数void main()BiTree T;printf(请创建二叉树：n);CreateBiTree(&T); NumberLeaves(T);printf(叶节点个数为：);printf(%d,m); printf(n二叉树的高度为:); printf(%d,HighBitree(T); printf(n先序