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

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

2、ee *rchild;/右孩子TreeNode,*Tree;typedef struct /层序遍历的队列结构体定义QElemType baseMAXQSIZEZ;int front;/定义队头int rear;/定义队尾Sqstack1;typedef struct stack /非递归遍历栈Tree *base;/定义栈底Tree *top;/定义栈顶int stackszie; /指示栈内剩余空间Sqstack; 六 详细设计（程序代码及核心代码流程图）总体操作步骤：(1)以前序遍历的方式输入二叉树；(2)打印出二叉树的中序递归、非递归遍历、层序遍历；(3)完成操作 。#include&

3、lt;stdio.h>#include<stdlib.h>#define STACKINITSIZE 100#define STACKINCREASESIZE 20/层序遍历部分#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;/*8typedef char ElemType;typedef struct tree /定义数据结构体ElemType data;/数据信息struct tree *lchild;/左孩子struct tree

4、*rchild;/右孩子TreeNode,*Tree; /层序遍历#define MAXQSIZEZ 100/宏定义最大长度typedef Tree QElemType;typedef struct /层序遍历的队列结构体定义QElemType baseMAXQSIZEZ;int front;/定义队头int rear;/定义队尾Sqstack1;typedef struct stack /利用结构体定义栈Tree *base;/定义栈底Tree *top;/定义栈顶int stackszie; /指示栈内剩余空间Sqstack; void CreateTree(Tree *root)/创建一

5、棵树char s;/定义树的根节点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

6、); /返回值/层序遍历队列定义void InitQueue(Sqstack1 *Q) /初始化前尾指针Q->front=Q->rear=0;/队头等于队尾Status ErQueue(Sqstack1 *Q, QElemType e) /入队if(Q->rear+1)%MAXQSIZEZ=Q->front)/判断对是否满return ERROR;Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZEZ; return OK;Status DeQueue(Sqstack1 *Q,QElemType *e) /删

7、除元素if(Q->front=Q->rear)/队为空，不能删除return ERROR;*e=Q->baseQ->front;Q->front=(Q->front+1)%MAXQSIZEZ; return OK;Status QueueEmpty(Sqstack1 Q) /判断队列是否为空if(Q.rear=Q.front)return TRUE;elsereturn FALSE;void Traverse(Tree T)/层序遍历Sqstack1 Q;Tree p;p=T;InitQueue(&Q);/初始化if(p)ErQueue(&Q

8、,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");/*/使用递归完成中序遍历void InOrder(Tree root )if(root)/如果根节点不为空，一句左根右的顺序遍历InOrder(root->lchild);printf("

9、%c",root->data);InOrder(root->rchild);/初始化栈void InStack(Sqstack *s)s->base=(Tree*)malloc(STACKINITSIZE*sizeof(TreeNode);/动态分配空间if(!s->base)printf("栈创建失败！");s->top=s->base;s->stackszie=STACKINITSIZE;/栈中的剩余内存/压栈void Push(Sqstack *s,Tree root)if(*s).top-(*s).base)>

10、;=(*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+;/进行依次入栈操作/获得栈顶元素void GetTop(Sqstack *s, Tree *

11、root)*root =*(*s).top-1);/弹出栈顶元素void Pop(Sqstack *s,Tree *root)if(*s).top = (*s).base) /=与=printf("栈已经空了！");*root = *(-(*s).top);/判断栈是否为空int StackEmpty(Sqstack *s)if(s->top= s->base) return 1;else return 0;/非递归中序遍历void InOrderS(Tree root)Tree p=root;Sqstack s;InStack(&s);while (p

12、 |!StackEmpty(&s)if(p) Push(&s,p);p=p->lchild;else Pop(&s,&p); printf("%c",p->data);p=p->rchild;void PrintTree(Tree root,int nLayer)/树状打印二叉树 int i;if(root = NULL)return;PrintTree(root->rchild ,nLayer+1);for(i=0;i<nLayer;i+)printf(" ");printf("%

13、cn",root->data);PrintTree(root->lchild ,nLayer+1);void main() int layer=0;Tree root=NULL;printf("先序遍历输入二叉树,#代表空子树:n");CreateTree( &root);/参数不懂printf("递归中序遍历输出:n"); InOrder(root);printf("n");printf("非递归中序遍历输出:n");InOrderS(root);printf("n&quo

14、t;);printf("层序遍历二叉树：n");Traverse(root);printf("打印二叉树：n");PrintTree(root, layer);printf("n");七 测试分析测试内容测试结果输入二叉树正确递归中序遍历正确非递归中序遍历正确层序遍历正确打印二叉树正确八课程设计总结此次课程设计中，题目为二叉树的中序遍历、层序遍历，在完成这次设计过程中，遇到了好多问题，例如：不知道如何循环完成二叉树的非递归遍历，如何利用栈和队列的特性，怎么将它们合理的进栈和出栈。 通过这次课程设计的设计，使我明白了自己在学习过程中的一

15、些漏洞，比如，栈和队列中出入的一些细节的处理、结构体指针的应用、运行过程中内存的分配等。#include<stdio.h>#include<stdlib.h>#define STACKINITSIZE 100#define STACKINCREASESIZE 20/层序遍历部分#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;/*8typedef char ElemType;typedef struct tree /定义数据结构体El

16、emType data;/数据信息struct tree *lchild;/左孩子struct tree *rchild;/右孩子TreeNode,*Tree;/重命名/层序遍历#define MAXQSIZEZ 100/宏定义最大长度typedef Tree QElemType;typedef struct /层序遍历的队列结构体定义QElemType baseMAXQSIZEZ;int front;/定义队头int rear;/定义队尾Sqstack1;typedef struct stack /利用结构体定义栈Tree *base;/定义栈底Tree *top;/定义栈顶int stac

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

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

19、Q->rear=e;Q->rear=(Q->rear+1)%MAXQSIZEZ;/？return OK;Status DeQueue(Sqstack1 *Q,QElemType *e) /删除元素if(Q->front=Q->rear)/队为空，不能删除return ERROR;*e=Q->baseQ->front;Q->front=(Q->front+1)%MAXQSIZEZ;/？return OK;Status QueueEmpty(Sqstack1 Q) /判断队列是否为空if(Q.rear=Q.front)return TRUE;e

20、lsereturn FALSE;void Traverse(Tree T)/层序遍历Sqstack1 Q;Tree p;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"

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

22、>base;s->stackszie=STACKINITSIZE;/栈中的剩余内存/压栈void Push(Sqstack *s,Tree root)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).s

23、tackszie+=STACKINCREASESIZE;*(s->top)= root; s->top+;/进行依次入栈操作/获得栈顶元素void GetTop(Sqstack *s, Tree *root)/?*root =*(*s).top-1);/弹出栈顶元素void Pop(Sqstack *s,Tree *root)if(*s).top = (*s).base) /=与=printf("栈已经空了！");*root = *(-(*s).top);/判断栈是否为空int StackEmpty(Sqstack *s)if(s->top= s->base) /=写为=return 1;else return 0;/非递归中序遍历void InOrderS(Tree roo