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

《二叉树的中序的递归、非递归遍历算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、ttree*rchild;//右孩子}TreeNode,*Tree;typedefstruct//层序遍历的队列结构体定义{QElemTypebase[MAXQSIZEZ];intfront;//定义队头intrear;//定义队尾}Sqstack1;typedefstructstack//非递归遍历栈{Tree*base;//定义栈底Tree*top;//定义栈顶intstackszie;//指示栈内剩余空间}Sqstack;六．详细设计（程序代码及核心代码流程图）总体操作步骤：(1)以前序遍历的方式输入二叉树；(2)打印出二叉树的中序递归、非递归遍历、层序遍

3、历；(3)完成操作。#include#include#defineSTACKINITSIZE100#defineSTACKINCREASESIZE20//层序遍历部分#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;//******************************8typedefcharElemType;typedefstructtree//定义数据结构体{ElemTypedata;//数据信息s

4、tructtree*lchild;//左孩子structtree*rchild;//右孩子}TreeNode,*Tree;//层序遍历#defineMAXQSIZEZ100//宏定义最大长度typedefTreeQElemType;typedefstruct//层序遍历的队列结构体定义{QElemTypebase[MAXQSIZEZ];intfront;//定义队头intrear;//定义队尾}Sqstack1;typedefstructstack//利用结构体定义栈{Tree*base;//定义栈底Tree*top;//定义栈顶intstackszie;//指

5、示栈内剩余空间}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)->l

6、child);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

7、(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);//

8、初始化if(p)ErQu