c语言编程实现利用二叉树求表达式的值

以下是基于二叉树的表达式求值的C语言实现：

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

struct TreeNode {
    char op;
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode *createNode(char op, int val) {
    struct TreeNode *newNode = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    newNode->op = op;
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct TreeNode *buildTree(char *expr) {
    int i = 0, num = 0, sign = 1;
    struct TreeNode *root = NULL, *cur = NULL;
    while (expr[i]) {
        if (isdigit(expr[i])) {
            num = num * 10 + (expr[i] - '0');
        } else if (expr[i] == '-') {
            sign = -1;
        } else if (expr[i] == '+' || expr[i] == '*') {
            if (root == NULL) {
                root = createNode(expr[i], 0);
                cur = root;
            } else {
                cur->right = createNode(expr[i], 0);
                cur = cur->right;
            }
            if (num != 0) {
                cur->left = createNode('n', num * sign);
                num = 0;
                sign = 1;
            }
        }
        i++;
    }
    if (num != 0) {
        cur->right = createNode('n', num * sign);
    }
    return 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->op) {
        case '+': return leftVal + rightVal;
        case '*': return leftVal * rightVal;
        default: return 0;
    }
}

int main() {
    char *expr = "3+4*5";
    struct TreeNode *root = buildTree(expr);
    printf("%d\n", evalTree(root)); // 输出 23
    return 0;
}

这里我们假设输入的表达式只包含数字、加号和乘号，并且没有括号。首先我们需要定义一个树节点结构体，包含一个操作符（如果是数字节点则为'n'），一个值和左右子节点。然后我们定义一个`createNode`函数用来创建节点。接着定义一个`buildTree`函数用来根据输入的表达式构建二叉树。我们使用一个指针`cur`来指向当前节点，遍历表达式字符串，如果遇到数字则累加到`num`中，如果遇到负号则将`sign`设为-1。如果遇到加号或乘号，则创建一个新节点并将`cur->right`指向它，然后将`cur`设为新节点。如果`num`不为0，则将`cur->left`设为数字节点，并重置`num`和`sign`。最后返回根节点指针。构建树的过程中我们没有考虑优先级，这是因为我们后面会通过递归计算解决这个问题。

我们定义一个`evalTree`函数用来计算表达式的值。如果根节点为空则返回0，如果根节点为数字节点则返回它的值。否则递归计算左子树和右子树的值，然后根据操作符计算并返回结果。

最后在`main`函数中调用`buildTree`和`evalTree`函数即可。