题目

请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，下列两棵表达式树作为算法输入时，输出的中缀表达式分别为 (a+b)*(c*(-d)) 和 (a*b)+(-(c-d))。

表达式树 1（中缀：(a+b)*(c*(-d))）：

表达式树 2（中缀：(a*b)+(-(c-d))）：

注：单目运算符 -（取负）在树里以左子树为空 _、右子树为操作数表示。

二叉树结点的定义如下：

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

要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

解析

(1) 设计思想

答案：对表达式树做中序遍历——访问内部结点（操作符）时先输出 (、再递归左、再输出该操作符、再递归右、最后输出 )；叶结点（操作数）直接输出。但根结点外面不加括号。

为什么是"中序 + 加括号"？

中缀表达式天生就是表达式树的中序遍历。问题在于"括号"——比如 a+b*c 和 (a+b)*c 的中序遍历都是 a+b*c，但树结构不同。要无歧义还原算式，每个非叶子树都用一对括号"封装"自己就万无一失。

根不加括号的两个原因：

• 整个式子最外层无需括号（题面例子也没有）；
• 若递归时一上来就给根加括号，单目 - 会产生 (-d) 整体在最外层，看起来变扭。

单目 -（取负）的处理：题中约定单目 - 的左子树为空、右子树为操作数。算法天然支持——递归"左子树"时若是空指针就跳过、不递归；输出顺序变成 ( - X )，正合题意（如 (-d)）。

完整流程：

1. 递归参数：当前结点 node、当前递归深度 depth（根 depth=0，子树 depth>0）；
2. 若 node 为空：直接 return；
3. 若 node 是叶子：输出 node->data，return；
4. 否则（操作符）：
   • 若 depth > 0：输出 (；
   • 递归左子树（若不空）；
   • 输出 node->data（操作符本身）；
   • 递归右子树；
   • 若 depth > 0：输出 )。

(2) 代码实现

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);
}

用例 1 推导——*(+(a, b), *(c, -(_, d)))：

递归状态	输出累计
进根 *，depth=0，不加 (	``
递归左子树 +，depth=1，加 (	(
递归 a（叶）输出 a	(a
输出 +	(a+
递归 b（叶）输出 b	(a+b
+ 子树结束，加 )	(a+b)
输出根 *	(a+b)*
递归右子树 *，depth=1，加 (	(a+b)*(
递归 c（叶）	(a+b)*(c
输出 *	(a+b)*(c*
递归右孙 -（单目），depth=2，加 (	(a+b)*(c*(
左子空，跳过	(a+b)*(c*(
输出 -	(a+b)*(c*(-
递归 d（叶）	(a+b)*(c*(-d
- 子树结束，加 )	(a+b)*(c*(-d)
* 子树结束，加 )	(a+b)*(c*(-d))

✓ 与题面一致。

关键点说明：

• 括号成对出现的位置：进入非叶非根时加 (，离开非叶非根时加 )，绝对配对，不会少一只多一只。
• 单目 - 不需特殊代码：题中规定单目 - 的左子树为空，递归 left 时直接 node == NULL return；接着输出 - 再递归右就得到 (-X)，与"先 ( 再 op 再右子树 再 )"流水线一致。
• 复杂度：时间 O(n)（n 个结点各访问一次，strcat 单次累加是常数次字符）；空间 O(h)（递归栈深 = 树高）。