c语言二叉树的表达式求值算法

二叉树表达式求值算法可以分为两个步骤：

1. 将中缀表达式转换为二叉树

2. 对二叉树进行后序遍历，计算表达式的值

下面是具体的代码实现：

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

typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef struct Stack {
    int top;
    int capacity;
    TreeNode **array;
} Stack;

TreeNode *createNode(char data) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Stack *createStack(int capacity) {
    Stack *newStack = (Stack *)malloc(sizeof(Stack));
    newStack->top = -1;
    newStack->capacity = capacity;
    newStack->array = (TreeNode **)malloc(capacity * sizeof(TreeNode *));
    return newStack;
}

void push(Stack *stack, TreeNode *node) {
    if (stack->top == stack->capacity - 1) {
        printf("Stack overflow!\n");
        return;
    }
    stack->array[++stack->top] = node;
}

TreeNode *pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack underflow!\n");
        return NULL;
    }
    return stack->array[stack->top--];
}

int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int getPriority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

TreeNode *buildTree(char *expression) {
    Stack *stack = createStack(strlen(expression));
    TreeNode *root = NULL;
    int i;

    for (i = 0; expression[i] != '\0'; i++) {
        if (isdigit(expression[i])) {
            TreeNode *newNode = createNode(expression[i]);
            push(stack, newNode);
        } else if (isOperator(expression[i])) {
            TreeNode *newNode = createNode(expression[i]);
            newNode->right = pop(stack);
            newNode->left = pop(stack);
            push(stack, newNode);
        }
    }

    root = pop(stack);
    free(stack);
    return root;
}

int evaluate(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return root->data - '0';
    }
    int leftValue = evaluate(root->left);
    int rightValue = evaluate(root->right);
    switch (root->data) {
        case '+':
            return leftValue + rightValue;
        case '-':
            return leftValue - rightValue;
        case '*':
            return leftValue * rightValue;
        case '/':
            return leftValue / rightValue;
        default:
            return 0;
    }
}

int main() {
    char expression[] = "52+3*";
    TreeNode *root = buildTree(expression);
    printf("The value of the expression is: %d\n", evaluate(root));
    return 0;
}

在上面的代码中，我们使用了一个栈来辅助进行中缀表达式的转换和后序遍历计算。在转换中缀表达式为二叉树时，如果遇到数字，我们就创建一个节点，并将其入栈；如果遇到运算符，我们就从栈中弹出两个节点，将运算符作为根节点，左右子树分别为弹出的两个节点，然后将根节点入栈。在计算表达式的值时，我们对二叉树进行后序遍历，并根据节点的类型进行不同的操作：如果是数字节点，就返回其对应的值；如果是运算符节点，就计算其左右子树的值，并根据运算符进行相应的计算。最后得到的结果就是表达式的值。

需要注意的是，上面的代码只能处理不带括号的简单中缀表达式。如果表达式中含有括号，那么我们需要先将中缀表达式转换为后缀表达式，然后再进行二叉树的构建和计算。