EC03-将二叉树转化为等价的中缀表达式¶

代码实现¶

C
// 函数 func：将二叉树转化为等价的中缀表达式
// 参数：p - 二叉树的根节点指针，deep - 当前递归深度（用于括号控制）
void func(BiTree p, int *deep) {
    // 递归终止条件：如果当前节点为空，则返回
    if (p != NULL) {
        ++(*deep); // 增加当前深度

        // 如果当前节点既有左子树又有右子树，并且深度大于 1，输出左括号
        if ((p->lchild && p->rchild) && *deep > 1) {
            printf("(");
        }

        // 递归处理左子树
        func(p->lchild, deep);

        // 输出当前节点的值（假设节点存储的是字符类型的操作符或操作数）
        printf("%c", p->data);

        // 递归处理右子树
        func(p->rchild, deep);

        // 如果当前节点既有左子树又有右子树，并且深度大于 1，输出右括号
        if ((p->lchild && p->rchild) && *deep > 1) {
            printf(")");
        }

        --(*deep); // 回溯时减少当前深度
    }
}

代码逻辑解析¶

1. 中缀表达式的定义¶

中缀表达式是操作符位于操作数之间的表达式形式，例如 (a + b) * c。
在二叉树中，操作符通常作为内部节点，而操作数作为叶子节点。

2. 算法思路¶

采用中序遍历（左-根-右）的方式生成中缀表达式。
使用括号来确保操作优先级和表达式结构的正确性：
括号仅在当前节点有左右子树且深度大于 1 时添加。
深度大于 1 的条件是为了避免对根节点添加多余的括号。

3. 括号控制规则¶

C
if ((p->lchild && p->rchild) && *deep > 1) {
    printf("("); // 添加左括号
}
// ...
if ((p->lchild && p->rchild) && *deep > 1) {
    printf(")"); // 添加右括号
}

- 只有当节点同时具有左右子树且深度大于 1 时，才需要添加括号。 - 深度 *deep 的作用是区分根节点与子树节点，避免对整个表达式包裹多余括号。

4. 递归遍历模式¶

左子树：递归处理左子树，生成左操作数部分。
根节点：输出当前节点的数据（操作符或操作数）。
右子树：递归处理右子树，生成右操作数部分。
回溯：在回溯时减少深度计数器 *deep，以便正确处理括号。

时间复杂度分析¶

1. 遍历节点数¶

算法需要访问二叉树中的每个节点 exactly 一次。
设二叉树有 n 个节点，则需要进行 n 次节点处理。

2. 每次操作复杂度¶

每个节点的操作包括：
检查左右子树是否存在：O(1)
打印字符：O(1)
深度计数器更新：O(1)

3. 总体时间复杂度¶

O(n) - 线性时间复杂度

空间复杂度分析¶

1. 额外空间使用¶

只使用了常量级别的局部变量（deep 和节点检查相关的临时变量）。
没有使用额外的数据结构。

2. 递归调用栈空间¶

递归深度取决于二叉树的高度。
最好情况（完全二叉树）：O(log n)
最坏情况（退化为链表）：O(n)

3. 总体空间复杂度¶

O(h)，其中 h 是树的高度。在最坏情况下为 O(n)。

较难理解部分的说明¶

1. **为什么需要深度计数器 `*deep`？**¶

深度计数器的作用是： - 区分根节点与子树节点：只有在子树中（深度大于 1）才需要添加括号。 - 避免多余括号：根节点本身不需要括号包裹，因为它是整个表达式的主体。

示例解释¶

假设二叉树如下：

Text Only
1 2 3 4 5	`* / \ + c / \ a b`

对应的中缀表达式应为：(a + b) * c。

根节点 * 不需要括号。
子树节点 + 需要括号包裹其左右子树。

如果没有深度计数器，可能会生成错误的表达式：((a + b) * c)，导致多余的外层括号。

2. 图解说明¶

输入二叉树¶

Text Only
1 2 3 4 5	`* / \ + c / \ a b`

转换过程¶

Text Only

1. 访问根节点 * （深度 = 1，不打印括号）
2. 递归进入左子树 +
   - 深度 = 2，打印左括号 (
   - 递归进入左子树 a （叶子节点，打印 a）
   - 返回到 +，打印 +
   - 递归进入右子树 b （叶子节点，打印 b）
   - 深度 = 2，打印右括号 )
3. 返回到 *，打印 *
4. 递归进入右子树 c （叶子节点，打印 c）

最终输出：(a + b) * c

延伸知识点¶

1. 改进版本 - 返回字符串¶

如果需要将结果存储为字符串而不是直接输出，可以修改为返回字符串的形式：

C
char* treeToInfix(BiTree p, int *deep) {
    if (p == NULL) return "";

    char result[1000]; // 假设足够大的缓冲区
    char left[500], right[500];

    ++(*deep);

    // 递归处理左右子树
    strcpy(left, treeToInfix(p->lchild, deep));
    strcpy(right, treeToInfix(p->rchild, deep));

    // 构造中缀表达式
    if ((p->lchild && p->rchild) && *deep > 1) {
        sprintf(result, "(%s%c%s)", left, p->data, right);
    } else {
        sprintf(result, "%s%c%s", left, p->data, right);
    }

    --(*deep);
    return strdup(result);
}

2. 前缀与后缀表达式转换¶

前缀表达式（波兰表示法）¶

C
void preOrder(BiTree p) {
    if (p != NULL) {
        printf("%c", p->data); // 先输出根节点
        preOrder(p->lchild);  // 再处理左子树
        preOrder(p->rchild);  // 最后处理右子树
    }
}

后缀表达式（逆波兰表示法）¶

C
void postOrder(BiTree p) {
    if (p != NULL) {
        postOrder(p->lchild);  // 先处理左子树
        postOrder(p->rchild);  // 再处理右子树
        printf("%c", p->data); // 最后输出根节点
    }
}

3. 实际应用场景¶

编译器设计：将语法树转换为中缀、前缀或后缀表达式，便于后续计算。
表达式求值：利用表达式树进行数学运算。
数据结构教学：帮助学生理解递归遍历与表达式转换的关系。
公式编辑器：将用户输入的表达式可视化为树形结构。

4. 相关算法优化¶

C
// 提前判断是否需要括号
if (p->lchild || p->rchild) {
    // 根据子树结构决定是否添加括号
    bool need_parentheses = (p->lchild && p->rchild) || (*deep > 1);
    if (need_parentheses) printf("(");
    func(p->lchild, deep);
    printf("%c", p->data);
    func(p->rchild, deep);
    if (need_parentheses) printf(")");
}

该算法体现了递归遍历与括号控制的经典思想，是二叉树应用中的基础问题。