include
#include
typedef int ElemType;
typedef int Status;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode ,*BiTree;
typedef BiTree pElemType;
typedef struct Snode
{
pElemType data;
struct Snode *next;
}Snode,*LinkStack;
Status CreateBiTree(BiTNode *T)
{
int ch;
scanf("%d",&ch);
if(ch==132) T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(0);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return 1;
}
void Init_StackL(LinkStack *S)
{
*S=NULL;
}
Status Push_L(LinkStack *S,pElemType x)
{
LinkStack p;
p=(LinkStack)malloc(sizeof(Snode));
p->data=x;
p->next=*S;
*S=p;
return 1;
}
Status Pop_L(LinkStack *S,pElemType *temp_)
{
LinkStack p;
pElemType temp;
if(*S==NULL) return 0;
temp=(*S)->data;
p=*S;
*S=p->next;
free(p);
*temp_=temp;
return 1;
}
Status StackEmpty(LinkStack *S)
{
if(*S==NULL) return 0;
else
return 1;
}
Status InOrderTraverse(BiTNode *T)
{
LinkStack S;
BiTNode *p;
p=T;
Init_StackL(&S);
while(p||StackEmpty(&S)){
if(p){Push_L(&S,p);p=p->lchild; printf("%d",p->data);
}
else{
Pop_L(&S,&p);
if(p->data) return 0;
p=p->rchild;
}
}
return 1;
}
void main()
{
BiTNode T;
CreateBiTree(&T);
InOrderTraverse(&T);
system("pause");
}