EC04-计算二叉树表达式的运算结果¶

表达式 \((a - (b + c)) \times (d / e)\) 存储在二叉树中，其中叶结点为操作数 \(a, b, c, d, e\)，非叶结点为运算符。要求对二叉树进行后序遍历求值，完成四则运算并输出结果。

代码实现¶

C
// 函数 func：计算二叉树表达式的运算结果
// 参数：p - 表达式二叉树的根节点指针
// 返回值：表达式的计算结果
int func(BiTree p) {
    // 递归终止条件1：如果当前节点为空，返回0
    if (p == NULL) {
        return 0;
    }

    // 递归终止条件2：如果当前节点是叶子节点（操作数）
    if (!p->lchild && !p->rchild) {
        // 将字符型数字转换为整型数值
        return p->data - '0';
    }

    // 递归处理：当前节点是运算符节点
    if (p->lchild && p->rchild) {
        // 递归计算左子树的值
        int A = func(p->lchild);
        // 递归计算右子树的值
        int B = func(p->rchild);

        // 根据当前节点的运算符进行相应运算
        if (p->data == '+') {
            return A + B; // 加法运算
        } else if (p->data == '-') {
            return A - B; // 减法运算
        } else if (p->data == '*') {
            return A * B; // 乘法运算
        } else if (p->data == '/') {
            return A / B; // 除法运算
        }
    }

    // 默认返回值（理论上不会执行到这里）
    return 0;
}

代码逻辑解析¶

1. 表达式树的结构¶

叶子节点：存储操作数（数字字符）
内部节点：存储运算符（+、-、*、/）
树的遍历顺序：后序遍历（左子树 → 右子树 → 根节点）

2. 递归处理策略¶

基本情况：
空节点：返回 0
叶子节点：将字符转换为数字返回
递归情况：
内部节点：递归计算左右子树，然后进行运算

3. 字符到数字的转换¶

C
// ASCII 码转换：'0'=48, '1'=49, ..., '9'=57
p->data - '0' // 将字符 '0'~'9' 转换为整数 0~9

4. 运算逻辑¶

按照后序遍历的顺序，先计算子表达式的值，再进行当前运算符的运算。

表达式树示例¶

对于表达式 (a-(b+c))*(d/e)，对应的二叉树结构为：

Text Only
1 2 3 4 5 6 7	`* / \ - / / \ / \ a + d e / \ b c`

计算过程（后序遍历）： 1. 访问 a：返回 a 的值 2. 访问 b：返回 b 的值 3. 访问 c：返回 c 的值 4. 计算 b+c：返回 (b+c) 的值 5. 计算 a-(b+c)：返回 a-(b+c) 的值 6. 访问 d：返回 d 的值 7. 访问 e：返回 e 的值 8. 计算 d/e：返回 d/e 的值 9. 计算 [a-(b+c)] * [d/e]：返回最终结果

时间复杂度分析¶

1. 节点访问次数¶

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

2. 每次操作复杂度¶

空节点检查：O(1)
叶子节点判断：O(1)
字符转数字：O(1)
基本运算：O(1)

3. 递归调用开销¶

每个节点最多进行一次递归调用（左右子树各一次）

4. 总体时间复杂度¶

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

空间复杂度分析¶

1. 额外空间使用¶

没有使用额外的数据结构
只使用了常量级别的局部变量（A, B）

2. 递归调用栈空间¶

递归深度取决于二叉树的高度
对于表达式树，高度通常为 O(log n)
最坏情况下（退化为链表）为 O(n)

3. 总体空间复杂度¶

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

较难理解部分的说明¶

1. 为什么是后序遍历？¶

表达式树的计算必须遵循后序遍历的顺序： - 先计算操作数的值 - 再进行运算符的运算 - 这与后缀表达式的计算方式一致

C
// 后序遍历的模板
void postOrder(BiTree p) {
    if (p != NULL) {
        postOrder(p->lchild);  // 左子树
        postOrder(p->rchild);  // 右子树
        visit(p);              // 访问根节点（在此处进行计算）
    }
}

2. 字符转数字的原理¶

C
// ASCII 码表中数字字符的编码
'0' = 48, '1' = 49, '2' = 50, ..., '9' = 57

// 转换示例
'5' - '0' = 53 - 48 = 5
'0' - '0' = 48 - 48 = 0

3. 图解计算过程¶

假设表达式为 (3-(1+2))*(6/2)，对应数值：

Text Only
1 2 3 4 5 6 7	`* // 运算：1 * 3 = 3 / \ - / // 左子树：3-3=0，右子树：6/2=3 / \ / \ 3 + 6 2 // 1+2=3 / \ 1 2`

计算顺序：

Text Only
1 2 3 4 5 6 7 8 9	`func(1) = 1 func(2) = 2 func(+) = 1 + 2 = 3 func(3) = 3 func(-) = 3 - 3 = 0 func(6) = 6 func(2) = 2 func(/) = 6 / 2 = 3 func() = 0 3 = 0`

延伸知识点¶

1. 改进版本 - 支持多位数¶

C
// 支持多位数的版本
int funcEnhanced(BiTree p) {
    if (p == NULL) return 0;

    if (!p->lchild && !p->rchild) {
        // 假设节点存储的是完整的数字字符串
        return atoi(p->data); // 使用 atoi 函数转换字符串为整数
    }

    if (p->lchild && p->rchild) {
        int A = funcEnhanced(p->lchild);
        int B = funcEnhanced(p->rchild);

        switch (p->data) {
            case '+': return A + B;
            case '-': return A - B;
            case '*': return A * B;
            case '/': 
                if (B == 0) {
                    printf("除零错误\n");
                    return 0;
                }
                return A / B;
            default: return 0;
        }
    }
    return 0;
}

2. 非递归版本 - 使用栈¶

C
int funcIterative(BiTree root) {
    if (root == NULL) return 0;

    Stack* stack = createStack();
    // 后序遍历的非递归实现
    // ... (实现略)

    return result;
}

3. 表达式树的构建¶

C
// 从中缀表达式构建表达式树
BiTree buildExpressionTree(char* expression) {
    // 使用两个栈：操作数栈和运算符栈
    // ... (实现略)
    return root;
}

4. 错误处理增强版¶

C
int funcWithErrorHandling(BiTree p, int* error) {
    if (p == NULL) return 0;

    if (!p->lchild && !p->rchild) {
        if (p->data >= '0' && p->data <= '9') {
            return p->data - '0';
        } else {
            *error = 1; // 非法操作数
            return 0;
        }
    }

    if (p->lchild && p->rchild) {
        int A = funcWithErrorHandling(p->lchild, error);
        if (*error) return 0;

        int B = funcWithErrorHandling(p->rchild, error);
        if (*error) return 0;

        switch (p->data) {
            case '+': return A + B;
            case '-': return A - B;
            case '*': return A * B;
            case '/': 
                if (B == 0) {
                    *error = 2; // 除零错误
                    return 0;
                }
                return A / B;
            default:
                *error = 3; // 非法运算符
                return 0;
        }
    }
    return 0;
}

5. 相关算法问题¶

表达式求值：中缀、前缀、后缀表达式的相互转换和计算
语法分析：编译器中的语法树构建和求值
计算器实现：科学计算器的表达式解析

6. 实际应用场景¶

编译器设计：语法分析和代码生成
计算器程序：数学表达式计算
数据库查询：SQL 表达式求值
科学计算：复杂数学公式的计算

这个算法体现了树的后序遍历和分治思想的经典应用，是数据结构与算法中的重要问题。