实验三? 二叉树遍历（递归算法和非递归算法）
一．实验目的
1.掌握二叉树的存储结构与基本操作
2.掌握二叉树的遍历算法
二．实验要求与内容
1. 建立二叉树，采用递归的方式完成前、中、后三种遍历。（建立二叉树的算法参考课本P174）
2. 建立二叉树，采用非递归的方式完成前、中、后三种遍历。
三．实验步骤
1．数据结构
递归算法只需要定义一个结构体储存各个节点信息，而非递归算法需要多定义一个栈来储存遍历时的信息。在非递归算法的后序遍历中还需要创建一个一维数组用来做标识结点的左右子树树否都遍历过。详细解释请看附录中结合代码的解释。
2．算法设计
递归算法根据不同的遍历方式采取不同递归调用遍历顺序即可。
非递归算法
前序遍历的核心思想：当node所指的结点不为空时，访问该结点即输出该结点的信息并将该结点所在的链接点的地址进栈，然后再将node指向该结点的左子树；当node所指的结点为空时，则从栈中退出栈顶元素给node，然后将该node指向该结点的右孩子结点。重复上述过程，直至node为NULL，并且栈也为空，遍历结束。
中序遍历的核心思想：当node所指的结点不为空时，则将该结点所在的链接点的地址进栈，然后再将node指向该结点的左子树；当node所指的结点为空时，则从栈中退出栈顶元素给node，访问该结点即输出该结点的信息，然后将该node指向该结点的右孩子结点。重复上述过程，直至node为NULL，并且栈也为空，遍历结束。
后序遍历的核心思想：当node指向某一个结点时，不能马上对它进行访问，而要先遍历它的左子树，因而要将该结点的地址进栈，当其左子树遍历完毕以后，再次搜索要该结点时（该结点的地址通过退栈得到），还不能对它进行访问，还需要遍历它的右子树，所以，将该结点的地址再一次进栈。只有该结点的右子树被遍历以后回到该结点，才访问该结点，为了标明某结点是否可以被访问，引入一个标志变量标明。
3．程序
void bulidtree(bitree &T)//二叉树的建立（按照前序遍历建立二叉树）
{
? ? char c;
? ? cin>>c;
? ? if(c=='#')//判断该节点是否存在
? ? ? ? T =NULL;
? ? else
? ? {
? ? ? ? T=new bitreenode;
? ? ? ? T->date=c;
? ? ? ? bulidtree(T->left);//建立左子树
? ? ? ? bulidtree(T->right);//建立右子树
? ? }
}
//中序后序的递归算法类似于前序只改变了输出位置
void front(bitree T)//前序遍历二叉树
{
? ? if(T!=NULL)
? ? {
? ? ? ? cout<<T->date<<" ";
? ? ? ? front(T->left);
? ? ? ? front(T->right);
? ? }
}
//非递归前序遍历，中序遍历类似于前序遍历
void front1(bitree T){
? ? if(T){
? ? ? ? Stack s;
? ? ? ? init(s.top);
? ? ? ? bitree node =T;
? ? ? ? while(node!=NULL||!empty(s.top)){//当结点为空并且栈也为空时退出
? ? ? ? ? ? while(node!=NULL){//当结点不为空时输出该结点并将该结点压入栈并遍历左子树
? ? ? ? ? ? ? ? printf("%c ",node->date);
? ? ? ? ? ? ? ? push(&s,node);
? ? ? ? ? ? ? ? node=node->left;
? ? ? ? ? ? }
? ? ? ? ? ? if(!empty(s.top)){//结点为NULL但是栈不为空
? ? ? ? ? ? ? ? node=pop(&s);//弹出栈顶元素并赋给node
? ? ? ? ? ? ? ? node=node->right;//遍历结点的右子树
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
//后序遍历
?void back1(bitree T){
?int b[20];
?if(T){
?Stack s;
?init(s.top);
?bitree node =T;
?while(node!=NULL || !empty(s.top)){
?while(node!=NULL){
?push(&s,node);//第一次进栈
?b[s.top]=0;
?node=node->left;
?}
?node=pop(&s);
?int flag=b[s.top+1];
?if(flag==0){? //说明只进过一次
?push(&s,node);//第二次进栈
?b[s.top]=1;
?node=node->right;
?}
?else{? ? //已经进过两次栈，说明左右子树都已经遍历过了
?printf("%c ",node->date);
?node=NULL;
?}
?}
?}
?}
4．程序调试
测试数据、程序运行结果截图?
四．结果与体会
该实验的难点在于非递归算法的设计，刚开始的时候没有想法，后面参考书上的方法发现可以用while或则do..while在一定程度上代替递归算法实现相同的目的，比如递归实现找到最左子树可以用while(node->left!=NULL)实现。
五．源程序
另附
#include<iostream>
using namespace std;
typedef struct node{
? ? node *left;
? ? node *right;
? ? char date;
}bitreenode,*bitree;
typedef struct {
? ? bitree stack[100];
? ? int top;
}Stack;
void init(int &top){
? ? top=-1;
}
int full(int top){
? ? return top==99;
}
int empty(int top){
? ? return top==-1;
}
int push(Stack *s,bitree a){
? ? int top1=s->top;
? ? if(a==NULL)
? ? ? ? return 0;
? ? else
? ? {
? ? ? ? s->top++;
? ? ? ? s->stack[++top1]=a;
? ? ? ? return 1;
? ? }
}
bitree pop(Stack *s){
? ? int top1=s->top;
? ? if (top1!=-1){
? ? ? ? s->top--;
? ? ? ? return s->stack[s->top+1];
? ? }
? ? else
? ? ? ? return NULL;
}
void bulidtree(bitree &T)//二叉树的建立（按照前序遍历建立二叉树）
{
? ? char c;
? ? cin>>c;
? ? if(c=='#')//判断该节点是否存在
? ? ? ? T =NULL;
? ? else
? ? {
? ? ? ? T=new bitreenode;
? ? ? ? T->date=c;
? ? ? ? bulidtree(T->left);//建立左子树
? ? ? ? bulidtree(T->right);//建立右子树
? ? }
}
void front(bitree T)//前序遍历二叉树
{
? ? if(T!=NULL)
? ? {
? ? ? ? cout<<T->date<<" ";
? ? ? ? front(T->left);
? ? ? ? front(T->right);
? ? }
}
void mid(bitree T)//中序遍历二叉树
{
? ? if(T!=NULL)
? ? {
? ? ? ? mid(T->left);
? ? ? ? cout<<T->date<<" ";
? ? ? ? mid(T->right);
? ? }
}
void back(bitree T)//后序遍历二叉树
{
? ? if(T!=NULL)
? ? {
? ? ? ? back(T->left);
? ? ? ? back(T->right);
? ? ? ? cout<<T->date<<" ";
? ? }
}
//非递归前序遍历
void front1(bitree T){
? ? if(T){
? ? ? ? Stack s;
? ? ? ? init(s.top);
? ? ? ? bitree node =T;
? ? ? ? while(node!=NULL||!empty(s.top)){//当结点为空并且栈也为空时退出
? ? ? ? ? ? while(node!=NULL){//当结点不为空时输出该结点并将该结点压入栈并遍历左子树
? ? ? ? ? ? ? ? printf("%c ",node->date);
? ? ? ? ? ? ? ? push(&s,node);
? ? ? ? ? ? ? ? node=node->left;
? ? ? ? ? ? }
? ? ? ? ? ? if(!empty(s.top)){//结点为NULL但是栈不为空
? ? ? ? ? ? ? ? node=pop(&s);//弹出栈顶元素并赋给node
? ? ? ? ? ? ? ? node=node->right;//遍历结点的右子树
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
//中序遍历
void mid1(bitree T){
? ? if(T){
? ? ? ? Stack s;
? ? ? ? init(s.top);
? ? ? ? bitree node =T;
? ? ? ? while(node!=NULL || !empty(s.top)){
? ? ? ? ? ? while(node!=NULL){
? ? ? ? ? ? ? ? push(&s,node);
? ? ? ? ? ? ? ? node=node->left;
? ? ? ? ? ? }
? ? ? ? ? ? if(!empty(s.top)){
? ? ? ? ? ? ? ? node=pop(&s);
? ? ? ? ? ? ? ? printf("%c ",node->date);
? ? ? ? ? ? ? ? node=node->right;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
?//后序遍历
?void back1(bitree T){
?int b[20];
?if(T){
?Stack s;
?init(s.top);
?bitree node =T;
?while(node!=NULL || !empty(s.top)){
?while(node!=NULL){
?push(&s,node);//第一次进栈
?b[s.top]=0;
?node=node->left;
?}
?node=pop(&s);
?int flag=b[s.top+1];
?if(flag==0){? //说明只进过一次
?push(&s,node);//第二次进栈
?b[s.top]=1;
?node=node->right;
?}
?else{? ? //已经进过两次栈，说明左右子树都已经遍历过了
?printf("%c ",node->date);
?node=NULL;
?}
?}
?}
?}
int main()
{
? ? bitree T;
? ? cout<<"开始建立二叉树"<<endl;
? ? cout<<"请按照前序遍历输入二叉树信息"<<endl;
? ? bulidtree(T);
? ? cout<<"二叉树创建成功"<<endl;
? ? cout<<"递归方式"<<endl;
? ? cout<<"前序遍历: ";
? ? front(T);
? ? cout<<endl;
? ? cout<<"中序遍历: ";
? ? mid(T);
? ? cout<<endl;
? ? cout<<"后续遍历: ";
? ? back(T);
? ? cout<<endl;
? ? cout<<"非递归方式: "<<endl;
? ? cout<<"前序遍历: ";
? ? front1(T);
? ? cout<<endl;
? ? cout<<"中序遍历: ";
? ? mid1(T);
? ? cout<<endl;
? ? cout<<"后续遍历: ";
? ? back1(T);
? ? cout<<endl;
? ? return 0;
?}
