课程设计二叉树

1、安徽理工大学数据结构课程设计说明书 题目: 二叉树的遍历集成 院 系： 计算机科学与工程学院 专业班级： 学 号： 学生姓名： 指导教师： 2015年 01 月 9 日安徽理工大学课程设计（论文）任务书 计算机科学与工程 学院 信息安全教研室学 号学生姓名专业（班级）设计题目 二叉树遍历的集成设计技术参数系统平台：windows 7开发工具：VC6.0+设计要求（1） 实现二叉树的各种遍历。包括先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。（2） 要求能查找任一结点在某种遍历序列中的前驱和后继。（3） 界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。工作量课程设计报告

2、要求不少于3000字。源程序要求不少于300行工作计划2015年1月5日 分配程序任务，小组内每人做不同模块2015年1月6日 完成先序中序后序三个遍历递归算法2015年1月7日 完成先序中序后序三个遍历非递归算法2015年1月7日 完成线索化二叉树并查找节点的前驱后继2015年1月8日 完成主函数，采用友好的选择菜单页面2015年1月9日 完成设计报告，并打印参考资料1严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社,1997.4指导教师签字教研室主任签字 2014年 12 月 18 日 目录1.需求分析12、 总体设计12.1 程序目录12.2 算法流程33、 详细设计33.1

3、界面设计33.2 详细代码设计43.3 调试分析104、 总结14参考文献15代码详述15 II1.需求分析 “数据结构”是计算机程序设计的重要理论技术基础,它不仅是计算机学科的核心,而且也成为其他理工类学科必修课程,所谓”数据结构”是相互之间存在一种或多种特定关系的数据元素的集合.数据元素之间的相互关系成为结构,结构一般有线性结构,树形结构,图状结构,本程序所做的就是树形结构的二叉树的遍历算法和线索化查找. 本程序使用VC6.0+编写,具体实现功能有二叉树的遍历,包括先序遍历,中序遍历,后序遍历的递归算法以及非递归算法.另外本程序还有可线索化二叉树的功能,由此可以得到二叉树某个节点的前驱和后

4、继.题目要求为:1.实现二叉树的各种遍历。包括先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。 2.要求能查找任一结点在某种遍历序列中的前驱和后继。3.界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。 由小组一起制作,本人做小组汇总工作,并在基础上加了查找某个节点是否存在二叉树,以及求二叉树总节点数等一些简单功能2、 总体设计2.1 程序目录(1) typedef struct node 二叉树的定义,包含数据域data,左孩子lchild,右孩子rchild,若二叉树为空,则头结点指向空指针,并且data数据域为字符型数据.(2) BiTree CreatBiTree

5、1(BiTree &T) 创建一颗二叉树,需要按照先序遍历输入相应字符才能构造出二叉树,其中用星号”*”来代表空字符.(3) void Preorder1(BiTree T) 先序遍历递归算法,调用此函数可以获得输入二叉树的先序序列(4)void Preorder2(BiTree T) 先序遍历非递归算法,和上面一样,调用此函数可以获得二叉树先序序列(5) void Inorder1(BiTree T) 中序遍历递归算法,调用此函数可以获得输入二叉树的中序序列(6) void Inorder2(BiTree T) 中序遍历非递归算法,和上面一样,调用此函数可以获得二叉树中序序列(7)

6、void Postorder1(BiTree T) 后序遍历递归算法,调用此函数可以获得输入二叉树的后序序列(8) void Postorder2(BiTree &T)和typedef struct stacknode 后序遍历非递归算法,和其中用到的哨兵结构体.调用此函数可以获得二叉树后序序列(9) void Levelorder(BiTree T,int NodeNum) 层序遍历二叉树,需要手动输入节点数,然后即可进行二叉树的层序遍历,输出遍历结果(10) void InThreading(BiTree p) 线索化二叉树中需要用到的线索化前驱和后继(11) void InOrd

7、erThreading(BiTree &Thrt,BiTree T) 以中序遍历来线索化二叉树,让空节点分别指向当前节点的前驱后继(12) BiTree Inprenode(BiTree p)和BiTree Inpostnode(BiTree p) 线索化后用此函数查找二叉树的前驱和后继(13) BiTree search(BiTree BT,char x) 查找某个二叉树节点,其中x为要查找节点的data域的值(14) main( ) 主函数利用while()和switch()语句构造可视化友好界面2.2 算法流程 小组分工设计独立的函数,比如三种遍历,层序遍历,二叉树线索化等,然后

8、再综合起来,用主函数调用即可Postorder1Inorder2Preorder2Postorder2Inorder1Preorder1CreatBiTree1mainsearchInThreadingLevelorderInOrderThreadingInprenodeInpostnode3、 详细设计3.1 界面设计（1）打开程序后首先是按照先序序列输入二叉树，其中用“*”号表示空节点。图1 二叉树输入界面（2）输入完二叉树后进入功能选择页面，选择对应的编号，实行相应的操作图2 二叉树功能选择页面3.2 详细代码设计（1）创建一个二叉树，用户按照二叉树先序遍历顺序输入相应data域数据，使

9、用getchar（）读入并赋给c，利用T节点，以及左右递归，即可建立出一颗二叉树。BiTree CreatBiTree1(BiTree &T) char ch; if(ch=getchar()='*') T=NULL; /读入星号，返回空指针 else T=(BiTNode *)malloc(sizeof(BiTNode);/生成结点if(!T)return 0;T->data=ch;T->LTag=0;T->RTag=0; CreatBiTree1(T->lchild); /构造左子树 CreatBiTree1(T->rchild); /

10、构造右子树 return(T); （2）先序递归算法，读取头节点后，输出，接下来使用递归算法，不断地向下延伸读取，输出即可。void Preorder1(BiTree T) if(T) printf("%c",T->data); /访问结点 Preorder1(T->lchild); /先序遍历左子树 Preorder1(T->rchild); /先序遍历右子树 (3)先序遍历非递归算法，设置一个stack的栈用来存储读取的二叉树序列,利用栈先进后出的特性,输出栈即为先序遍历.void Preorder2(BiTree T)BiTree stackMax,

11、p;int top;if( T!=NULL)top=0;p=T;while(p!=NULL|top>0)while(p!=NULL)printf("%c",p->data);stacktop=p;top+;p=p->lchild;if(top>0)top-; p=stacktop;p=p->rchild;(4) 中序遍历递归算法和先序遍历思想差不多,只是在遍历完左边后再输出头节点.void Inorder1(BiTree T) if(T) Inorder1(T->lchild); /中序遍历左子树 printf("%c"

12、;,T->data); /访问结点 Inorder1(T->rchild); /中序遍历右子树(5) 中序遍历非递归算法,同理也是利用栈的特性来存储读取出来的data域的值,修改下出栈方式即可.void Inorder2(BiTree T) BiTree stackMax,p;int top;if( T!=NULL)top=0;p=T;while(p!=NULL|top>0)while(p!=NULL)stacktop=p;top+;p=p->lchild;if(top>0)top-; p=stacktop; printf("%c",p->

13、;data);p=p->rchild;(6) 后序遍历递归算法和先序遍历思想差不多,只是在遍历完最后后再输出头节点.void Postorder1(BiTree T) if(T) Postorder1(T->lchild); /后序遍历左子树 Postorder1(T->rchild); /后序遍历右子树 printf("%c",T->data); /访问结点(7) 后序遍历非递归算法,首先设置一个typedef struct stacknode的结构体为监查哨兵,输出过的节点都做上标记,防止二次输出.typedef structBiTree ptr

14、;int tag;stacknode; /设置哨兵void Postorder2(BiTree &T)stacknode sMax,x;BiTree p=T;int top;if(T!=NULL)top=0;p=T;dowhile(p!=NULL)stop.ptr=p;stop.tag=1;top+;p=p->lchild;while(top>0&&stop-1.tag=2)x=s-top;p=x.ptr;printf("%c",p->data);if(top>0)stop-1.tag=2;p=stop-1.ptr->r

15、child;while(top>0);(8) 层序遍历二叉树,利用指针数组*cqMax进行出队入队操作,再遍历左子树,最后再遍历右子树.void Levelorder(BiTree T,int NodeNum) int front=0,rear=1; BiTNode *cqMax,*p; /定义结点的指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%NodeNum; p=cqfront; /出队 printf("%c",p->data); /出队，输出结点的值 if(p->lchild!=NULL)

16、 rear=(rear+1)%NodeNum; cqrear=p->lchild; /左子树入队 if(p->rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p->rchild; /右子树入队 (9) 线索化二叉树,利用void InThreading(BiTree p)和void InOrderThreading(BiTree &Thrt,BiTree T)可完成二叉树中序线索化.主要思想是使二叉树中的空节点指向其前驱和后继.void InThreading(BiTree p)/线索化二叉树前驱后继if(p)InThreadi

17、ng(p->lchild);if(!p->lchild)p->LTag=1;p->lchild=pre;if(!pre->rchild)pre->RTag=1;pre->rchild=p;pre=p;InThreading(p->rchild);void InOrderThreading(BiTree &Thrt,BiTree T)Thrt=(BiTree)malloc(sizeof(BiTNode);Thrt->LTag=0;Thrt->RTag=1; Thrt->rchild=Thrt;if(!T)Thrt->

18、lchild=Thrt;else Thrt->lchild=T; pre=Thrt; InThreading(T); pre->rchild=Thrt; pre->RTag=1; Thrt->rchild=pre;(10) 查找二叉树的前驱和后继,基于中序线索化二叉树后,根据LTag和RTag的只能即可确定出节点的前驱和后继.BiTree Inprenode(BiTree p)/查找前驱BiTree pre;pre=p->lchild;if (p->LTag!=1)while(pre->RTag=0)pre=pre->rchild;return(

19、pre); BiTree Inpostnode(BiTree p)/查找后继BiTree post;post=p->rchild;if (p->RTag!=1)while(post->LTag=0)post=post->lchild;return(post);(11) 查找某个二叉树节点.根据data域的值,可以利用递归遍历查找出二叉树的对应节点的data域的值,从而确定所要查询的节点是否在二叉树中.BiTree search(BiTree BT,char x)/查找结点X，BiTree是二叉树结点类型的指针 if(BT->data=x) return BT; e

20、lse if(BT->lchild) return search(BT->lchild,x); else if(BT->rchild) return search(BT->rchild,x); else return NULL;3.3 调试分析(1)先序递归遍历图3 二叉树先序递归遍历(2)先序非递归遍历图4 二叉树先序非递归遍历(3)中序递归遍历图5 二叉树中序递归遍历(4)中序非递归遍历图6 二叉树中序非递归遍历(5)后序递归遍历图7 二叉树后序递归遍历(6)后序非递归遍历图8 二叉树后序非递归遍历(7)层序遍历图8 层序遍历二叉树(8)查找二叉树节点的前驱和后继图

21、9 查找前驱和后继(9)判断节点是否在二叉树内图10 判断节点是否在二叉树内4、 总结数据结构是一门博大精深的课程,尤其是通过这次课程设计,我深切是了解到算法为何是程序的灵魂了,算法决定一个程序的好与坏,效率高与效率低.在以前的c语言学习中,编写的程序大多数都是简短的实现单一功能的程序,没有了解到程序与程序之间的联系,和不同算法之间是如何相联系的.而这次试验却完全不一样.编写程序前需要自己做一个好的规划和设计,不断去了解所需要的编写的功能概念和算法,一开始总是很难,但随着不断地深入,我渐渐喜欢上了这种不断探索的过程,当然程序是不断出错的,而一次又一次的解决错误的过程,却使我体会到成功的喜悦.最

22、终在自己的努力下,程序可以运行起来,实现自己所需要的功能,这是一件自豪的事情.通过这次试验,我也体会到数据结构的重要性,只有真正理解数据类型的区别和数据类型之间的转换,才能更好地做出程序,比如查找前驱和后继的时候用户输入的是char型的数据,而查找函数需要的是BiTree的结构体数据,因为就需要search函数来转化,找到这个节点,从而查找出前驱和后继,这就是数据利用的一小点,而这一小点,让我在程序设计中避免了好多错误,巧妙地利用数据之间的关系,就可以灵活的调用函数,而避免出错.这次试验中我有一个疑惑的部分,我输入data数据,使用scanf(“%c”,ch),在运行过程中却没法输入,这个令我

23、很疑惑,我将程序改为cin>>ch;就可以了,我认为%c字符把enter当成字符了,而cin却不把enter当成字符,所以可以输入.像这样的小问题,我不断发现,不断解决,最终提高自己,感受到数据结构的魅力,参考文献1严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社,1997.4代码详述#include"stdio.h"#include"string.h"#include"malloc.h"#include <iostream>using namespace std;#define Max 20 /结点

24、的最大个数typedef struct node char data; struct node *lchild,*rchild;int LTag,RTag,flag;/用于线索化二叉树BiTNode,*BiTree; /自定义二叉树的结点类型BiTree pre;/用于线索化int NodeNum; /NodeNum为结点数/二叉树线索化之前先输入二叉树BiTree CreatBiTree1(BiTree &T) char ch; if(ch=getchar()='*') T=NULL; /读入星号，返回空指针 else T=(BiTNode *)malloc(size

25、of(BiTNode);/生成结点if(!T)return 0;T->data=ch;T->LTag=0;T->RTag=0; CreatBiTree1(T->lchild); /构造左子树 CreatBiTree1(T->rchild); /构造右子树 return(T); /DLR 先序遍历递归算法void Preorder1(BiTree T) if(T) printf("%c",T->data); /访问结点 Preorder1(T->lchild); /先序遍历左子树 Preorder1(T->rchild); /先

26、序遍历右子树 /DLR 先序遍历非递归算法void Preorder2(BiTree T)BiTree stackMax,p;int top;if( T!=NULL)top=0;p=T;while(p!=NULL|top>0)while(p!=NULL)printf("%c",p->data);stacktop=p;top+;p=p->lchild;if(top>0)top-; p=stacktop;p=p->rchild;/LDR 中序遍历递归算法 void Inorder1(BiTree T) if(T) Inorder1(T->lc

27、hild); /中序遍历左子树 printf("%c",T->data); /访问结点 Inorder1(T->rchild); /中序遍历右子树 /LDR 中序遍历非递归算法 void Inorder2(BiTree T) BiTree stackMax,p;int top;if( T!=NULL)top=0;p=T;while(p!=NULL|top>0)while(p!=NULL)stacktop=p;top+;p=p->lchild;if(top>0)top-; p=stacktop; printf("%c",p-&

28、gt;data);p=p->rchild; /LRD 后序遍历递归算法void Postorder1(BiTree T) if(T) Postorder1(T->lchild); /后序遍历左子树 Postorder1(T->rchild); /后序遍历右子树 printf("%c",T->data); /访问结点 /LRD 后序遍历非递归算法typedef structBiTree ptr;int tag;stacknode; /设置哨兵void Postorder2(BiTree &T)stacknode sMax,x;BiTree p=

29、T;int top;if(T!=NULL)top=0;p=T;dowhile(p!=NULL)stop.ptr=p;stop.tag=1;top+;p=p->lchild;while(top>0&&stop-1.tag=2)x=s-top;p=x.ptr;printf("%c",p->data);if(top>0)stop-1.tag=2;p=stop-1.ptr->rchild;while(top>0);/层次遍历二叉树void Levelorder(BiTree T,int NodeNum) int front=0,r

30、ear=1; BiTNode *cqMax,*p; /定义结点的指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%NodeNum; p=cqfront; /出队 printf("%c",p->data); /出队，输出结点的值 if(p->lchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p->lchild; /左子树入队 if(p->rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p->rchild; /右子

31、树入队 /中序遍历下节点的前驱后继void InThreading(BiTree p)/线索化二叉树前驱后继if(p)InThreading(p->lchild);if(!p->lchild)p->LTag=1;p->lchild=pre;if(!pre->rchild)pre->RTag=1;pre->rchild=p;pre=p;InThreading(p->rchild);void InOrderThreading(BiTree &Thrt,BiTree T)Thrt=(BiTree)malloc(sizeof(BiTNode);T

32、hrt->LTag=0;Thrt->RTag=1; Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;else Thrt->lchild=T; pre=Thrt; InThreading(T); pre->rchild=Thrt; pre->RTag=1; Thrt->rchild=pre;BiTree Inprenode(BiTree p)/查找前驱BiTree pre;pre=p->lchild;if (p->LTag!=1)while(pre->RTag=0)pre=pre->rch

33、ild;return(pre); BiTree Inpostnode(BiTree p)/查找后继BiTree post;post=p->rchild;if (p->RTag!=1)while(post->LTag=0)post=post->lchild;return(post); /查找某个节点BiTree search(BiTree BT,char x)/查找结点X，BiTree是二叉树结点类型的指针 if(BT->data=x) return BT; else if(BT->lchild) return search(BT->lchild,x);

34、 else if(BT->rchild) return search(BT->rchild,x); else return 0;/主函数int main() BiTree root,t,k1;char c; int i; printf("n");printf("创建二叉树; 输入完全二叉树的先序序列:"); /输入完全二叉树的先序序列， / 用*代表虚结点，如ABD#CE#F# CreatBiTree1(root); /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。 printf("t* select *n&quo

35、t;);printf("t1: 先序遍历递归算法n"); printf("t2: 先序遍历非递归算法n");printf("t3: 中序遍历递归算法n"); printf("t4: 中序遍历非递归算法n");printf("t5: 后序遍历递归算法n"); printf("t6: 后序遍历非递归算法n");printf("t7: 层次遍历二叉树n");/按层次遍历之前printf("t8: 求二叉树节点的前驱后继n");/中序遍历下,节点的前驱后继printf("t9: 判断节点是否在二叉树内n");printf("t0: Exitn"); printf("t*n");scanf("%d",&i); /输入菜单序