Status preordertraverse_b(bitree *T,Status (* visit)(elemtype e))
{
bitree *p;
sqstack s;
initstack (s);
p=T;
while(p||!stackempty(s))
{
if(p)
{
if(!visit(p->data))
typedef struct bitree
{
elemtype data;//数据域
struct bitree *lchild,*rchild;//指针域
}BiTree;//二叉树结点结构
4.1.2本算法使用的栈采用顺序存储结构，设栈的初始大小为100，增长量为10，栈的数据类型如下：
#definestack_init_size100//初始大小
if(visit(T->data))
if(inordertraverse(T->rchild,visit))
return ok;
return error；
else
return ok;
}
算法三后序递归遍历二叉树算法
Status postordertraverse(bitree *T,Status (* visit)(elemtype e))
}
}
return ok;
}
算法六后序非递归遍历二叉树算法
Status postordertraverse_b(bitree *T,Status (* visit)(elemtype e))
{
sqstack s;
BiTree *p;
BiTree *pre=NULL;
initstack(s);
p=T;
while((p!=NULL)||!stackempty(s))
山西大学计算机与信息技术学院
实验报告
姓名
学号
专业班级
课程名称
实验日期
成绩
指导教师
批改日期
实验名称
一、实验目的：
二叉树的遍历操作是树形结构其他众多操作的基础。本实验旨在使学生进一步加深对二叉树的先序、中序和后序等三种遍历次序特点的理解，熟悉二叉链表存储结构，熟练掌握二叉树上的递归算法的设计技术。
二、实验内容：
构造一棵二叉树，使用二叉链表方式存储，试设计程序，按照先序、中序、后序三种方式将这棵二叉树遍历出来，要求使用递归和非递归两种实现方式。
三、主要算法：
4.1数据结构描述
4.1.1本算法研究的待遍历的二叉树结点的数据类型如下，设二叉树结点的数据域均为字符型：
typedef char elemtype;//元素类型定义
用中序非递归算法遍历二叉树的输出为：dbeafcg
用后序非递归算法遍历二叉树的输出为：debfgca
运行结果如下图所示：
4.2.4先序非递归遍历二叉树的基本思想：T是要遍历的树的根指针，若T != NULL，引入栈模拟递归工作栈，初始时栈为空。用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针。
4.2.5中序非递归遍历二叉树的基本思想：T是要遍历的树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针。
4.3算法实现
算法一先序递归遍历二叉树算法
Status preordertraverse(bitree *T,Status (* visit)(elemtype e))
{
if(T)
{if(visit(T->data))
if(preordertraverse(T->lchild,visit))
if(preordertraverse(T->rchild,visit))
{
if(T)
{if(postordertraverse(T->lchild,visit))
if(postordertraverse(T->rchild,visit))
if(visit(T->data))
return ok;
return error;
}
else
return ok;
}
算法四先序非递归遍历二叉树算法
g
f
e
b
a
aaaaaaaaa
c
d
4.2.1先序递归遍历二叉树的基本思想：首先访问二叉树的根结点；其次先序递归的遍历根结点的左子树；最后先序递归的遍历根结点的右子树。
4.2.2中序递归遍历二叉树的基本思想：首先中序递归的遍历根结点的左子树；其次访问根结点；最后中序递归的遍历根结点的右子树。
4.2.3后序递归遍历二叉树的基本思想：首先后序递归的遍历根结点的左子树；其次后序递归的遍历根结点的右子树；最后访问根结点。
return error;
push(s,p);
p=p->lchild;
}
else
{
pop(s,p);
p=p->rchild;
}}Biblioteka return ok;}
算法五中序非递归遍历二叉树算法
Status inordertraverse_b(bitree *T,Status (* visit)(elemtype e))
{
if(p!=NULL)
{
push(s,p);
p=p->lchild;
}
else
{
p=*(s.top-1);
if(p->rchild!=NULL&&pre!=p->rchild)
p=p->rchild;
else
{
p=pre=*(s.top-1);
visit(p->data);
pop(s,p);
p=NULL;
return ok;
return error;
}
else
return ok;
}
算法二中序递归遍历二叉树算法
Status inordertraverse(bitree *T,Status (* visit)(elemtype e))
{
if(T)
{if(inordertraverse(T->lchild,visit) )
#definestackincrement 10//增量
typedef struct
{
bitree* *base;//栈底指针
bitree* *top;//栈顶指针
int stacksize;//栈的大小
}sqstack;//顺序栈
4.2函数功能描述
假设待遍历的二叉树的数据域序列为：a、b、c、d、e、f、g，该二叉树表示如下：
}
}
}
return ok;
}
五、实验结果分析：
当输入的二叉树数据域序列为：a、b、c、d、e、f、g时，各种遍历算法的输出分别为：
用先序递归算法遍历二叉树的输出为：abdecfg
用中序递归算法遍历二叉树的输出为：dbeafcg
用后序递归算法遍历二叉树的输出为：debfgca
用先序非递归算法遍历二叉树的输出为：abdecfg
{
BiTree *p;
sqstack s;
initstack (s);
p=T;
while(p||!stackempty(s))
{
if(p)
{
push(s,p);
p=p->lchild;
}
else
{
pop(s,p);
if(!visit(p->data))
return error;
p=p->rchild;
4.2.6后序非递归遍历二叉树的基本思想：T是要遍历的树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)；也可以使用堆栈来记录根结点的左右子树是否均遍历过，本实验采用堆栈的方法。