#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;}                          

评论