http://blog.bc-cn.net/user15/82588/archives/2006/1864.shtml
http://blog.bc-cn.net/user15/82588/archives/2006/1864.shtml
#include"stdio.h"
#include"string.h"
typedef char datatype;
typedef struct node{ /*树的定义*/
datatype data;
struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;
typedef struct stack{ /*栈定义*/
bintree opst[100];
int tag[100];
int top;
}seqstack;
void push(seqstack *s,bintree t) /*进栈*/
{ s->opst[++s->top]=t;
}
bintree pop(seqstack *s)/*出栈*/
{ if(s->top!=-1)
{ s->top--;
return(s->opst[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 prebintree(bintree t) /*前序遍历的递归实现*/
{ if(t)
{ printf("%c",t->data);
prebintree(t->lchild);
prebintree(t->rchild);
}
}
void inbintree(bintree t)/*中序遍历的递归实现*/
{ if(t)
{ inbintree(t->lchild);
printf("%c",t->data);
inbintree(t->rchild);
}
}
void posbintree(bintree t) /*后序遍历的递归实现*/
{ if(t)
{ posbintree(t->lchild);
posbintree(t->rchild);
printf("%c",t->data);
}
}
void fprebintree(bintree t) /*前序遍历的非递归实现*/
{ seqstack s;
s.top=-1;
while(t||(s.top!=-1))
if(t)/*将当前根结点先打印后进栈*/
{ printf("%c",t->data);
s.opst[++s.top]=t;
t=t->lchild;
}
else /*当前左子树已经建好,将栈顶元素出栈建右子树*/
{ t=pop(&s);
t=t->rchild;
}
}
void finbintree(bintree t) /*中序遍历的非递归实现*/
{ seqstack s;
s.top=-1;
while(t||(s.top!=-1))
if(t)/*将当前根结点进栈*/
{
push(&s,t);
t=t->lchild;
}
else
{ t=pop(&s);
printf("%c",t->data);
t=t->rchild;
}
}
void fposbintree(bintree t)/*后序遍历的非递归实现*/
{ seqstack s;
s.top=-1;
while(t||(s.top!=-1))
{ if(t)
{
s.opst[++s.top]=t;
s.tag[s.top]=0;
t=t->lchild;
}
else
{ while((s.top!=-1)&&(s.tag[s.top]==1))
{ t=s.opst[s.top];
printf("%c",t->data);
s.top--;
}
if(s.top!=-1)
{ t=s.opst[s.top];
s.tag[s.top]=1;
t=t->rchild;
}
else t=NULL;
}
}
}