《数据结构》第六次实验报告
学生姓名
学生班级
学生学号
指导老师
一、实验内容
1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序
以及按层次遍历的操作，求所有叶子及结点总数的操作。
2) 输出树的深度，最大元，最小元。
二、需求分析
遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。
递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。
下面重点来讲述非递归方法：
首先介绍先序遍历：
先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。
再次介绍中序遍历：
中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。
最后介绍后序遍历：
后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。
三、详细设计
源代码：
#include
#define MAX 100 //表示栈的最大容量
#define FULL 99//表示栈满
#define EMPTY -1//表示栈空
typedef struct Tnode //定义结点
{
char data;//存储结点数据
struct Tnode *left;//定义结点左子指针
struct Tnode *right;//定义右子指针
}Tnode,*Pnode;//声明Tnode类型的变量和指针typedef struct Stack//定义栈
{
Pnode pnode[MAX];//存放数据
int p;//栈顶指针
}Stack,*Pstack;//定义Stack类型的变量和指针void Push (Pstack pstack,Pnode pnode)//入栈{
pstack->p ++;
pstack->pnode[pstack->p] = pnode;//赋值}
Pnode Pop(Pstack pstack)//出栈
{
return pstack->pnode[pstack->p--];
}
Pnode Top (Pstack pstack)//看栈顶元素
{
return pstack->pnode[pstack->p];
}
int Isempty (Pstack pstack)//栈判空
{
if(pstack->p==EMPTY)
return 1;
else
return 0;;
}
int Isfull (Pstack pstack )//栈满
{
if (pstack ->p==FULL)
return 1;
else
return 0;
}
void Initstack (Pstack pstack)//初始化栈
{
pstack->p=EMPTY;
}
void Inittnode(Pnode root,Pnode left,Pnode right,char data)//初始化结点
{
root->left=left;
root->right = right;
root->data = data;
}
void PreorderR(Pnode proot)//递归先序遍历算法
{
if(proot)
{
printf("%2c",proot->data);
PreorderR(proot->left);
PreorderR(proot->right);
}
}
void InorderR(Pnode proot)//递归中序遍历算法
{
if(proot)
{
InorderR(proot->left);
printf("%2c",proot->data);
InorderR(proot->right);
}
}
void PostorderR(Pnode proot)//递归后序遍历算法
{
if(proot)
{
PostorderR(proot->left);
PostorderR(proot->right);
printf("%2c",proot->data);
}
}
void PreorderI(Pnode proot,Pstack pstack)//非递归先序遍历算法
{
Initstack(pstack);//初始化栈
while(proot||!Isempty(pstack))//如果栈空并且结点指针空，则结束循环{
if(proot)
{
printf("%2c",proot->data);
