根据输入的算术表达式构造对应的二叉树

Question

根据输入的算术表达式构造对应的二叉树，利用二叉树的非递归算法输出对应的前缀后缀（数据结构C语言）

Answer 1

typedef struct BtNode
{
char data;
struct BtNode *lchild;//左子树
struct BtNode *rchild;
};
typedef struct
{
struct BtNode *node;
char tag;
}StackNode;
BtNode * creat(char a[])
{
int i=0,k=0,top=-1;
BtNode *p,*t=NULL;
BtNode *st[maxsize];
char ch;
ch=a[i];
while(a[i]!='\0')
{
switch (ch)
{case '(':{
top++;st[top]=p;k=1;break;}
case ')':{
top--;break;}
case ',':{
k=2;break;}
default :{
p=(BtNode *)malloc(sizeof(BtNode));
p->data=ch;
p->lchild=NULL;p->rchild=NULL;
if(t==NULL) t=p;
else{
if(k==1)
{ st[top]->lchild=p;}
else if(k==2)
{ st[top]->rchild=p;}
}
}
}
i++;ch=a[i];

}
return t;
}
int preorder(BtNode * t)
{
int top=-1;
BtNode *st[maxsize],*p=t;
while(p!=NULL||top!=-1){
while(p!=NULL){
printf("%c",p->data);
top++;st[top]=p;
p=p->lchild;
}if(top==-1)
return 1;
else{
p=st[top];
top--;
}
p=p->rchild;
}
}
int inorder(BtNode *t)
{
BtNode *st[maxsize],*p=t;
int top=-1;
while(p!=NULL||top!=-1){
while(p!=NULL){
top++;st[top]=p;p=p->lchild;
}
if(top==-1) return 1;
else{
p=st[top];top--;
printf("%c",p->data);
p=p->rchild;
}
}
}
void postorder(BtNode *t)
{
int top=-1,a;
BtNode *p=t;
StackNode w,s[maxsize];
do{
while(p!=NULL){
w.node=p;w.tag='L';top++;s[top]=w;p=p->lchild;}
a=1;
while(a&&top!=-1){
w=s[top];top--;p=w.node;
switch(w.tag){
case 'L' :
w.tag='R';w.node=p;top++;s[top]=w;
a=0;p=p->rchild;
break;
case 'R':
printf("%c",p->data);

    }
    }
}while(top!=-1);

}