二叉树的中序的递归、非递归遍历算法

1、信息工程学院数据结构课程设计报告设计题目二叉树的中序的递归、非递归遍历算法专业班级小组成员一.题目：二叉树的中序的递归、非递归遍历算法二.小组任务分工马凯：编写二叉树中序递归遍历、非递归遍历崔妍：编写二叉树层序遍历、打印二叉树三.设计目标帮助学生熟练掌握二叉树的遍历;应包含建树二叉树的中序的递归、非递归遍历算法，层次序的非递归遍历算法的实现,为了的实现。五.概要设计实现上述程序功能，需要定义一个结构体typedefstructtree/定义数据结构体(ElemTypedata;/数据信息structtree*lchild;/左孩子structtree*rchild;/右孩子TreeNode,*

2、Tree;typedefstruct/层序遍历的队列结构体定义QElemTypebaseMAXQSIZEZintfront;/定义队头intrear;/定义队尾Sqstack1;typedefstructstack/非递归遍历栈(Tree*base;/定义栈底Tree*top;/定义栈顶intstackszie;/指示栈内剩余空间Sqstack;六.详细设计（程序代码及核心代码流程图）总体操作步骤:(1)以前序遍历的方式输入二叉树；(2)打印出二叉树的中序递归、非递归遍历、层序遍历;(3)完成操作。#include<stdio.h>#include<stdlib.h>#

3、defineSTACKINITSIZE100#defineSTACKINCREASESIZE/层序遍历部分#defineTRUE1#defineFALSE0#defineOK1#defineERROR#defineOVERFLOWtypedefintStatus;/*8typedefcharElemTypetypedefstructtree/定义数据结构体ElemTypedata;/数据信息structtree*lchild;/左孩子structtree*rchild;/右孩子TreeNode,*Tree;/层序遍历#defineMAXQSIZEZ00/宏定义最大长度typedefTreeQE

4、lemTypetypedefstruct/层序遍历的队列结构体定义QElemTypebaseMAXQSIZEZintfront;/定义队头intrear;/定义队尾Sqstack1;typedefstructstack/利用结构体定义栈Tree*base;/定义栈底Tree*top;/定义栈顶intstackszie;/指示栈内剩余空间Sqstack;voidCreateTree(Tree*root)/创建一棵树(chars;/定义树的根节点s=getchar();/描述树中表示空树时的情况if(s='#')(*root=NULLelse(*root=(Tree)malloc(

5、sizeof(TreeNode);/申请空间，用malloc函数动态分配空间if(!root)/判断根节点是否为空，即，该树是否为空(printf("分配内存失败！")；(*root)->data=s;/将getcher得到的数据分配到树中CreateTree(&(*root)->lchild);CreateTree(&(*root)->rchild);/返回值/层序遍历队列定义voidInitQueue(Sqstack1*Q/初始化前尾指针(Q>front=Q>rear=0;/队头等于队尾StatusErQueue(Sqsta

6、ck1*QQElemTypee)/入队(if(Q>rear+1)%MAXQSIZEZ=Q->front)/判断对是否满returnERRQRQ>baseQ->rear=e;Q>rear=(Q>rear+1)%MAXQSIZEZreturnOK)StatusDeQueue(Sqstack1*QQElemType*e)/删除元素(if(Q->front=Q>rear)/队为空，不能删除returnERRQR*e=Q>baseQ>front;Q>front=(Q>front+1)%MAXQSIZEZreturnOK)Status

7、QueueEmpty(Sqstack1Q/判断队列是否为空(if(Qrear=Qfront)returnTRUEelsereturnFALSE)voidTraverse(TreeT)/层序遍历(Sqstack1Q;Treep;P=T;InitQueue(&Q);/初始化if(p)ErQueue(&Q,p);while(!QueueEmpty(Q)(DeQueue(&Q,&p);/出队printf("%c",p->data);if(p->lchild)ErQueue(&Q,p->lchild);if(p->rch

8、ild)ErQueue(&Q,p->rchild);)printf("n");*/使用递归完成中序遍历voidInOrder(Treeroot)(if(root)/如果根节点不为空，一句左根右的顺序遍历(InOrder(root->lchild);printf("%c",root->data);InOrder(root->rchild);/初始化栈voidInStack(Sqstack*s)(s->base=(Tree*)malloc(STACKINITSIZE?sizeof(TreeNode);/动态分配空间if(

9、!s->base)(printf("栈创建失败!");s->top=s->base;s->stackszie=STACKINITSIZE;/栈中的剩余内存/压栈voidPush(Sqstack*s,Treeroot)(if(*s).top-(*s).base)>=(*s).stackszie)/判断栈是否满？如果满(*s).base=(Tree*)realloc(*s).base,(*s).stackszie+STACKINCREASESI)ZEsizeof(Tree);/扩容if(!(*s).base)(printf("内存分配失败

10、！")；(*s).top=(*s).base+(*s).stackszie;(*s).stackszie+=STACKINCREASESIZE*(s->top)=root;s->top+;/进行依次入栈操作)/获得栈顶元素voidGetTop(Sqstack*s,Tree*root)(*root=*(*s).top-1);)/弹出栈顶元素voidPop(Sqstack*s,Tree*root)(if(*s).top=(*s).base)/=与=(printf("栈已经空了！")；)*root=*(-(*s).top);)/判断栈是否为空intStack

11、Empty(Sqstack*s)(if(s->top=s->base)return1;elsereturn0;)/非递归中序遍历voidInOrderS(Treeroot)(Treep=root;Sqstacks;InStack(&s);while(p|!StackEmpty(&s)(Pop(&s,&p);printf("%c",p->data);p=p->rchild;)voidPrintTree(Treeroot,intnLayer)/树状打印二叉树inti;if(root=NULL|return;PrintTre

12、e(root->rchild,nLayer+1);for(i=0;i<nLayer;i+)printf("");printf("%cn",root->data);PrintTree(root->lchild,nLayer+1);)voidmain()intlayer=0;Treeroot=NULLprintf("先序遍历输入二叉树，#代表空子树:n");CreateTree(&root);/参数不懂printf("递归中序遍历输出:n");InOrder(root);printf(&

13、quot;n");printf("非递归中序遍历输出:n");InOrderS(root);printf("n");printf("层序遍历二叉树：n");Traverse(root);printf("打印二叉树:n");PrintTree(root,layer);printf("n");七.测试分析测试内容测试结果输入二叉树正确递归中序遍历正确非递归中序遍历正确层序遍历正确打印二叉树正确新irs不-Mkroiohvrsudic*:*nWr不汹(2)<1值受:忤E!Mli'

14、;i*lrMI"W工困旧值阻mtn匚婚埠吐划悄*diol*，。”匕国看I/厂Fl%我由青1-f|WId-W卜Mqm<-ab6E-，1«nb；|FTitwE“mEJIErr«<fcis“w3：司.用小箕ET讦卜小口讣川却断电节岂是否为三，5瓜团里否FE时inrc分配内存失败！“门匚：版|公主giKgpMD图jg砌既交享文档.中图tfk-Mn"A£："幅护小到的做if分崎树中门干E.eM口日«.-rwcjfhhlii叫t/r(->Ehli叫m/f'f心卓肌值二工把Ln棒交神1ABeKtoDllElB再归

15、中序俎历瘠：也匚皿充理归中与遍历就出二CHME片序遍历二叉榭AAECDFT中二反商StatusEnWuf”qSnH1*Q,qElmTfe#>北人队ifCV*晔1，-河->”10”列曲对是否第Tr»tvirriERROR：U事3mFGq->r«r-(Q->rrjr*1WKQElZEZ?/*»rstun*VK;<£Qnctjrfa1b-nnnD»Tnn*jBHjfe7TIF匆-11Cn«ilingrB.音建文三文档也）用；新通交事品档，外SSMb叫Him拼音电人法至二LiNkinq.ub新建文/文档田第*-*

16、waifMm心hsi鹿上调在生月冲文甥，在文n冲查我%主祟x国匕叫询/111LJ行如,利11&.W'0E“力医不皿忖'C:User5)Km±DesktopDebug8f(2).exe"序遍历输入二叉树M代表空子树：BCttttDttttEtttt递归中序遍历输出：BDAEE递归巾序遍历输出二3BDAE县序遍历二叉树工ABECD打印二叉树：EAPressankeytocontinue搜狗拼音输入法全:八.课程设计总结此次课程设计中，题目为二叉树的中序遍历、层序遍历，在完成这次设计过程中，遇到了好多问题，例如：不知道如何循环完成二叉树的非递归遍历，如何利

17、用栈和队列的特性，怎么将它们合理的进栈和出栈。通过这次课程设计的设计，使我明白了自己在学习过程中的一些漏洞，比如，栈和队列中出入的一些细节的处理、结构体指针的应用、运行过程中内存的分配等。#include<stdio.h>#include<stdlib.h>#defineSTACKINITSIZE100# defineSTACKINCREASESIZE20/层序遍历部分# defineTRUE1# defineFALSE0# defineOK1# defineERROR0# defineOVERFLOW-2typedefintStatus;*typedefcharEle

18、mType;typedefstructtree定义数据结构体(ElemTypedata;/数据信息structtree*lchild;/左孩子structtree*rchild;/右孩子TreeNode,*Tree;/重命名/层序遍历#defineMAXQSIZEZ100/宏定义最大长度typedefTreeQElemType;typedefstruct/层序遍历的队列结构体定义(QElemTypebaseMAXQSIZEZ;intfront;/定义队头intrear;定义队尾Sqstack1;typedefstructstack/利用结构体定义栈(Tree*base;/定义栈底Tree*to

19、p;/定义栈顶intstackszie;/指示栈内剩余空间Sqstack;/借助结构体对栈进行重命名voidCreateTree(Tree*root)/创建一棵树(chars;/定义树的根节点s=getchar();/getchar和scanf的区别是什么手动从键盘输入字符描述树中表示空树时的情况if(s='#')(*root=NULL;else(*root=(Tree)malloc(sizeof(TreeNode);/申请空间，用malloc函数动态分配空间if(!root)判断根节点是否为空，即，该树是否为空(printf("分配内存失败！");)(*r

20、oot)->data=s;将getcher得到的数据分配到树中？CreateTree(&(*root)->lchild);/?CreateTree(&(*root)->rchild);/?)返回值)/层序遍历队列定义voidInitQueue(Sqstack1*Q)初始化前尾指针(Q->front=Q->rear=0;/队头等于队尾)StatusErQueue(Sqstack1*Q,QElemTypee)/入队(if(Q->rear+1)%MAXQSIZEZ=Q->front)/判断对是否满？returnERROR;Q->base

21、Q->rear=e;Q->rear=(Q->rear+1)%MAXQSIZEZ;/?returnOK;)StatusDeQueue(Sqstack1*Q,QElemType*e)删除元素(if(Q->front=Q->rear)/队为空，不能删除returnERROR;*e=Q->baseQ->front;Q->front=(Q->front+1)%MAXQSIZEZ;/?returnOK;)StatusQueueEmpty(Sqstack1Q)/判断队列是否为空(if(Q.rear=Q.front)returnTRUE;elseretur

22、nFALSE;)voidTraverse(TreeT)/层序遍历(Sqstack1Q;Treep;P=T;InitQueue(&Q);/初始化if(p)ErQueue(&Q,p);while(!QueueEmpty(Q)(DeQueue(&Q,&p);/出队printf("%c",p->data);if(p->lchild)ErQueue(&Q,p->lchild);if(p->rchild)ErQueue(&Q,p->rchild);)printf("n");)*使用递归完成

23、中序遍历voidInOrder(Treeroot)(if(root)/如果根节点不为空，一句左根右的顺序遍历(InOrder(root->lchild);printf("%c",root->data);InOrder(root->rchild);)初始化栈voidInStack(Sqstack*s)(s->base=(Tree*)malloc(STACKINITSIZE*sizeof(TreeNode);动态分配空间if(!s->base)printf("栈创建失败！");s->top=s->base;s->

24、;stackszie=STACKINITSIZE;/栈中的剩余内存/压栈voidPush(Sqstack*s,Treeroot)if(*s).top-(*s).base)>=(*s).stackszie)/判断栈是否满？如果满(*s).base=(Tree*)realloc(*s).base,(*s).stackszie+STACKINCREASESIZE)*sizeof(Tree);扩容if(!(*s).base)printf("内存分配失败！");(*s).top=(*s).base+(*s).stackszie;(*s).stackszie+=STACKINCREASESIZE;*(s->top)=root;s->top+;/进行依次入栈操作/获得栈顶元素voidGetTop(Sqstack*s,Tree*root)/?*root=*(*s).top-1);弹出栈顶元素voidPop(Sqstack*s,Tree*root)if(*s).top=(*s).base)/=与=printf("栈已经空了！");*root=*(-(*s).top);)判断栈是否为空intStackEmpty(Sqstack*s)(if(s-&