CodeBrick 博客

Appearance

2017·41 表达式树转中缀：中序遍历+加括号，难点不在效率在细节 ​

本文属于「从暴力解到最优解」专题的第二组。第一组讲的是「怎么把暴力解优化掉」；第二组反过来，讲怎么认出一道题根本不用优化——直观写法就是满分解，力气要花在别的地方。

题目 ​

请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，两棵表达式树 *(+(a, b), *(c, -(_, d))) 和 +(*(a, b), -(_, -(c, d))) 作为算法输入时，输出的中缀表达式分别为 (a+b)*(c*(-d)) 和 (a*b)+(-(c-d))（单目运算符 - 取负，在树里以左子树为空、右子树为操作数表示）。二叉树结点定义如下：

c
typedef struct node {
    char data[10];   // 存储操作数或操作符
    struct node *left, *right;
} BTree;

要求：(1) 给出算法的基本设计思想；(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。总分 15 分。

先注意一件事：题面没有出现「尽可能高效」。按总纲的分类，这属于第二组——没有悬在头顶的最优性要求。但这不等于随便写，下面会看到力气该花在哪。

直观解法：中序遍历顺手加括号 ​

中缀表达式天生就是表达式树的中序遍历——左子树、根、右子树，正是我们平时手写算式的顺序。唯一要补的是括号：a+b*c 和 (a+b)*c 的中序遍历都是 a+b*c，树结构不同、输出却可能撞车，所以每一棵非叶子树都要用括号把自己「封装」起来，才能无歧义还原运算次序。最直接的想法是递归时带一个 depth 参数，进操作符结点时按 depth 是否为根决定加不加括号：

c
typedef struct node {
    char data[10];
    struct node *left, *right;
} BTree;

// depth: 当前结点在树中的递归深度，根为 0
static void traverse(BTree *node, int depth, char *buf) {
    if (node == NULL) return;

    int isLeaf = (node->left == NULL && node->right == NULL);
    if (isLeaf) {
        strcat(buf, node->data);                     // 操作数直接输出
        return;
    }

    if (depth > 0) strcat(buf, "(");                 // 非根的操作符，左侧加 (
    if (node->left != NULL) traverse(node->left, depth + 1, buf);
    strcat(buf, node->data);                         // 输出操作符
    traverse(node->right, depth + 1, buf);
    if (depth > 0) strcat(buf, ")");                 // 非根的操作符，右侧加 )
}

void toInfix(BTree *root, char *buf) {
    buf[0] = '\0';
    traverse(root, 0, buf);
}

复杂度：每个结点访问一次、strcat 单次追加是常数次字符操作，时间 O(n)；递归栈深等于树高，空间 O(h)。

为什么它就是满分解 ​

这道题没有「暴力 vs 最优」的分差，因为这个 O(n) 已经是下界，无法再降。用总纲的「找浪费三问」审一遍：

  1. 有没有重复扫描？ 没有。每个结点只在中序遍历经过它的那一刻被访问一次，操作符要不要加括号、操作数直接输出，都是当场判断当场写，不需要事后回头改。
  2. 有没有重算已知的东西？ 没有。深度作为递归参数顺路传递，不需要为某个结点重新计算它在树里的位置。
  3. 有没有放着性质不用？ 没有。题目没给额外的结构性质（比如运算符优先级表）要求你去利用——它反而明确要求「用括号反映计算次序」，也就是干脆放弃优先级判断，用括号把每层结构原样封起来，这本身就是最直接的做法。

更根本的一条：要把树的结构信息（谁先算、谁后算）完整还原成一条线性字符串，就必须至少访问树中每一个结点一次——这是 O(n) 的理论下界，任何正确算法都躲不开。既然碰到了下界，直观写法就是最优解。

这也是第二组题的共同特征：当输出必须完整反映输入结构时，"优化"这个动作根本不存在。认出这一点，就不会在考场上为不存在的分数去冒险写复杂代码。

真正的难点在括号与单目负号 ​

分不在优化上，那在哪？在这道题最容易失手的三处易错细节：

  • 只有非根结点才加括号：整个表达式的最外层不需要括号（题面给的两个样例都没有最外层括号）。用 depth > 0 判断——根的 depth 是 0，天然跳过加括号这一步；如果一上来就不分青红皂白地给根也加括号，整条表达式会被多包一层，与标准答案不符。
  • 单目负号 - 靠"左子树为空就跳过"自动处理，不需要额外分支。题面约定单目 - 的左子树为空、右子树是操作数。递归时 if (node->left != NULL) traverse(...) 这一行本身就会在左子树为空时什么都不做，紧接着输出 -、再递归右子树，自然拼出 (-X) 这样的形态——不需要专门写一个 if (isUnaryMinus) 分支去特殊处理它。
  • 括号必须成对，进出对称：加左括号发生在"进入非叶非根结点、递归左子树之前"，加右括号发生在"递归完右子树之后、即将返回之前"——一进一出严格配对。哪怕只是把 if (depth > 0) strcat(buf, ")") 这一行漏掉或错放了位置，输出的括号就会多一只或少一只，整条表达式作废。

三处任何一处出错，代码依然「跑得动」、能输出一串字符，但字符串本身是错的或有歧义的——这正是它们比空指针段错误更隐蔽、更容易在考场上被忽略的原因。

中序遍历拼中缀，看一遍 ​

用题面给的第一棵树 *(+(a, b), *(c, -(_, d)))，期望输出 (a+b)*(c*(-d))：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足 ​

第二组题的另一半功夫，是忍住不去做多余的事。这道题最容易出现的两个「过度设计」陷阱：

  • 给叶子也加括号。看到「非叶结点要加括号」，容易联想成「统一格式，干脆所有结点都加一层括号」，写出 (a)+(b) 这样的结果。但题面样例里操作数从来都是裸露输出的，叶子判定要放在"要不要加括号"之前直接短路返回，不参与括号逻辑。
  • 一上来就给根加括号。为了让代码"看起来更整齐"，把 if (depth > 0) 的判断去掉、所有层级一视同仁地加括号，结果整条表达式被多包一层最外层括号，与题面给的两个样例都对不上。根不加括号是判分点之一，不能省。

这两个陷阱的共同点是：都源于想让代码"看起来更一致、更保险"的冲动，但表达式树的括号规则本来就是不对称的——非根才需要、叶子完全不需要。把这份不对称原样写出来，比强行统一格式更接近满分。

下一步 ​

相关真题（1题）

2016Q42综合题8分
去刷题

正则 k 叉树性质：已知非叶结点数 m 求叶结点数、已知高度 h 求结点数范围

树与森林