用C語言寫中序同時轉前序中序與後序

Question

如題
input 一個中序式
可以 output 前序 中序 後序
想很久想不出來~"~
請高手幫忙 謝謝

要使用tree
不使用stack

有了樹之後要怎麼把中序轉成後序呢
可以再清楚一點嗎~"~

Answer 1

我想你應該是不知道怎麼用中序來建樹吧。
給你個函數，應該會有幫助。字串可以用類似"a+b*c"的格式傳進去試。參考資料可以看看常見資料演算的中序轉後序。
typedef struct node{
char data;
struct node* left;
struct node* right;
}Node;
int priority(char op) {
int p;
switch(op) {
case '+': case '-':
p = 1;
break;
case '*': case '/':
p = 2;
break;
default:
p = 0;
break;
}
return p;
}
Node* creat_tree(char* infix){
Node*left=NULL;
Node*right=NULL;
Node*temp=NULL;
int i;
for(i=0;infix[i]!='\0';i++)
{
switch(infix[i])
{
case '+':case '-':case '*':case '/':
temp=(Node*)malloc(sizeof(Node));
temp->data=infix[i];
temp->right=NULL;
if(left->right!=NULL&&priority(left->data) {
temp->left=left->right;
left->right=temp;
}
else
{
temp->left=left;
left=temp;
}
break;
default:
if(temp==NULL)
{
left=(Node*)malloc(sizeof(Node));
left->data=infix[i];
left->left=left->right=NULL;
}
else
{
right=(Node*)malloc(sizeof(Node));
right->left=right->right=NULL;
right->data=infix[i];
temp->right=right;
temp=right=NULL;
}
break;
}
}
return left;
}

2007-01-11 12:41:43 補充：
有了樹之後，要轉後序或前序就只是你走訪樹的方法不同而已。
後序是先拜訪左子樹跟右子樹在印出自己，前序則是先印出自己在去拜訪左子樹跟右子樹。至於怎麼拜訪左子樹跟右子樹教授應該有教。