#include
#include
typedef int ElemType;
typedef int Status;
typedef struct Snode
{
ElemType data; /*数据域*/
struct Snode next; /指针域*/
}Snode,*LinkStack;
/*二叉树的二叉链表储存*/
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode ,*BiTree;
Status CreateBiTree(BiTNode *T)
{
int ch;
scanf("%d",&ch);
if(ch==' ') 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,ElemType x) /将元素x插入到栈顶位置*/
{
LinkStack p;
p=(LinkStack)malloc(sizeof(Snode)); /*新节点生成*/
p->data=x; /*向新节点赋值*/
p->next=*S; /*向栈顶插入新结点*/
S=p;
return 1;
}
Status Pop_L(LinkStack *S,ElemType *temp_) /删除链栈的顶元素*/
{
LinkStack p;
ElemType temp;
if(*S==NULL) return 0; /*对于空栈则退出*/
temp=(*S)->data; /*暂存栈顶元素值，以便返回*/
p=*S; /*使栈顶指向下一结点*/
S=p->next;
free(p); /释放栈顶元素*/
temp_=temp;
return 1;
}
Status StackEmpty(LinkStack *S) /链栈的顶元素*/
{
LinkStack p;
if(*S==NULL) return 0; /*对于空栈则退出*/
else
return 1;
}
Status InOrderTraverse(BiTree T)
LinkStack S;
Init_StackL(&S);
BiTree p;
p=T;
while(p||StackEmpty(S)){
if(p){Push_L(&S,p);p=p->lchild;}
else{
Pop_L(&S,p);
p=p->rchild;
}
}
return 1;
}
