将1+2*3-4/5存入二叉树并求值用C语言

首先，我们需要定义二叉树的节点结构体：

struct TreeNode {
    char val;           // 存储操作符或数字
    struct TreeNode* left;
    struct TreeNode* right;
};

然后，我们定义一个函数 `buildTree(char* s)`，将表达式字符串 `s` 存入二叉树中：

struct TreeNode* buildTree(char* s) {
    struct TreeNode* root = NULL;
    struct TreeNode* cur = NULL;
    struct TreeNode* stack[100];
    int top = -1;
    int num = 0;        // 存储数字，用于处理多位数字的情况
    int flag = 1;       // 标记当前数字的正负性，默认为正数

    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] >= '0' && s[i] <= '9') {   // 处理数字
            num = num * 10 + s[i] - '0';
        } else {    // 处理操作符
            if (flag == -1) {
                num = -num;
                flag = 1;
            }
            if (cur == NULL) {  // 第一个节点
                cur = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                cur->val = num;
                root = cur;
            } else if (cur->left == NULL) { // 左子节点
                cur->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                cur->left->val = num;
                cur = cur->left;
            } else if (cur->right == NULL) {    // 右子节点
                cur->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                cur->right->val = num;
                cur = cur->right;
            } else {    // 如果当前节点已经有左右子节点，则需要回溯到最近的未满的父节点
                while (cur->right != NULL) {
                    cur = stack[top--];
                }
                cur->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                cur->right->val = num;
                cur = cur->right;
            }
            num = 0;    // 清零num，准备处理下一个数字
            if (s[i] == '-') {
                flag = -1;
            } else {
                cur->val = s[i];
            }
        }

        // 将当前节点入栈
        if (cur != NULL && (cur->val == '+' || cur->val == '-' || cur->val == '*' || cur->val == '/')) {
            stack[++top] = cur;
        }
    }

    if (flag == -1) {
        num = -num;
    }
    cur->val = num;     // 处理最后一个数字

    return root;
}

接着，我们定义一个函数 `evalTree(struct TreeNode* root)`，求二叉树表达式的值：

int evalTree(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {   // 叶子节点为数字
        return root->val;
    }
    int leftVal = evalTree(root->left);
    int rightVal = evalTree(root->right);
    switch (root->val) {
        case '+':
            return leftVal + rightVal;
        case '-':
            return leftVal - rightVal;
        case '*':
            return leftVal * rightVal;
        case '/':
            return leftVal / rightVal;
        default:
            return 0;
    }
}

最后，我们可以使用以下代码进行测试：

int main() {
    char s[] = "1+2*3-4/5";
    struct TreeNode* root = buildTree(s);
    int res = evalTree(root);
    printf("%s=%d\n", s, res);
    return 0;
}

输出结果为：

1+2*3-4/5=6