题18

题18

题目

【2017 统考真题】请设计一个算法, 将给定的表达式树 (二叉树) 转换为等价的中级表达式 (通过括号反映操作符的计算次序) 并输出。例如, 当下列两棵表达式树作为算法的输入时:

输出的等价中级表达式分别为 (a + b) * (c * (-d)) 和 (a * b) + (-(c - d)) 。二叉树结点定义如下:

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

要求:

1. 给出算法的基本设计思想。
2. 根据设计思想, 采用 C 或 C++语言描述算法, 关键之处给出注释。

分析

解

1. 算法的基本设计思想。

表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。

表达式树中分支结点所对应的子表达式的计算次序, 由该分支结点所处的位置决定。为得到正确的中缀表达式, 需要在生成遍历序列的同时, 在适当位置增加必要的括号。显然, 表达式的最外层（对应根结点）和操作数（对应叶结点）不需要添加括号。

2. 算法实现。

将二叉树的中序遍历递归算法稍加改造即可得本题的答案。除根结点和叶结点外, 遍历到其他结点时在遍历其左子树之前加上左括号, 遍历完右子树后加上右括号。

void BtreeToE(BTree *root) {
    BtreeToExp(root, 1); // 根的高度为 1
}
 
void BtreeToExp(BTree *root, int deep) {
    if (root == NULL) return; // 空结点返回
    else if (root->left == NULL && root->right == NULL) // 若为叶结点
        printf("%s", root->data); // 输出操作数, 不加括号
    else {
        if (deep > 1) printf("("); // 若有子表达式则加一层括号
        BtreeToExp(root->left, deep + 1);
        printf("%s", root->data); // 输出操作符
        BtreeToExp(root->right, deep + 1);
        if (deep > 1) printf(")"); // 若有子表达式则加一层括号
    }
}