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

信息工程学院《数据结构》

课程设计报告

设计题目 二叉树的中序的递归、非递归遍历算法

专 业 班 级

小 组 成 员

一． 题目：二叉树的中序的递归、非递归遍历算法 二． 小组任务分工

马凯：编写二叉树中序递归遍历、非递归遍历 崔妍：编写二叉树层序遍历、打印二叉树 三． 设计目标

帮助学生熟练掌握二叉树的遍历； 四． 问题描述

二叉树的中序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树

为了的实现。 五． 概要设计

实现上述程序功能，需要定义一个结构体

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 //利用结构体定义栈