表达式树是什么？如何用二叉树表示和计算算术表达式？

简化版

表达式树用叶子节点表示操作数，用内部节点表示运算符。对表达式树做后序遍历可以得到后缀表达式；递归计算时先算左右子树，再用当前运算符合并结果。

详细版

表达式树把算术表达式结构化。例如 (3 + 4) * 5 可以表示为根节点 *，左子树是 +，右子树是 5。

特点：

叶子节点：数字、变量。
内部节点：+ - * / 等运算符。
中序遍历接近中缀表达式，但需要括号恢复优先级。
后序遍历得到后缀表达式。
求值天然递归：eval(node)=op(eval(left), eval(right))。

表达式树的价值是把字符串表达式变成结构，后续求值、优化和代码生成都更容易。

完整版教学

一、为什么表达式需要树结构

字符串表达式有优先级和括号。3 + 4 * 5 不能简单从左到右计算，因为乘法优先。树可以把优先级变成结构层次。

根节点是最后执行的运算。乘法在右子树里先完成，再和 3 做加法。树结构把“谁先算”表达得很清楚。

二、节点含义怎么定义

表达式树通常把操作数放叶子，把运算符放内部节点。因为二元运算符需要左右两个输入，正好对应左右子树。

叶子：3、x、42
内部节点：+、-、*、/

如果是一元运算，比如负号或函数调用，节点可以只有一个孩子，或者扩展为更一般的抽象语法树。面试里如果只谈算术二元表达式，二叉树就够用。

三、遍历和表达式形式的关系

表达式树的三种遍历对应三种表达式记法。

遍历	表达式形式	示例
前序	前缀表达式	`* + 3 4 5`
中序	中缀表达式	`(3 + 4) * 5`
后序	后缀表达式	`3 4 + 5 *`

中序输出时要注意括号，否则结构可能丢失。后序表达式不需要括号，适合用栈求值。

四、如何从后缀表达式构建表达式树

扫描后缀表达式。遇到操作数就建叶子入栈；遇到运算符就弹出两个节点作为右孩子和左孩子，再把新树根入栈。

输入：3 4 + 5 *
3 入栈
4 入栈
+ 弹 4、3，建 +(3,4)
5 入栈
* 弹 5、+，建 *(+,5)

注意弹出顺序：先弹出的是右操作数，后弹出的是左操作数。减法和除法尤其不能反。

五、递归求值为什么自然

表达式树的每个子树本身也是表达式。求值时先求左右子树，再处理当前运算符。

function evalTree(node) {
  if (node is number) return node.value;
  const left = evalTree(node.left);
  const right = evalTree(node.right);
  return apply(node.op, left, right);
}

对于 (3+4)*5，左子树结果是 7，右子树结果是 5，根节点乘法得到 35。

六、工程上表达式树有什么用

表达式树是 AST 的简化版本。编译器、解释器、规则引擎、SQL 优化器都会把文本解析成结构化树，然后做求值、优化或生成代码。

记忆钩子：表达式树的根是“最后执行的运算”，叶子是“最先拿到的值”。

七、常见误区与追问

误区：中序遍历一定能无歧义还原表达式。 如果不加括号，优先级结构可能丢失。
误区：后缀构树时先弹的是左孩子。 先弹出的是右操作数，后弹出的是左操作数。
误区：表达式树只能求值。 它还能做优化、变量替换、代码生成和规则解释。
追问：为什么后序对应后缀表达式？ 因为后序是左、右、根，运算符在两个操作数之后。
追问：一元运算怎么办？ 可以让节点只有一个孩子，或扩展为更通用的 AST 节点。

八、加强记忆

表达式树把表达式从字符串变成结构。内部节点是运算，叶子节点是值；后序遍历得到后缀表达式，递归求值先算子树再算根。只要记住“根是最后一步”，优先级和括号问题就都能顺下来。

简化版

详细版