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

1、建立二叉树-并对树进行操作数 据结构课程设课题名：建立二叉树，并对树进行操作系别:信息与计算科学系年级:2009级专业：数学与应用数学班级：一班学号:2009031116、2009031112、2009123123 2009031102、2009031110姓名:唐永桥、杨文升、李兵、陈丕权、范庆勇指导老师:李学勇2011-5-10目录摘 要错误!未定义书签。1、 引言 错误!未定义书签。1.1设计目标5.1.2相关知识5.2、总体设计.102.1主要数据存储结构设计 102.2模块的划分及其功能103、详细设计.1.13.1存储结构的建立由scanf ()函数实现 1 13.2重要函数123

2、.3程序相关分析123.4结构体和全局变量定义123.5程序清单134、测试数据及结果分析1.95、总结 错误!未定义书签。6、参考文献22数据结构(C语言版)，严蔚敏，清华大学出版社，2003. 2231、运行环境、开发工具运行环境：VC+ 6.0开发工具：电脑2、需求分析2.1 设计目标二叉树是形象的说既树中每个节点最多只有两个分支，它是一个重要的数 据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分 类和各种机构的职位图表。二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历， 后序遍历。以及能够从输入的数据中得知二叉树的叶子节点的个数，二叉树的 深度。在此

3、，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。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

4、);/左子树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)-&g

5、t;rchild);右子树2、前序遍历：先访问根结点，再访问左子树，最后访问右子树。具体实现如下：status PreOrderTraverse(BiTree T)if(T)prin tf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);return OK;3、求叶子结点的个数：用 m变量表示叶子结点的总个数。当树为空是此时讨论叶子结点个数无意义；当树非空时分为：一、左右子树都不存在时，m自加1, m的值就为1,即叶子结点的个数为1；二、左右子树存在，就用分别访问出

6、左右子树中叶子结点的个数，两者相加就 为二叉树叶子结点的个数。具体实现如下：/求二叉树的叶结点个数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 InO rderTraverse(BiTree T)if(T)In OrderTr

7、averse(T->lchild);prin tf("%c",T->data);In OrderTraverse(T->rchild);return OK;5、后序遍历：先访问左子树，再访问右子树，最后访问根结点。具体实现如下：status PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);prin tf("%c",T->data);return OK;6求二叉树的深度：先定义2个整形变量m

8、 n,并将其初值设为0。如果树为空，则深度0; 否则，先分别访问出左右子树的深度，再进行比较，将较大的+1的结果就是所求二叉树的深度。具体实现如下：status Max(i nt m, i nt n) /一个比较函数if (m > n) return m;elsereturn n;/获取二叉树的高度 status HighBitree(BiTree t) if (t = NULL)return 0;elsereturnMax(HighBitree(t->lchild),HighBitree(t->rchild);5、主函数包括：BiTreeprin tf("%d&q

9、uot;,HighBitree(T) PostOrderTraverse(T),/主函数T ， reateBiTree(&T) ， NumberLeaves(T)， ，PreOrderTraverse(T) ， InOrderTraverse(T) ，Arra ngeme ntTraverse(T)void mai n()BiTree T;prin tf("请创建二叉树：CreateBiTree(&T);NumberLeaves(T);prin tf("叶节点个数为：prin tf("%d",m);printf("n二叉树的高度

10、为:");prin tf("%d",HighBitree(T);printf("n先序遍历:n");PreOrderTraverse(T);/* printf("n中序遍历:n");In OrderTraverse(T);n");");printf("n后序遍历:n");PostOrderTraverse(T);*/ prin tf("n层次遍历 n");Arran geme ntTraverse(T);prin tf("n");2程序设计112

11、、概要设计2.1主要数据存储结构设计本设计中，对二叉树采用链式存储结构，其结构定义如下：typedef struct BiTNodeTelemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;每个结点中设置三个域，即值域data，左指针域*lchild和右指针域*child。2.2模块的划分及其功能本程序分为：6大模块。二叉树的建立链式存储结构，前序遍历，求叶 子结点的个数计算，中序遍历，后序遍历，深度求解。1）二叉树的建立：定义二叉树的链式存储结构，输入数据生成二叉树。 二叉树的前序遍历：利用二叉链表作为存储结构的前序遍历；先访

12、问根结 点，再依次访问左右子树。2）二叉树的求叶子结点的个数计算：先分别求的左右子树中各叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。3）二叉树的中序遍历：利用二叉链表作为存储结构的中序遍历；先访 问左子树，再访问根结点，最后访问右子树。4）二叉树的后序遍历：利用二叉链表作为存储结构的前序遍历；先访 问左右子树，再访问根结点5）求二叉树的深度：首先判断二叉树是否为空，若为空则此二叉树的深度为0.否则，就先求出左右子树的深度并进行比较，求较大的+1就为二叉树的深度。6）主函数。核心算法的设计：二叉树是n各结点的有穷个集合，它或者是空集（n=0）, 或者同时满足以下两个条件：（1）：有且

13、仅有一个称为根的节点：（2）: 其余节点分为两个互为相交的集合T1,T2，并且T1, T2都是二叉树，分别称为根的左子树和右子树。3、详细设计3.1存储结构的建立由scanf ()函数实现一、首先输入的是根结点；二、然后输入的是根结点的左孩子；三、再者输入的是根结点的右孩子；四、接着输入的是根结点左孩子的左孩子;五、输入的是根结点的左孩子的；六、输入的是根结点的右孩子的左孩子；七、输入的是根结点的右孩子的左孩子；ii八、最后输入的是根结点的右孩子的右孩子。依次输入数据3.2重要函数主函数、void mai n()输入函数printf()输出函数sca nf()二叉树的先序建立函数CreateB

14、iTree()二叉树的先序遍历函数PreOrderTraverse（）二叉树的中序遍历函数InO rderTraverse（）二叉树的后序遍历函数PostOrderTraverse（）二叉树的层序遍历函数Arran geme ntTraverse（）求叶子节点函数NumberLeaves()求深度函数HighBitree()比较函数Max（）3.3程序相关分析#i nclude <stdio.h> /*标准输入输出函数定义*/#include <string.h> /*字符和字符串函数定义*/#in elude <con io.h> /*控制台进行数据输入和

15、数据输出的函数*/#include <stdlib.h> /*常见数学函数定义*/ （本程序中涉及很多关于字符串的函数，使用其函数，必须先定义）3.4结构体和全局变量定义#defi ne OK 1#defi ne ERROR -1#defi ne ENDFLAG '#'/* 表示节点没有左孩子或者没有右孩子用 #代替*/ typedef char TelemType;/* 宏定义 char 类型 */ typedef int status;/* 宏定义 int 类型 */typedef struct BiTNodeTelemType data;struct BiTN

16、ode *lchild,*rchild;BiTNode,*BiTree; /*二叉树的存储结构 */int m=0; /*全局变量，表示叶子个数*/3.5程序清单/头文件#include "stdio.h"#i nclude "coni o.h"#i nclude "stdlib.h"/预定义宏常量#defi ne OK 1#defi ne ERROR -1#defi ne ENDFLAG '#' typedef char TelemType; typedef int status;/二叉树的存储结构typedef s

17、truct BiTNodeTelemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/全局变量，表示叶子个数int m=0;/二叉树的创建status CreateBiTree(BiTree *T)/先序创建TelemType ch; sca nf("%c",&ch);if(ch=ENDFLAG) *T=NULL;elseif(!(*T=(BiTNode *)malloc(sizeof(BiTNode) prin tf("nOut of space.");getch();exit(

18、0);(*T)->data=ch; /生成根结点左子树CreateBiTree(&(*T)->lchild);右子树CreateBiTree(&(*T)->rchild); return OK;/先序遍历status PreOrderTraverse(BiTree T)if(T)prin tf("%c",T->data);PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild);return OK;/*/中序status InO rderTraverse(BiTree

19、 T)if(T)In OrderTraverse(T->lchild);prin tf("%c",T->data);In OrderTraverse(T->rchild);return OK;/后序status PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild); prin tf("%c",T->data);return OK;*/*用队列层次遍历*/存储定义typedef char QEle

20、mType;/typedef int status;typedef struct QueueQElemType data; struct Queue *n ext;Queue;/头指针和尾指针typedef structQueue *front;Queue *rear;Lin kQueue;/初始化队列status In itQueue(L in kQueue *q)q->fron t=q->rear =NULL; /-无头结点return OK;/*判断队列是否为空*/status QueueEmpty(L in kQueue *Q)return (Q->fro nt=NU

21、LL)&&(Q->rear=NULL);/*实际上只须判断队头指针是否为空即可*/入队void En Queue(L in kQueue *q,QEIemType e)Queue *p;p=(Queue *)malloc(sizeof(Queue);/*申请新结点 */p->data=e;p-> next=NULL;if(QueueEmpty(q)q->fron t=q->rear=p;else/*x插入非空队列的尾*/q->rear->next=p; /*p链到原队尾结点后*/q->rear=p;/* 队尾指针指向新的尾*/出队

22、QElemType DeQueue(L in kQueue *q)Queue *p;QEIemType e;if(QueueEmpty(q)prin tf("Queue un derflow'n");/*下溢 */exit(1);p=q->front;/*指向对头结点*/e=p->data;/*保存对头结点的数据*/q->front=p->next;/*将对头结点从链上摘下*/if(q->rear=p)/* 原队中只有一个结点，删去后队列变空，此时队头指针已 为空*/q->rear=NULL;free(p);/*释放被删队头结点*

23、/return e;/*返回原队头数据*/*层次遍历思想递归a. 根结点入队列b. 原队左子树的左右孩子(非空)入队列c. 原队右子数的左右孩子(非空)入队列*/层次遍历入队列status Arran ge(BiTree T,Lin kQueue *Q)if(T)En Queue(Q,T->data);Arran ge(T->lchild,Q);Arran ge(T->rchild,Q);return OK;/从队列中输出各元素status Arran geme ntTraverse(BiTree T)char e;Lin kQueue Q;In itQueue(&Q

24、);if(T)Arran ge(T,&Q);递归调用while(!QueueEmpty(&Q)e=DeQueue(&Q);prin tf("%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;/ 一个比较函数statu

25、s Max(i nt m, int n)if (m > n)return m;elsereturn n;/获取二叉树的高度status HighBitree(BiTree t)if (t = NULL)return 0;elsereturn 1 + Max(HighBitree(t->lchild), HighBitree(t->rchild);/主函数void mai n()BiTree T;prin tf("请创建二叉树：n");CreateBiTree(&T);NumberLeaves(T);printf("叶节点个数为：");prin tf("%d",m);printf("n二叉树的高度为:");prin tf("%d",HighB