表达式树是节点含义固定的二叉树：叶子必为操作数（数字或变量），非叶子必为二元运算符，构造需满足语义约束；普通二叉树无此限制。
什么是表达式树，它和普通二叉树有什么区别
表达式树本质是二叉树，但节点含义固定：叶子节点一定是操作数（如 3、x），非叶子节点一定是运算符（如 +、*），且每个运算符节点必须有且仅有两个子节点（即使是一元运算符如负号，也常被建模为二元结构，右子为空或设为占位符）。这决定了它的构造不能随意——你不能把 + 当作叶子插入，也不能让 5 节点有两个子节点。
常见错误是直接套用通用二叉树模板，忽略语义约束，结果在遍历或求值时崩溃或逻辑错乱。
如何设计节点结构并支持基本运算符
节点类型需区分操作数与运算符，推荐用枚举 + 联合体（或 std::variant）避免虚函数开销。例如：
enum class NodeType { NUM, VAR, OP };
struct Node {
NodeType type;
union {
double num_val; // 仅 type == NUM 时有效
char var_name; // 仅 type == VAR 时有效（简化起见用单字符）
char op; // 仅 type == OP 时有效，如 '+'、'*'
};
Node* left = nullptr;
Node* right = nullptr;
};
关键点：
立即学习“C++免费学习笔记（深入）”；
-
op只能是'+'、'-'、'*'、'/'等有限集合，构造时必须校验 - 叶子节点（
NUM或VAR）的left和right必须为nullptr，否则后续求值逻辑会误判 - 若需支持变量代入，
VAR节点应在求值时查表（如传入std::map<char, double>）
如何从中缀表达式字符串构建树（不带括号的简化版）
完整中缀转表达式树需处理优先级和括号，复杂度高。实际开发中，更可行的是先转后缀（逆波兰），再用栈构建——这是稳定、易调试的路径。
假设输入是空格分隔的后缀表达式，如 "3 4 + 2 *"，构建逻辑如下：
std::stack<Node*> st;
for (const auto& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
Node* right = st.top(); st.pop();
Node* left = st.top(); st.pop();
Node* op_node = new Node{NodeType::OP, .op = token[0], left, right};
st.push(op_node);
} else {
Node* leaf = new Node{NodeType::NUM, .num_val = std::stod(token)};
st.push(leaf);
}
}
Node* root = st.top();
注意：
- 后缀表达式保证了运算符总在操作数之后，因此每次取两个栈顶元素作为左右子树，左操作数先弹出（因为栈是后进先出）
- 必须确保
tokens是合法后缀序列，否则栈空时调用top()会崩溃 - 若含变量（如
"x 2 +"），需额外判断 token 是否为字母，走NodeType::VAR分支
如何安全求值并避免除零或类型错误
递归求值函数必须检查节点类型，并对运算符做分支处理：
double eval(const Node* n, const std::map<char, double>& vars) {
if (!n) return 0.0;
switch (n->type) {
case NodeType::NUM: return n->num_val;
case NodeType::VAR: return vars.at(n->var_name); // 抛出 std::out_of_range 若未定义
case NodeType::OP:
double l = eval(n->left, vars);
double r = eval(n->right, vars);
switch (n->op) {
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/':
if (r == 0.0) throw std::runtime_error("division by zero");
return l / r;
default: throw std::runtime_error("unknown operator");
}
}
return 0.0;
}
容易忽略的细节：
-
vars.at()比vars[n->var_name]更安全——后者会静默插入默认值0.0，掩盖变量未定义的 bug - 所有浮点数比较（如
r == 0.0）应考虑精度，生产环境建议用std::abs(r) < 1e-9 - 内存泄漏风险高：示例中用
new分配，必须配套实现析构函数或改用std::unique_ptr<Node>
真正麻烦的从来不是写完树结构，而是确保每种节点类型在每个函数里都被覆盖，且边界条件（空指针、除零、未定义变量）都有明确行为。漏掉一个 case 或一次空指针检查，就可能让整个计算流程静默失败。
