#include <iostream> #include <string> #include <memory> using namespace std; struct BitNode { string data; BitNode* lchild; BitNode* rchild; }; void CreateBiTree(BitNode*& t) { string ch; cin >> ch; if (ch[0] == '#') { t = NULL; } else { t = new BitNode; t->data = ch; CreateBiTree(t->lchild); CreateBiTree(t->rchild); } } int InOrderTraverse(BitNode* t) { string op = t->data; int a, b; if (op[0] < '0' || op[0] > '9') { cout << '('; a = InOrderTraverse(t->lchild); cout << t->data; b = InOrderTraverse(t->rchild); cout << ')'; if (op == "+") return a + b; else if (op == "-") return a - b; else if (op == "*") return a * b; else return a / b; } else { cout << t->data; int num = 0; for (int i = 0; i < op.size(); i++) { num = num * 10 + op[i] - '0'; } return num; } } int main() { BitNode* tree = new BitNode; string ch; int sum; while (cin >> ch) { tree->data = ch; CreateBiTree(tree->lchild); CreateBiTree(tree->rchild); sum = InOrderTraverse(tree); printf("=%d\n", sum); } system("pause"); return 0; }用c实现

这段代码是用 C++ 实现的，如果要用 C 语言实现的话，需要对代码进行修改。

首先，需要将头文件修改为：

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

然后，需要将结构体的定义修改为：

struct BitNode {
    char data[10];
    struct BitNode* lchild;
    struct BitNode* rchild;
};

接着，需要修改 CreateBiTree 函数：

void CreateBiTree(struct BitNode** t) {
    char ch[10];
    scanf("%s", ch);
    if (ch[0] == '#') {
        *t = NULL;
    } else {
        *t = (struct BitNode*)malloc(sizeof(struct BitNode));
        strcpy((*t)->data, ch);
        CreateBiTree(&(*t)->lchild);
        CreateBiTree(&(*t)->rchild);
    }
}

最后，需要修改 InOrderTraverse 函数：

int InOrderTraverse(struct BitNode* t) {
    char* op = t->data;
    int a, b;
    if (op[0] < '0' || op[0] > '9') {
        printf("(");
        a = InOrderTraverse(t->lchild);
        printf("%s", t->data);
        b = InOrderTraverse(t->rchild);
        printf(")");
        if (strcmp(op, "+") == 0)
            return a + b;
        else if (strcmp(op, "-") == 0)
            return a - b;
        else if (strcmp(op, "*") == 0)
            return a * b;
        else
            return a / b;
    } else {
        printf("%s", t->data);
        int num = 0;
        for (int i = 0; i < strlen(op); i++) {
            num = num * 10 + op[i] - '0';
        }
        return num;
    }
}

完整的 C 语言代码如下：