考研笔记

板子：表达式树转中缀表达式（2017）

中序遍历，进入一个非根的运算符结点时输出 (，离开时输出 )。叶子是操作数，直接输出。

代码

typedef struct node {                        // 2017 原题给的结点定义
    char data[10];                           // 存操作数或运算符（字符串）
    struct node *left, *right;
} BTree;
 
void BtreeToExp(BTree *root, int deep) {     // deep：当前结点的深度，根为 1
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        printf("%s", root->data);            // 叶子是操作数：直接输出，不加括号
        return;
    }
    if (deep > 1) printf("(");               // 非根的运算符：给它的子表达式加一层括号
    BtreeToExp(root->left, deep + 1);        // 中序：左
    printf("%s", root->data);                //       根（运算符）
    BtreeToExp(root->right, deep + 1);       //       右
    if (deep > 1) printf(")");
}
 
void BtreeToE(BTree *root) {
    BtreeToExp(root, 1);                     // 整个表达式最外层不加括号
}

复杂度：每个结点访问一次，时间 ，空间 。

原题的两个例子：输出 (a+b)*(c*(-d)) 和 (a*b)+(-(c-d))。

关键边界

结点加不加括号为什么
叶子（操作数）不加单个操作数加括号是多余的，比如 (a)
根不加整个表达式外面不需要括号
其余运算符左右各加一个这个子表达式要作为整体参与上一层的运算
单目负号 -d照常处理左子树为空，递归直接返回，输出 (-d)

这种写法加的括号比「必要的括号」多，比如 (a*b) 的括号其实可以不要。但原题给的例子就是这么输出的，这样写能拿满分。

易错点

  • data 是字符串（char[10]），输出用 %s，不是 %c。
  • BTree 是结构体类型本身，不是指针，参数要写成 BTree *root。
  • 用 deep 判断是不是根，而不是比较 root == 原来的根，因为递归时拿不到原来的根。

链接

反向链接