26、树与表达式：表达式树（二叉树表示算术表达式）、表达式树的构建与求值

表达式树，说白了就是用二叉树来装一个算术表达式。你想想看，我们平时写的 3 + 4 * 5 这种中缀表达式，计算机读起来其实挺费劲的。但要是把它变成一棵树，事情就简单多了。

我个人习惯把表达式树叫做“语法骨架”。它把操作数放在叶子节点，运算符放在内部节点。这样整个表达式的计算顺序，就变成了树的遍历顺序。嗯，这里要注意：树的形状直接决定了运算的优先级。

什么是表达式树

表达式树是一种特殊的二叉树。它的每个节点要么是操作数（叶子），要么是运算符（内部节点）。举个例子：

表达式：3 + 4 * 5

对应的表达式树：

      +
     / \
    3   *
       / \
      4   5

你看，+ 是根节点，左孩子是 3，右孩子是一棵子树 *。这棵子树里，* 的左孩子是 4，右孩子是 5。计算的时候，先算子树 4 * 5 = 20，再算 3 + 20 = 23。完全符合数学上的优先级。

表达式树的构建

构建表达式树，最常用的方法是利用后缀表达式（逆波兰式）。为什么？因为后缀表达式没有括号，也没有优先级问题，计算机处理起来特别顺手。

我记得有一次在项目中需要解析用户输入的数学公式，用户写的是 (a+b)*c 这种中缀形式。我当时的做法是：先把中缀转成后缀，再用后缀构建表达式树。两步走，稳得很。

构建步骤

1. 将中缀表达式转为后缀表达式（利用运算符栈）
2. 从左到右扫描后缀表达式
3. 遇到操作数：创建叶子节点，压入节点栈
4. 遇到运算符：从节点栈弹出两个节点作为右孩子和左孩子，创建运算符节点，再压回栈
5. 扫描结束后，栈顶就是表达式树的根节点

来看代码实现：

// 表达式树节点结构
typedef struct ExprNode {
    char data;                // 运算符或操作数
    struct ExprNode *left;    // 左孩子
    struct ExprNode *right;   // 右孩子
} ExprNode;

// 根据后缀表达式构建表达式树
ExprNode* buildExprTree(char postfix[]) {
    ExprNode *stack[100];
    int top = -1;
    
    for (int i = 0; postfix[i] != '\0'; i++) {
        char ch = postfix[i];
        
        // 跳过空格
        if (ch == ' ') continue;
        
        // 创建新节点
        ExprNode *node = (ExprNode*)malloc(sizeof(ExprNode));
        node->data = ch;
        node->left = NULL;
        node->right = NULL;
        
        if (ch >= '0' && ch <= '9') {
            // 操作数：直接入栈
            stack[++top] = node;
        } else {
            // 运算符：弹出两个操作数
            node->right = stack[top--];  // 注意：先弹出的是右孩子
            node->left = stack[top--];   // 后弹出的是左孩子
            stack[++top] = node;
        }
    }
    return stack[top];
}

表达式树的求值

表达式树建好了，求值就简单了。用后序遍历就行——先算左子树，再算右子树，最后算根节点。这正好对应了“先算子表达式，再算父表达式”的逻辑。

// 表达式树求值
int evaluate(ExprNode *root) {
    if (root == NULL) return 0;
    
    // 叶子节点：返回操作数的值
    if (root->left == NULL && root->right == NULL) {
        return root->data - '0';  // 字符转数字
    }
    
    // 递归计算左右子树
    int leftVal = evaluate(root->left);
    int rightVal = evaluate(root->right);
    
    // 根据运算符计算结果
    switch (root->data) {
        case '+': return leftVal + rightVal;
        case '-': return leftVal - rightVal;
        case '*': return leftVal * rightVal;
        case '/': return leftVal / rightVal;
        default: return 0;
    }
}

你看，代码非常简洁。递归的妙处就在这里——你不需要关心树有多深，递归会帮你一层一层算到底。

三种遍历与表达式形式

表达式树的三种遍历，正好对应了三种表达式写法：

遍历方式	遍历顺序	对应表达式	示例（3+4*5）
前序遍历	根 → 左 → 右	前缀表达式（波兰式）	+ 3 * 4 5
中序遍历	左 → 根 → 右	中缀表达式	3 + 4 * 5
后序遍历	左 → 右 → 根	后缀表达式（逆波兰式）	3 4 5 * +

有意思的是，中序遍历虽然最符合我们人类的阅读习惯，但它需要括号来标明优先级。而后缀表达式完全不需要括号，计算机处理起来最方便。所以实际工程中，我经常用后缀表达式作为中间表示。

表达式树的核心逻辑图

下面这张图展示了表达式树的完整处理流程：从输入中缀表达式开始，经过转换、构建、求值，最终得到结果。

实际应用中的注意事项

表达式树在实际项目中用得挺多的。比如计算器、公式解析器、编译器的语法分析阶段，都会用到类似的思想。

我曾经在做一个报表系统时，需要支持用户自定义计算公式。用户输入 SUM(A1:A10) * 1.2 + B1 这种表达式。我当时的做法就是：先解析成表达式树，然后对树进行优化（比如常量折叠），最后再求值。这样做的好处是，树结构方便做各种优化和变换。

表达式树还有一个妙用：它可以用来做表达式化简。比如 0 * x 可以直接化简为 0，x + 0 化简为 x。这些优化在编译器中非常常见。你想想看，如果编译器不做这些优化，生成的代码里就会有很多无用的计算指令，白白浪费CPU时间。

好了，表达式树的内容就讲到这里。它本质上就是用二叉树来组织算术表达式，构建靠后缀表达式，求值靠后序遍历。这三个知识点串起来，就是表达式树的完整故事。

---

公众号:蓝海资料掘金营，微信deep3321