#include <iostream>
using namespace std;

//二叉树链式存储的头文件
typedef char datatype;         //结点属性值类型
typedef struct node            //二叉树结点的类型
{
 datatype data;
 struct node* lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;                   //指向二叉树根结点指针

//下面是些栈的操作 为非递归实现做准备

typedef struct stack            //栈结构定义
{
 bintree data[100];          //data 元素类型为   指针
 int tag[100];               //为栈中元素作的标记，用于后序遍历
 int top;                    //栈顶指针
}seqstack;

void push(seqstack* s,bintree t) //进栈
{
 s->data[++s->top]=t;
}

bintree pop(seqstack* s)            //出栈
{
 if(s->top!=-1)               //非递归遍历中，top初始值为-1
 {
  s->top--;
  return (s->data[s->top+1]);
 }
 else
  return NULL;
}

//按照前序遍历顺序建立一棵给定的二叉树

void createbintree(bintree* t)  
{
 char ch;
 if((ch=getchar())==' ')
  *t=NULL;
 else
 {
  *t=(bintnode*)malloc(sizeof(bintnode));   //产生二叉树根结点
  (*t)->data=ch;
  createbintree(&(*t)->lchild);             //递归实现左子树的创建
  createbintree(&(*t)->rchild);             //递归实现右子树的创建 
 }
}

//二叉树前序遍历 递归 实现

void preorder(bintree t)            //t 是指针变量，而不是 结点 结构体变量
{
 if(t)
 {
  cout<<t->data<<"   ";
  preorder(t->lchild);
  preorder(t->rchild);
 }
}

//二叉树前序遍历 非递归 实现

void preorder1(bintree t)
{
 seqstack s;
 s.top=-1;                            //top初始值为-1
 while((t)||(s.top!=-1))              // 当前 处理的 子树 不为空，或栈不为空，则循环
 {
  while(t)
  {
   cout<<t->data<<"  ";         //访问当前子树根结点
   s.top++;
   s.data[s.top]=t;             //当前子树根结点进栈(因为还要访问右子树)
   t=t->lchild;                 //访问此根结点 左孩子
  }                                //循环直到遍历完 当前子树  根结点，和其 左 孩子
  if(s.top>-1)
  {
   t=pop(&s);                   //当前子树跟结点出栈
   t=t->rchild;                 //访问其右孩子
  }
 }
}

//二叉树中序遍历递归算法

void inorder(bintree t)
{
 if(t)
 {
  inorder(t->lchild);
  cout<<t->data<<"  ";
  inorder(t->rchild);
 }
}

//二叉树中序遍历 非递归 算法

void inorder1(bintree t)
{
 seqstack s;
 s.top=-1;
 while((t!=NULL)||(s.top!=-1))
 {
  while(t)                  
  {
   push(&s,t);        
   t=t->lchild;       //子树根结点全部进栈
  }
  if(s.top!=-1)
  {
   t=pop(&s);
   cout<<t->data<<"  ";   //输出根结点，其实也就是左孩子或右孩子(没有孩子的根结点是它父亲的左或右孩子）
   t=t->rchild;           //进入右孩子访问
  }
 }
}

//后序递归遍历二叉树

void postorder(bintree t)
{
 if(t)
 {
  postorder(t->lchild);
  postorder(t->rchild);
  cout<<t->data<<"  ";
 }
}

//后序遍历 非递归 实现

void postorder1(bintree t)
{
 seqstack s;
 s.top=-1;
 while((t)||(s.top!=-1))
 {
  while(t)
  {
   s.top++;
   s.data[s.top]=t;              //子树根结点进栈
   s.tag[s.top]=0;        //设此根结点标志初始化为0，表示左右孩子都没访问，当访问完左子树 tag 变为1
   t=t->lchild;           //进入左子树访问。(左子树根结点全部进栈)
  }
  while((s.top>-1)&&(s.tag[s.top]==1))
  {
   t=s.data[s.top];     
   cout<<t->data<<"  "; //没有孩子的根结点，也就是它父亲的左孩子或右孩子
   s.top--;
  }
  if(s.top>-1)
  {
   t=s.data[s.top];
   s.tag[s.top]=1;          //进入右子树 前，标志tag变为1
   t=t->rchild;             //进入右子树
  }
  else
   t=NULL;
 }
}

int main()
{
 bintree tree;
 cout<<"输入根结点：";
 createbintree(&tree);
 
 
 cout<<"\n前序递归遍历二叉树:";
 preorder(tree);
 cout<<"\n前序非递归遍历二叉树:";
    preorder1(tree);
 cout<<"\n-----------------------------\n";
 
 cout<<"\n中序递归遍历二叉树:";
    inorder(tree);
    cout<<"\n中序非递归遍历二叉树:";
    inorder1(tree);
    cout<<"\n----------------------------\n";
 
 cout<<"\n后序递归遍历二叉树:";
    postorder(tree);
 cout<<"\n后序非递归遍历二叉树:";
    postorder1(tree);
 cout<<endl;
}

评论