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

PAGEPAGE2课题名:建立二叉树,并对树进行操作系别:信息与计算科学系年级:2009级专业:数学与应用数学班级:一班学号:2009031116、2009031112、2009123123、2009031102、2009031110姓名:唐永桥、杨文升、李兵、陈丕权、范庆勇指导老师:李学勇2011-5-10目录摘要 错误!未定义书签。1、引言 错误!未定义书签。1.1设计目标 41.2相关知识 42、总体设计 92.1主要数据存储结构设计 92.2模块的划分及其功能 93、详细设计 103.1存储结构的建立由scanf（）函数实现 103.2重要函数 113.3程序相关分析 113.4结构体和全局变量定义 113.5程序清单 124、测试数据及结果分析 185、总结 错误!未定义书签。6、参考文献 21［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2003． 21returnOK;}4、中序遍历：先访问左子树，再访问根结点，最后访问右子树。具体实现如下：statusInOrderTraverse(BiTreeT){if(T){InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}returnOK;}5、后序遍历：先访问左子树，再访问右子树，最后访问根结点。具体实现如下：statusPostOrderTraverse(BiTreeT){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}returnOK;｝6、求二叉树的深度：先定义2个整形变量m，n，并将其初值设为0。如果树为空，则深度0；否则，先分别访问出左右子树的深度，再进行比较，将较大的+1的结果就是所求二叉树的深度。具体实现如下：statusMax(intm,intn)//一个比较函数{if(m>n)returnm;elsereturnn;}//获取二叉树的高度statusHighBitree(BiTreet){if(t==NULL)return0;elsereturn1+Max(HighBitree(t->lchild),HighBitree(t->rchild));}主函数包括：BiTreeT，reateBiTree(&T)，NumberLeaves(T)，printf("%d",HighBitree(T))，PreOrderTraverse(T)，InOrderTraverse(T)，PostOrderTraverse(T)，ArrangementTraverse(T)//主函数voidmain(){BiTreeT;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主要数据存储结构设计本设计中，对二叉树采用链式存储结构，其结构定义如下：typedefstructBiTNode{TelemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;每个结点中设置三个域，即值域data，左指针域*lchild和右指针域*child。2.2模块的划分及其功能本程序分为：6大模块。二叉树的建立链式存储结构，前序遍历，求叶子结点的个数计算，中序遍历，后序遍历，深度求解。1）二叉树的建立：定义二叉树的链式存储结构，输入数据生成二叉树。二叉树的前序遍历：利用二叉链表作为存储结构的前序遍历；先访问根结点，再依次访问左右子树。二叉树的求叶子结点的个数计算：先分别求的左右子树中各叶子结点的个数，再计算出两者之和即为二叉树的叶子结点数。二叉树的中序遍历：利用二叉链表作为存储结构的中序遍历；先访问左子树，再访问根结点，最后访问右子树。二叉树的后序遍历：利用二叉链表作为存储结构的前序遍历；先访问左右子树，再访问根结点求二叉树的深度：首先判断二叉树是否为空，若为空则此二叉树的深度为0.否则，就先求出左右子树的深度并进行比较，求较大的+1就为二叉树的深度。主函数。核心算法的设计：二叉树是n各结点的有穷个集合，它或者是空集（n=0）,或者同时满足以下两个条件：（1）：有且仅有一个称为根的节点：（2）：其余节点分为两个互为相交的集合T1,T2，并且T1，T2都是二叉树，分别称为根的左子树和右子树。3、详细设计开始开始建立二叉树建立二叉树中序遍历求叶子结点数先序遍历后序遍历求树的深度主函数3.1存储结构的建立由scanf（）函数实现一、首先输入的是根结点；二、然后输入的是根结点的左孩子；三、再者输入的是根结点的右孩子；四、接着输入的是根结点左孩子的左孩子；五、输入的是根结点的左孩子的；六、输入的是根结点的右孩子的左孩子；七、输入的是根结点的右孩子的左孩子；八、最后输入的是根结点的右孩子的右孩子。依次输入数据。3.2重要函数主函数voidmain()输入函数printf()输出函数scanf()二叉树的先序建立函数CreateBiTree（）二叉树的先序遍历函数PreOrderTraverse（）二叉树的中序遍历函数InOrderTraverse（）二叉树的后序遍历函数PostOrderTraverse（）二叉树的层序遍历函数ArrangementTraverse（）求叶子节点函数NumberLeaves（）求深度函数HighBitree（）比较函数Max（）3.3程序相关分析#include<stdio.h>/*标准输入输出函数定义*/#include<string.h>/*字符和字符串函数定义*/#include<conio.h>/*控制台进行数据输入和数据输出的函数*/#include<stdlib.h>/*常见数学函数定义*/（本程序中涉及很多关于字符串的函数，使用其函数，必须先定义）3.4结构体和全局变量定义#defineOK1#defineERROR-1#defineENDFLAG'#'/*表示节点没有左孩子或者没有右孩子用#代替*/typedefcharTelemType;/*宏定义char类型*/typedefintstatus;/*宏定义int类型*/typedefstructBiTNode{TelemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;/*二叉树的存储结构*/intm=0;/*全局变量，表示叶子个数*/3.5程序清单//头文件#include"stdio.h"#include"conio.h"#include"stdlib.h"//预定义宏常量#defineOK1#defineERROR-1#defineENDFLAG'#'typedefcharTelemType;typedefintstatus;//二叉树的存储结构typedefstructBiTNode{TelemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//全局变量，表示叶子个数intm=0;//二叉树的创建statusCreateBiTree(BiTree*T){ //先序创建 TelemTypech; scanf("%c",&ch);if(ch==ENDFLAG)*T=NULL;else{if(!(*T=(BiTNode*)malloc(sizeof(BiTNode)))){ printf("\nOutofspace.");getch();exit(0);}(*T)->data=ch;//生成根结点CreateBiTree(&((*T)->lchild));//左子树CreateBiTree(&((*T)->rchild));//右子树}returnOK;}//先序遍历statusPreOrderTraverse(BiTreeT){ if(T) { printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } returnOK; }/*//中序statusInOrderTraverse(BiTreeT){if(T){InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}returnOK;}//后序statusPostOrderTraverse(BiTreeT){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}returnOK;}*//*用队列层次遍历*///存储定义typedefcharQElemType;//typedefintstatus;typedefstructQueue{ QElemTypedata; structQueue*next;}Queue;//头指针和尾指针typedefstruct{ Queue*front;Queue*rear;}LinkQueue;//初始化队列statusInitQueue(LinkQueue*q){ q->front=q->rear=NULL;//无头结点 returnOK;}/*判断队列是否为空*/statusQueueEmpty(LinkQueue*Q){return(Q->front==NULL)&&(Q->rear==NULL);/*实际上只须判断队头指针是否为空即可*/}//入队voidEnQueue(LinkQueue*q,QElemTypee){ 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;/*队尾指针指向新的尾*/ }}//出队QElemTypeDeQueue(LinkQueue*q){ Queue*p; QElemTypee; if(QueueEmpty(q)) { printf("Queueunderflow\n");/*下溢*/ exit(1);} p=q->front;/*指向对头结点*/ e=p->data;/*保存对头结点的数据*/ q->front=p->next;/*将对头结点从链上摘下*/ if(q->rear==p)/*原队中只有一个结点，删去后队列变空，此时队头指针已为空*/ q->rear=NULL; free(p);/*释放被删队头结点*/ returne;/*返回原队头数据*/}/*层次遍历思想递归a.根结点入队列b.原队左子树的左右孩子（非空）入队列c.原队右子数的左右孩子（非空）入队列*///层次遍历入队列statusArrange(BiTreeT,LinkQueue*Q){ if(T) { EnQueue(Q,T->data); Arrange(T->lchild,Q); Arrange(T->rchild,Q);}returnOK;}//从队列中输出各元素statusArrangementTraverse(BiTreeT){chare;LinkQueueQ;InitQueue(&Q);if(T){Arrange(T,&Q);//递归调用while(!QueueEmpty(&Q)){e=DeQueue(&Q);printf("%c",e);}}returnOK;}//求二叉树的叶结点个数statusNumberLeaves(BiTreeT){//先序遍历得到叶结点的数目//m=0;if(T){ if(T->lchild==NULL&&T->rchild==NULL)m++; NumberLeaves(T->lchild); NumberLeaves(T->rchild);}returnOK;}//一个比较函数statusMax(intm,intn){if(m>n)returnm;elsereturnn;}//获取二叉树的高度statusHighBitree(BiTreet){if(t==NULL) return0;else return1+Max(HighBitree(t->lchild),HighBitree(t->rchild));}//主函数voidmain(){ BiTreeT; printf("请创建二叉树：\n"); CreateBiTree(&T);NumberLeaves(T); printf("叶节点个数为："); printf("%d",m);printf("\n二叉树的高度为:");printf("%d",HighBitree(T));printf("\n先序遍历:\n");PreOrderTraverse(T);/*printf("\n中序遍历:\n");InOrder