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

信息工程学院《数据结构》课程设计报告设计题目二叉树的中序的递归、非递归遍历算法专业班级小组成员一．题目：二叉树的中序的递归、非递归遍历算法二．小组任务分工马凯：编写二叉树中序递归遍历、非递归遍历崔妍：编写二叉树层序遍历、打印二叉树三．设计目标帮助学生熟练掌握二叉树的遍历；四．问题描述二叉树的中序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树为了的实现。五．概要设计实现上述程序功能，需要定义一个结构体typedefstructtree//定义数据结构体{ElemTypedata;//数据信息structtree*lchild;//左孩子structtree*rchild;//右孩子}TreeNode,*Tree;typedefstruct//层序遍历的队列结构体定义{QElemTypebase[MAXQSIZEZ];intfront;//定义队头intrear;//定义队尾}Sqstack1;typedefstructstack//非递归遍历栈{Tree*base;//定义栈底Tree*top;//定义栈顶intstackszie;//指示栈内剩余空间}Sqstack;六．详细设计（程序代码及核心代码流程图）总体操作步骤：(1)以前序遍历的方式输入二叉树；(2)打印出二叉树的中序递归、非递归遍历、层序遍历；(3)完成操作。#includestdio.h#includestdlib.h#defineSTACKINITSIZE100#defineSTACKINCREASESIZE20//层序遍历部分#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;//******************************8typedefcharElemType;typedefstructtree//定义数据结构体{ElemTypedata;//数据信息structtree*lchild;//左孩子structtree*rchild;//右孩子}TreeNode,*Tree;//层序遍历#defineMAXQSIZEZ100//宏定义最大长度typedefTreeQElemType;typedefstruct//层序遍历的队列结构体定义{QElemTypebase[MAXQSIZEZ];intfront;//定义队头intrear;//定义队尾}Sqstack1;typedefstructstack//利用结构体定义栈{Tree*base;//定义栈底Tree*top;//定义栈顶intstackszie;//指示栈内剩余空间}Sqstack;voidCreateTree(Tree*root)//创建一棵树{chars;//定义树的根节点s=getchar();//描述树中表示空树时的情况if(s=='#'){*root=NULL;}else{*root=(Tree)malloc(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(Sqstack1*Q,QElemTypee)//入队{if((Q-rear+1)%MAXQSIZEZ==Q-front)//判断对是否满returnERROR;Q-base[Q-rear]=e;Q-rear=(Q-rear+1)%MAXQSIZEZ;returnOK;}StatusDeQueue(Sqstack1*Q,QElemType*e)//删除元素{if(Q-front==Q-rear)//队为空，不能删除returnERROR;*e=Q-base[Q-front];Q-front=(Q-front+1)%MAXQSIZEZ;returnOK;}StatusQueueEmpty(Sqstack1Q)//判断队列是否为空{if(Q.rear==Q.front)returnTRUE;elsereturnFALSE;}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);}//**********************************//使用递归完成中序遍历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-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-top==s-base)return1;elsereturn0;}//非递归中序遍历voidInOrderS(Treeroot){Treep=root;Sqstacks;InStack(&s);while(p||!StackEmpty(&s)){if(p){Push(&s,p);p=p-lchild;}else{Pop(&s,&p);printf(%c,p-data);p=p-rchild;}}}voidPrintTree(Treeroot,intnLayer)//树状打印二叉树{inti;if(root==NULL)return;PrintTree(root-rchild,nLayer+1);for(i=0;inLayer;i++)printf();printf(%c\n,root-data);PrintTree(root-lchild,nLayer+1);}voidmain(){intlayer=0;Treeroot=NULL;printf(先序遍历输入二叉树,#代表空子树:\n);CreateTree(&root);//参数不懂printf(递归中序遍历输出:\n);InOrder(root);printf(\n);printf(非递归中序遍历输出:\n);InOrderS(root);printf(\n);printf(层序遍历二叉树：\n);Traverse(root);printf(打印二叉树：\n);PrintTree(root,layer);printf(\n);}七．测试分析测试内容测试结果输入二叉树正确递归中序遍历正确非递归中序遍历正确层序遍历正确打印二叉树正确八．课程设计总结此次课程设计中，题目为二叉树的中序遍历、层序遍历，在完成这次设计过程中，遇到了好多问题，例如：不知道如何循环完成二叉树的非递归遍历，如何利用栈和队列的特性，怎么将它们合理的进栈和出栈。通过这次课程设计的设计，使我明白了自己在学习过程中的一些漏洞，比如，栈和队列中出入的一些细节的处理、结构体指针的应用、运行过程中内存的分配等。#includestdio.h#includestdlib.h#defineSTACKINITSIZE100#defineSTACKINCREASESIZE20//层序遍历部分#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;//******************************8typedefcharElemType;typedefstructtree//定义数据结构体{ElemTypedata;//数据信息structtree*lchild;//左孩子structtree*rchild;//右孩子}TreeNode,*Tree;//重命名//层序遍历#defineMAXQSIZEZ100//宏定义最大长度typedefTreeQElemType;typedefstruct//层序遍历的队列结构体定义{QElemTypebase[MAXQSIZEZ];intfront;//定义队头intrear;//定义队尾}Sqstack1;typedefstructstack//利用结构体定义栈{Tree*base;//定义栈底Tree*top;//定义栈顶intstackszie;//指示栈内剩余空间}Sqstack;//借助结构体对栈进行重命名voidCreateTree(Tree*root)//创建一棵树{chars;//定义树的根节点s=getchar();//getchar和scanf的区别是什么手动从键盘输入字符//描述树中表示空树时的情况if(s=='#'){*root=NULL;}else{*root=(Tree)malloc(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(Sqstack1*Q,QElemTypee)//入队{if((Q-rear+1)%MAXQSIZEZ==Q-front)//判断对是否满?returnERROR;Q-