信息工程学院《数据结构》
课程设计报告
设计题目 二叉树的中序的递归、非递归遍历算法 专 业 班 级
小 组 成 员
一． 题目：二叉树的中序的递归、非递归遍历算法
二． 小组任务分工
马凯：编写二叉树中序递归遍历、非递归遍历
崔妍：编写二叉树层序遍历、打印二叉树
三． 设计目标
帮助学生熟练掌握二叉树的遍历；
四． 问题描述
二叉树的中序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树为了的实现。
五． 概要设计
实现上述程序功能，需要定义一个结构体 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
#include
#define STACKINITSIZE 100
#define STACKINCREASESIZE 20
//层序遍历部分
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
//******************************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("\n");
} DeQueue(&Q,&p);//出队 printf("%c",p->data); if(p->lchild) ErQueue(&Q,p->lchild); if(p->rchild) ErQueue(&Q,p->rchild);
//**********************************
//使用递归完成中序遍历
void InOrder(Tree root ) {
if(root)//如果根节点不为空，一句左根右的顺序遍历
{
} }
//初始化栈
void InStack(Sqstack *s) {
s->base=(Tree*)malloc(STACKINITSIZE*sizeof(TreeNode));//动态分配空间
if(!s->base)
{
}
s->top=s->base;
s->stackszie=STACKINITSIZE;//栈中的剩余内存 }
//压栈
void Push(Sqstack *s,Tree root) {
if(((*s).top-(*s).base)>=(*s).stackszie)//判断栈是否满？如果满
{
(*s).base printf("栈创建失败！"); InOrder(root->lchild); printf("%c",root->data); InOrder(root->rchild);
=(Tree*)realloc((*s).base,((*s).stackszie+STACKINCREASESIZE)*sizeof(Tree));//扩容
}
*(s->top)= root;
s->top++;//进行依次入栈操作 if(!(*s).base) { } (*s).top=(*s).base+(*s).stackszie; (*s).stackszie+=STACKINCREASESIZE; printf("内存分配失败！");
}
//获得栈顶元素
void GetTop(Sqstack *s, Tree *root) {
*root =*((*s).top-1); }
//弹出栈顶元素
void Pop(Sqstack *s,Tree *root) {
if((*s).top == (*s).base) //=与==
{
}
*root = *(--(*s).top); }
//判断栈是否为空
int StackEmpty(Sqstack *s) {
if(s->top== s->base)
return 1; printf("栈已经空了！");
else
return 0; }
//非递归中序遍历
void InOrderS(Tree root) {
Tree p=root;
Sqstack s;
InStack(&s);
while (p ||!StackEmpty(&s)) {
if(p) { } else { Push(&s,p); p=p->lchild;
} } } 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
printf("%c\n",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");
printf("层序遍历二叉树：\n");
Traverse(root);
printf("打印二叉树：\n");
PrintTree(root, layer);
printf("\n");
}
七． 测试分析
八．课程设计总结
此次课程设计中，题目为二叉树的中序遍历、层序遍历，在完成这次设计过程中，遇到了好多问题，例如：不知道如何循环完成二叉树的非递归遍历，如何利用栈和队列的特性，怎么将它们合理的进栈和出栈。
通过这次课程设计的设计，使我明白了自己在学习过程中的一些漏洞，比如，栈和队列中出入的一些细节的处理、结构体指针的应用、运行过程中内存的分配等。
信息工程学院《数据结构》
课程设计报告
设计题目 二叉树的中序的递归、非递归遍历算法 专 业 班 级
小 组 成 员
一． 题目：二叉树的中序的递归、非递归遍历算法
二． 小组任务分工
马凯：编写二叉树中序递归遍历、非递归遍历
崔妍：编写二叉树层序遍历、打印二叉树
三． 设计目标
帮助学生熟练掌握二叉树的遍历；
四． 问题描述
二叉树的中序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树为了的实现。
五． 概要设计
实现上述程序功能，需要定义一个结构体 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
#include
#define STACKINITSIZE 100
#define STACKINCREASESIZE 20
//层序遍历部分
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
//******************************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("\n");
} DeQueue(&Q,&p);//出队 printf("%c",p->data); if(p->lchild) ErQueue(&Q,p->lchild); if(p->rchild) ErQueue(&Q,p->rchild);
//**********************************
//使用递归完成中序遍历
void InOrder(Tree root ) {
if(root)//如果根节点不为空，一句左根右的顺序遍历
{
} }
//初始化栈
void InStack(Sqstack *s) {
s->base=(Tree*)malloc(STACKINITSIZE*sizeof(TreeNode));//动态分配空间
if(!s->base)
{
}
s->top=s->base;
s->stackszie=STACKINITSIZE;//栈中的剩余内存 }
//压栈
void Push(Sqstack *s,Tree root) {
if(((*s).top-(*s).base)>=(*s).stackszie)//判断栈是否满？如果满
{
(*s).base printf("栈创建失败！"); InOrder(root->lchild); printf("%c",root->data); InOrder(root->rchild);
=(Tree*)realloc((*s).base,((*s).stackszie+STACKINCREASESIZE)*sizeof(Tree));//扩容
}
*(s->top)= root;
s->top++;//进行依次入栈操作 if(!(*s).base) { } (*s).top=(*s).base+(*s).stackszie; (*s).stackszie+=STACKINCREASESIZE; printf("内存分配失败！");
}
//获得栈顶元素
void GetTop(Sqstack *s, Tree *root) {
*root =*((*s).top-1); }
//弹出栈顶元素
void Pop(Sqstack *s,Tree *root) {
if((*s).top == (*s).base) //=与==
{
}
*root = *(--(*s).top); }
//判断栈是否为空
int StackEmpty(Sqstack *s) {
if(s->top== s->base)
return 1; printf("栈已经空了！");
else
return 0; }
//非递归中序遍历
void InOrderS(Tree root) {
Tree p=root;
Sqstack s;
InStack(&s);
while (p ||!StackEmpty(&s)) {
if(p) { } else { Push(&s,p); p=p->lchild;
} } } 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
printf("%c\n",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");
printf("层序遍历二叉树：\n");
Traverse(root);
printf("打印二叉树：\n");
PrintTree(root, layer);
printf("\n");
}
七． 测试分析
八．课程设计总结
此次课程设计中，题目为二叉树的中序遍历、层序遍历，在完成这次设计过程中，遇到了好多问题，例如：不知道如何循环完成二叉树的非递归遍历，如何利用栈和队列的特性，怎么将它们合理的进栈和出栈。
通过这次课程设计的设计，使我明白了自己在学习过程中的一些漏洞，比如，栈和队列中出入的一些细节的处理、结构体指针的应用、运行过程中内存的分配等。