信息工程学院《数据结构》
课程设计报告
设计题目 二叉树的中序的递归、非递归遍历算法
专 业 班 级
小 组 成 员
一． 题目：二叉树的中序的递归、非递归遍历算法 二． 小组任务分工
马凯：编写二叉树中序递归遍历、非递归遍历 崔妍：编写二叉树层序遍历、打印二叉树 三． 设计目标
帮助学生熟练掌握二叉树的遍历； 四． 问题描述
二叉树的中序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树
为了的实现。 五． 概要设计
实现上述程序功能，需要定义一个结构体
typedef struct tree //定义数据结构体 {
ElemType data;//数据信息 struct tree *lchild;//左孩子 struct tree *rchild;//右孩子
}TreeNode,*Tree;
typedef struct //层序遍历的队列结构体定义 {
QElemType base[MAXQSIZEZ]; int front;//定义队头 int rear;//定义队尾
}Sqstack1;
typedef struct stack //非递归遍历栈 {
Tree *base;//定义栈底 Tree *top;//定义栈顶
int stackszie; //指示栈内剩余空间
}Sqstack;
六． 详细设计（程序代码及核心代码流程图）
总体操作步骤：
(1)以前序遍历的方式输入二叉树；
(2)打印出二叉树的中序递归、非递归遍历、层序遍历； (3)完成操作 。
#include
//******************************8
typedef char ElemType;
typedef struct tree //定义数据结构体 {
ElemType data;//数据信息 struct tree *lchild;//左孩子 struct tree *rchild;//右孩子 }TreeNode,*Tree;
//层序遍历
#define MAXQSIZEZ 100//宏定义最大长度 typedef Tree QElemType;
typedef struct //层序遍历的队列结构体定义 {
QElemType base[MAXQSIZEZ]; int front;//定义队头 int rear;//定义队尾 }Sqstack1;
typedef struct stack //利用结构体定义栈
{
Tree *base;//定义栈底 Tree *top;//定义栈顶
int stackszie; //指示栈内剩余空间 }Sqstack;
void CreateTree(Tree *root)//创建一棵树 {
char s;//定义树的根节点 s=getchar();
//描述树中表示空树时的情况 if(s == '#') { } else { } //返回值 }
//层序遍历队列定义
void InitQueue(Sqstack1 *Q) //初始化前尾指针 {
Q->front=Q->rear=0;//队头等于队尾 }
Status ErQueue(Sqstack1 *Q, QElemType e) //入队 {
if((Q->rear+1)%MAXQSIZEZ==Q->front)//判断对是否满
return ERROR;
*root=(Tree)malloc(sizeof(TreeNode));//申请空间，用malloc函数动态分配空间 if(!root)//判断根节点是否为空，即，该树是否为空 { }
(*root)->data=s; //将getcher得到的数据分配到树中 CreateTree(&(*root)->lchild); CreateTree(&(*root)->rchild);
printf(\分配内存失败！\); *root= NULL;
Q->base[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->base[Q->front];
Q->front=(Q->front+1)%MAXQSIZEZ; return OK; }
Status QueueEmpty(Sqstack1 Q) //判断队列是否为空 {
if(Q.rear==Q.front)
return TRUE;
else }
void Traverse(Tree T)//层序遍历 {
Sqstack1 Q; Tree p; p=T;
InitQueue(&Q);//初始化 if(p)
ErQueue(&Q,p); return FALSE;
while (!QueueEmpty(Q)) { }
printf(\); }
DeQueue(&Q,&p);//出队 printf(\,p->data); if(p->lchild)
ErQueue(&Q,p->lchild);
if(p->rchild)
ErQueue(&Q,p->rchild);
二叉树的中序的递归、非递归遍历算法
