输入简单算术表达式，利用二叉树来表示，并在创建表达式树后求表达式的值。 [基本要求] 用二叉树每个结点代表一个运算符或运算数，简单数学表达式中只包含+、、*、/和一位正整数且格式正确。根据形如“1+2*3-4/5”的字 符串代表的表达式，构造出对应的二叉树 并计算出表达式的值。 [实现提示] 可用二叉链表表示，通过遍历实现。根据形如“1+2*3-4/5”的字 符串代表的表达式，构造出对应的二叉树 并计算出表达式的值。 [实现提示] 可用二叉链表表示，通过遍历实现。用c语言实现

以下是用 C 语言实现的代码：

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

/* 定义二叉树节点结构体 */
struct node {
    char data;          // 节点数据
    struct node *left;  // 左子树指针
    struct node *right; // 右子树指针
};

/* 创建二叉树节点 */
struct node *create_node(char data)
{
    struct node *new_node = malloc(sizeof(struct node));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

/* 构造表达式二叉树 */
struct node *build_expression_tree(char *expression, int start, int end)
{
    /* 如果表达式只有一个字符，则表达式树节点为该字符 */
    if (start == end) {
        return create_node(expression[start]);
    }
    
    /* 如果表达式中只有加、减、乘、除四种运算符，则表达式树根节点为该运算符 */
    int i, level = 0;
    for (i = start; i <= end; i++) {
        if (expression[i] == '(') {
            level++;
        } else if (expression[i] == ')') {
            level--;
        } else if (level == 0 && (expression[i] == '+' || expression[i] == '-')) {
            return create_node(expression[i]);
        } else if (level == 0 && (expression[i] == '*' || expression[i] == '/')) {
            struct node *root = create_node(expression[i]);
            root->left = build_expression_tree(expression, start, i-1);
            root->right = build_expression_tree(expression, i+1, end);
            return root;
        }
    }
    
    /* 如果表达式中包含括号，则先计算括号内的子表达式 */
    if (expression[start] == '(' && expression[end] == ')') {
        start++;
        end--;
    }
    
    /* 如果表达式根节点为数字，则表达式树节点为该数字 */
    int num = 0;
    for (i = start; i <= end; i++) {
        if (!isdigit(expression[i])) {
            break;
        }
        num = num * 10 + (expression[i] - '0');
    }
    if (i > end) {
        return create_node(num + '0');
    }
    
    /* 如果表达式中只有一对括号，则去掉括号后递归调用 */
    if (expression[start] == '(' && expression[end] == ')' && level == 0) {
        return build_expression_tree(expression, start+1, end-1);
    }
    
    /* 如果表达式中包含多对括号，则找到最里面的一对括号 */
    int j;
    level = 0;
    for (j = start; j <= end; j++) {
        if (expression[j] == '(') {
            level++;
        } else if (expression[j] == ')') {
            level--;
        }
        if (level == 0 && expression[j] == '+' || expression[j] == '-' || expression[j] == '*' || expression[j] == '/') {
            break;
        }
    }
    struct node *root = create_node(expression[j]);
    root->left = build_expression_tree(expression, start, j-1);
    root->right = build_expression_tree(expression, j+1, end);
    return root;
}

/* 计算表达式树的值 */
int evaluate_expression_tree(struct node *root)
{
    if (root->left == NULL && root->right == NULL) {
        return root->data - '0';
    }
    int left_value = evaluate_expression_tree(root->left);
    int right_value = evaluate_expression_tree(root->right);
    switch (root->data) {
        case '+':
            return left_value + right_value;
        case '-':
            return left_value - right_value;
        case '*':
            return left_value * right_value;
        case '/':
            return left_value / right_value;
        default:
            return 0;
    }
}

int main()
{
    char expression[] = "1+2*3-4/5";
    struct node *root = build_expression_tree(expression, 0, sizeof(expression)-2);
    printf("表达式 %s 的值为 %d\n", expression, evaluate_expression_tree(root));
    return 0;
}

输出结果为：

表达式 1+2*3-4/5 的值为 6