从c中的前缀表达式构建解析树

我正在尝试创建这样的二叉树： link

输入将由用户输入为前缀并作为字符串读取，然后放入二叉树中。

这是我到目前为止：

struct node{ char val; struct node *left; struct node *right; }; typedef struct node root; typedef root *tree; 

主要：

 void main(){ int i; tree tr; char* s; s=input(); //input function tr=create_empty_tree(); for(i=0;s[i]!='\0';i++){ tr=add_root(s[i],ab); } convert_infix(tr); } 

这是我几天来一直在努力的部分; 我似乎无法正确构建树。 这是我到目前为止：

 tree add_root(char val, tree tr){ if ( tr == NULL ){ tr= create_root(val); } else{ if(val=="*" || val=="+" || val=="-" || val=="/"){ tr->left= add_root(val, tr->left); } else{ if(tr->left == NULL){ tr->left= add_root(val, tr->left); } else{ tr->right= add_root(val, tr->right); } } } return tr; } 

我在网上看了这个，我知道我的function是错的，我试过这样做：

• 插入新节点，每次向左移动，直到插入操作数。

• 回溯到最后一个运算符，并将下一个节点放在右侧。

• 继续以相同的模式。

但我不知道如何回溯。 我已经好几天了，我疯了; 我只是编程的初学者所以请不要评判。

Answer 1

你有一个问题，一个字符串不是字符串char*所以你不能做一些事情，比如在char和char *之间进行比较char * …… ''用于char，当""用于c字符串即char *所以替换这个：

  if(val=="*" || val=="+" || val=="-" || val=="/") 

通过以下代码

  if(val=='*' || val=='+' || val=='-' || val=='/') 

Answer 2

简单示例（简化了错误检查）

 #include  #include  #include  #include  struct node{ char op; int val; struct node *left; struct node *right; }; typedef struct node Tree; char *get_token(char **p){ while(**p && isspace(**p)){//skip spaces ++*p; } char *ret = *p; if(!*ret){//empty return NULL; } while(**p && !isspace(**p)){ ++*p; } if(!**p){ **p = 0; ++*p; } return ret; } Tree *make_tree(char **p){ char *token = get_token(p); if(token){ Tree *tree = malloc(sizeof(*tree)); switch(*token){//token[1] == '\0' ?? case '*': case '/': case '+': case '-': tree->op = *token; tree->val = 0; tree->left = make_tree(p); tree->right = make_tree(p); break; default: tree->op = 'N'; tree->val = atoi(token); tree->left = tree->right = NULL; } return tree; } return NULL; } void release(Tree *tree){ if(tree){ release(tree->left); release(tree->right); free(tree); } } void print_infix(Tree *tree){ if(tree){ switch(tree->op){ case '*': case '/': case '+': case '-': putchar('(');print_infix(tree->left);printf(" %c ", tree->op);print_infix(tree->right);putchar(')'); break; case 'N': printf("%d", tree->val); break; default: fprintf(stderr, "\nerror!\n");//this should never be executed } } } int main(void){ char line[256]; while(fgets(line, sizeof(line), stdin)){ char *s = line; Tree *tree = make_tree(&s); print_infix(tree); putchar('\n'); release(tree); } return 0; } #if 0 * + 7 3 - 5 2 ((7 + 3) * (5 - 2)) * 3 + 1 2 (3 * (1 + 2)) / + 1 + 2 3 5 ((1 + (2 + 3)) / 5) ^Z #endif