面试题：C语言中基于二叉树实现表达式求值

Question

给定一个用二叉树表示的算术表达式（每个叶节点为操作数，非叶节点为操作符，假设操作符只有+、-、*、/ ，操作数为整数），请用C语言编写一个函数来对该表达式进行求值。要求处理可能的除零错误，并考虑表达式树的结构遍历与计算顺序。

Answer 1

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

// 定义二叉树节点结构
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(char value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 计算表达式树的值
int evaluateExpressionTree(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    // 叶节点，直接返回操作数
    if (root->left == NULL && root->right == NULL) {
        return root->data - '0';
    }
    int leftValue = evaluateExpressionTree(root->left);
    int rightValue = evaluateExpressionTree(root->right);

    switch (root->data) {
        case '+':
            return leftValue + rightValue;
        case '-':
            return leftValue - rightValue;
        case '*':
            return leftValue * rightValue;
        case '/':
            if (rightValue == 0) {
                printf("除零错误\n");
                exit(1);
            }
            return leftValue / rightValue;
        default:
            return 0;
    }
}

int main() {
    // 构建表达式树 3 + 5 * 2
    TreeNode* root = createNode('+');
    root->left = createNode('3');
    TreeNode* mulNode = createNode('*');
    root->right = mulNode;
    mulNode->left = createNode('5');
    mulNode->right = createNode('2');

    int result = evaluateExpressionTree(root);
    printf("表达式的值为: %d\n", result);

    return 0;
}