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

1课题名:建立二叉树,并对树进行操作系别:信息与计算科学系年级:2009级专业:数学与应用数学班级:一班学号:2009031116、2009031112、2009123123、2009031102、2009031110姓名:唐永桥、杨文升、李兵、陈丕权、范庆勇指导老师:李学勇2011-5-102目录摘要............................................................................................错误!未定义书签。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．...................2131、运行环境、开发工具运行环境：VC++6.0开发工具：电脑2、需求分析2.1设计目标二叉树是形象的说既树中每个节点最多只有两个分支，它是一个重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表。二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历。以及能够从输入的数据中得知二叉树的叶子节点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。2.2相关知识1、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;}TelemType的作用是输入n各任意的字符，而且在输入n个字符后，必须输入N=1个0，才能够得到本程序所有能够实现的功能。T=Null是将二叉树置为空。5if(!(*T=(BiTNode*)malloc(sizeof(BiTNode))))//采用动态申请结点的方式，不仅实现起来方便，而且还节省大量的存储空间。(*T)-data=ch;//生成根结点CreateBiTree(&((*T)-lchild));//左子树CreateBiTree(&((*T)-rchild));//右子树2、前序遍历：先访问根结点，再访问左子树，最后访问右子树。具体实现如下：statusPreOrderTraverse(BiTreeT){if(T){printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);}returnOK;}3、求叶子结点的个数：用m变量表示叶子结点的总个数。当树为空是此时讨论叶子结点个数无意义；当树非空时分为：一、左右子树都不存在时，m自加1，m的值就为1，即叶子结点的个数为1；二、左右子树存在，就用分别访问出左右子树中叶子结点的个数，两者相加就为二叉树叶子结点的个数。具体实现如下：//求二叉树的叶结点个数statusNumberLeaves(BiTreeT){//先序遍历得到叶结点的数目//m=0;if(T){if(T-lchild==NULL&&T-rchild==NULL)m++;NumberLeaves(T-lchild);NumberLeaves(T-rchild);}6returnOK;}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(mn)7returnm;elsereturnn;}//获取二叉树的高度statusHighBitree(BiTreet){if(t==NULL)return0;elsereturn1+Max(HighBitree(t-lchild),HighBitree(t-rchild));}5、主函数包括：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);8PostOrderTraverse(T);*/printf(\n层次遍历\n);ArrangementTraverse(T);printf(\n);}2程序设计92、概要设计2.1主要数据存储结构设计本设计中，对二叉树采用链式存储结构，其结构定义如下：typedefstructBiTNode{TelemTypedata;structBiTNode*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都是二叉树，分别称为根的左子树和右子树。103、详细设计3.1存储结构的建立由scanf（）函数实现一、首先输入的是根结点；二、然后输入的是根结点的左孩子；三、再者输入的是根结点的右孩子；四、接着输入的是根结点左孩子的左孩子；五、输入的是根结点的左孩子的；六、输入的是根结点的右孩子的左孩子；七、输入的是根结点的右