基于二叉树的表达式求值算法

基于二叉树的表达式求值算法也被称为表达式树求值算法，其基本思想是利用二叉树的先序遍历和中序遍历构建表达式树，再利用后序遍历对表达式树进行求值。具体步骤如下：

1. 将中缀表达式转换为后缀表达式。

2. 构建表达式树：

a. 从后缀表达式中取出第一个元素，创建一个新节点并将该元素作为节点的值。

b. 如果该元素是操作符，则从栈中弹出两个元素作为该节点的左右儿子。

c. 将该节点压入栈中。

d. 重复步骤 a-c 直到后缀表达式结束。

e. 最终栈中只剩下一个元素，即为根节点。

3. 对表达式树进行后序遍历，同时利用一个栈保存中间结果：

a. 如果当前节点是操作符，则从栈中弹出两个元素并进行相应的运算，将结果压入栈中。

b. 如果当前节点是操作数，则将其压入栈中。

c. 重复步骤 a-b 直到遍历结束。

4. 最终栈中只剩下一个元素，即为表达式的值。

代码实现：

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def build_expression_tree(postfix):
    stack = []
    for token in postfix:
        if token.isdigit():
            node = TreeNode(int(token))
            stack.append(node)
        else:
            right = stack.pop()
            left = stack.pop()
            node = TreeNode(token)
            node.left = left
            node.right = right
            stack.append(node)
    return stack.pop()

def evaluate_expression_tree(root):
    stack = []
    def dfs(node):
        if node:
            dfs(node.left)
            dfs(node.right)
            if node.val.isdigit():
                stack.append(int(node.val))
            else:
                right = stack.pop()
                left = stack.pop()
                if node.val == '+':
                    stack.append(left + right)
                elif node.val == '-':
                    stack.append(left - right)
                elif node.val == '*':
                    stack.append(left * right)
                elif node.val == '/':
                    stack.append(left / right)
    dfs(root)
    return stack.pop()

这里假设后缀表达式已经转换好了，输入为一个字符串列表。build_expression_tree 函数将后缀表达式转换为表达式树，并返回根节点；evaluate_expression_tree 函数对表达式树进行后序遍历求值，并返回结果。