创建一个递归函数，该函数从 C 中的前缀表达式（在 char 数组中）创建表达式树

Question

前缀表达式中的每个元素（操作数、运算符、括号）由白色分隔 space。这些是一些需要的功能。

void createExpTree ( BTNode ** root , char * prefix );
void printTree ( BTNode * node );
void printTreePostfix ( BTNode * node );

这是BTnode的结构

typedef struct _btnode{
int item;
struct _btnode *left;
struct _btnode *right;
} BTNode;

这是我的函数 createExpTree 的代码，但我不明白哪里出了问题

void createExpTree(BTNode** root,char* prefix)
{
int j, x;
char c;
char d[SIZE];

static int count=0;

c = prefix[count];
if (count == strlen(prefix)) {
    return;
}
if (c == ' ')
    count++;
c = prefix[count];
if (c=='*' || c=='/' || c=='+' || c=='-') {
    // if prefix exp is OPT
    // create children
    BTNode* nn = (BTNode*)malloc(sizeof(BTNode));
    nn->left = (BTNode*)malloc(sizeof(BTNode));
    nn->right = (BTNode*)malloc(sizeof(BTNode));
    nn->item = (int)c;
    nn->left = NULL;
    nn->right = NULL;
    *root = nn;
    count++;
    createExpTree(&((*root)->left), prefix);
    createExpTree(&((*root)->right), prefix);
}
else { //if prefix exp is OPERAND
    j=0;
    while (c!=' ') {
        d[j]=c;
        j++; count++;
        c = prefix[count];
    }
    d[j]='[=12=]';
    x = atoi(d);
    BTNode* nn = (BTNode*)malloc(sizeof(BTNode));
    nn->item = x;
    nn->left = NULL;
    nn->right = NULL;
    *root = nn;
    count++;
    return;
}

}

这些是我的 printTree 和 printTreePostfix 代码

void printTree(BTNode *node){
if (node == NULL) {
    return;
}
else {
    printTree(node->left);
    if(node->item >= 0 || node->item <= INT_MAX)
        printf("%d ",node->item);
    else
        printf("%c ",(char)(node->item));
    printTree(node->right);
}
}

void printTreePostfix(BTNode *node){
if (node == NULL) {
    return;
}
else {
    printTreePostfix(node->left);
    printTreePostfix(node->right);
    if(node->item >= 0 || node->item <= INT_MAX)
        printf("%d ",node->item);
    else
        printf("%c ",(char)(node->item));
}
}

这道题的输入类似于“+ 99 / + 88 77 - * 66 - 55 44 33”，整数大概是两位数。

我是否正确地创建了表达式树？我不断收到代码块中的分段错误

非常感谢任何帮助！！谢谢！！

**更新的代码：在我将前缀++固定为前缀[计数]后，似乎仍然存在分段错误，静态整数计数

Answer 1

使用 strtok() 的可能解决方案如下：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

typedef struct _btnode {
   int item;
   struct _btnode *left;
   struct _btnode *right;
} BTNode;

void createExpTree(BTNode **root, char *prefix) {
   *root = malloc(sizeof(BTNode));
   char *token = strtok(prefix, " ");    // set string prefix, delimited by spaces, to be tokenized
   if( isdigit(token[0]) ) {             // external nodes (= leaves) are operands
       (*root)->item = atoi(token);
       (*root)->left = NULL;
       (*root)->right = NULL;
   }
   else {                                // internal nodes are binary operators
       (*root)->item = token[0];
       createExpTree(&(*root)->left, NULL);  // continue using the same string prefix
       createExpTree(&(*root)->right, NULL); // continue using the same string prefix
   }
}

void printTree(BTNode *node){
   if( node == NULL ) return;
   if( node->left == NULL && node->right == NULL )  // external node
       printf("%d", node->item);
   else {                                           // internal node
       printf("(");
       printTree(node->left);
       printf(" %c ", (char)node->item);
       printTree(node->right);
       printf(")");
   }
}

void printTreePostfix(BTNode *node){
   if( node == NULL ) return;
   printTreePostfix(node->left);
   printTreePostfix(node->right);
   if(node->left ==NULL && node->right == NULL)  // external node
      printf("%d ",node->item);
   else                                          // internal node
      printf("%c ",(char)(node->item));
}

int main(void) {
   BTNode *root1;
   char prefix1[513] = "* + 1 2 - 3 4";
   createExpTree(&root1, prefix1);
   printf("Infix Tree:   ");
   printTree(root1);
   printf("\nPostfix Tree: ");
   printTreePostfix(root1);
   puts("");

   BTNode *root2;
   char prefix2[513] = "+ 99 / + 88 77 - * 66 - 55 44 33";
   createExpTree(&root2, prefix2);
   printf("Infix Tree:   ");
   printTree(root2);
   printf("\nPostfix Tree: ");
   printTreePostfix(root2);
   puts("");
   return 0;
}

输出：

Infix Tree:   ((1 + 2) * (3 - 4))
Postfix Tree: 1 2 + 3 4 - *
Infix Tree:   (99 + ((88 + 77) / ((66 * (55 - 44)) - 33)))
Postfix Tree: 99 88 77 + 66 55 44 - * 33 - / +

备注： 如果您不能在您的解决方案中使用预定义函数 strtok()，请尝试创建您自己的函数，其行为类似于 strtok()。

创建一个递归函数，该函数从 C 中的前缀表达式（在 char 数组中）创建表达式树

Creating a recursive function that creates a expression tree from a prefix expression (in a char array) in C

c

recursion

binary-tree

pointers

traversal