文档介绍：word
word
- 1 - / 18
word
数据结构〔双语〕
——项目文档报告
递归、非递归两种算法遍历二叉树
专 业： 计算机科学与技术
班 级：
指导教师：树
完毕
按后根遍历方式遍历右子树
访问根结点
Y
N
图3 .后序递归流程图
word
word
- 8 - / 18
word
开始
申请一个栈stack
判断结点是否空
输出结点值，压栈，指针指向它的左孩子
判断结点是否空
弹出栈顶元素，
指向结点的右孩子
完毕
判断栈或结点是否空
N
Y
N
Y
N
图4 . 先序非递归流程图
word
word
- 9 - / 18
word
开始
申请一个stack
判断结点是否空
把结点压栈，指针指向它的左孩子
判断结点是否空
弹栈，设为当前结点，打印结点值，指向右孩子
完毕
判断栈或结点是否空
N
Y
Y
N
N
图1. 流程图
图2. 流程图
图3.. 流程图
图 5. 中序非递归流程图
word
word
- 10 - / 18
word
开始
申请一个栈stack，用一个bool变量tag标记右孩子已被访问
把当前结点压栈，
p=p->lchild
top++
判断标志tag是否为1
输出结点值
p = ()
p= p->rchild
完毕
N
Y
Y
N
N
Y
Y
N
判断结点是否空
判断栈或结点是否为空
判断结点是否空
图 6. 后序非递归流程图
word
word
- 11 - / 18
word
三 、源代码
下面给出的是实现递归和非递归遍历二叉树的算法程序的源代码〔合并在一起〕：
#include <>
#include <>
#define MAX 100 //定义堆栈最大容量
enum BOOL{False,True};
enum RVISIT{Rchildnovisit,Rchildvisit};
//在后序遍历二叉树时用来指示是否已访问过右子树
typedef struct BiTNode //定义二叉树节点结构
{char data; //数据域
struct BiTNode *lchild,*rchild; //左右孩子指针域
}BiTNode,*BiTree;
typedef struct //定义堆栈结构
{BiTree elem[MAX]; //栈区
int top; //栈顶指针
}BiTreeStack;
void Initial(BiTreeStack &); //初始化一个堆栈
BOOL Push(BiTreeStack &,BiTree); //将一个元素入栈
BOOL Pop(BiTreeStack&,BiTree &); //将一个元素出栈
BOOL Gettop(BiTreeStack ,BiTree &); //取得堆栈栈顶元素
BOOL StackEmpty(BiTreeStack); //判断堆栈是否已空
void CreateBiTree(BiTree &); //生成一个二叉树
void PreOrder(BiTree); //先序非递归遍历二叉树
void InOrder(BiTree); //中序非递归遍历二叉树
void PostOrder(BiTree); //后序非递归遍历二叉树
void PreTravel(BiTree ); //先序递归遍历二叉树
void MidTravel(BiTree ); //中序递归遍历二叉树
void PostTravel(BiTree ); //后序递归遍历二叉树
int main()
{ BiTree T;
int flag=1; //标记
BOOL temp;
printf("二叉树的递归和非递