设计一个使用二叉树实现数学表达式求值的程序，需要完成以下功能： （1）输入一个中缀表达式，建立二叉解析树，并对其进行先序、中序和后序的遍历； （2）利用递归的方法实现二叉解析树的求值功能；

好的，下面是一个使用二叉树实现数学表达式求值的 Python 程序： ```python class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def is_leaf(self): """ 判断当前节点是否为叶子节点 """ return self.left is None and self.right is None def __str__(self): return str(self.val) def build_expression_tree(expression): """ 构建表达式二叉树 """ operators = set(['+', '-', '*', '/', '(', ')']) precedence = {'+': 1, '-': 1, '*': 2, '/': 2} stack = [] root = None for token in expression: if token not in operators: node = TreeNode(int(token)) stack.append(node) else: if token == '(': stack.append(token) elif token == ')': while stack[-1] != '(': right = stack.pop() left = stack.pop() parent = stack.pop() parent.left = left parent.right = right stack.append(parent) stack.pop() else: while stack and stack[-1] != '(' and precedence[token] <= precedence.get(stack[-1], 0): right = stack.pop() left = stack.pop() parent = TreeNode(stack.pop()) parent.left = left parent.right = right stack.append(parent) stack.append(token) while stack: right = stack.pop() left = stack.pop() parent = TreeNode(stack.pop()) parent.left = left parent.right = right stack.append(parent) if stack: root = stack.pop() return root def evaluate_expression_tree(root): """ 递归求解表达式二叉树的值 """ if not root: return 0 if root.is_leaf(): return root.val left_val = evaluate_expression_tree(root.left) right_val = evaluate_expression_tree(root.right) if root.val == '+': return left_val + right_val elif root.val == '-': return left_val - right_val elif root.val == '*': return left_val * right_val else: return left_val / right_val def preorder_traversal(root): """ 先序遍历 """ if not root: return print(root.val, end=' ') preorder_traversal(root.left) preorder_traversal(root.right) def inorder_traversal(root): """ 中序遍历 """ if not root: return inorder_traversal(root.left) print(root.val, end=' ') inorder_traversal(root.right) def postorder_traversal(root): """ 后序遍历 """ if not root: return postorder_traversal(root.left) postorder_traversal(root.right) print(root.val, end=' ') if __name__ == '__main__': expression = '5 + ( 3 - 1 ) * 2 + 6 / 3 - 4' root = build_expression_tree(expression.split()) print('先序遍历：', end='') preorder_traversal(root) print('\n中序遍历：', end='') inorder_traversal(root) print('\n后序遍历：', end='') postorder_traversal(root) print('\n表达式求值结果：', evaluate_expression_tree(root)) ``` 这个程序使用二叉树来解析中缀表达式，并实现了先序、中序、后序遍历以及递归求解表达式二叉树的值的功能。程序首先定义了一个 TreeNode 类，表示二叉树的节点，其中包含节点的值、左子节点和右子节点，以及判断节点是否为叶子节点的方法。然后定义了一个 build_expression_tree 函数，用于构建表达式二叉树。这个函数接受一个中缀表达式的列表作为输入，返回构建好的表达式二叉树的根节点。函数使用栈来辅助构建二叉树，具体实现如下： - 对于每个表达式中的元素，如果是数字，则创建一个节点，并将其压入栈中； - 如果是左括号，则将其压入栈中； - 如果是右括号，则不断弹出栈顶元素，直到遇到左括号为止。每次弹出两个节点作为当前右子树和左子树，创建一个父节点，并将其作为栈顶元素的左子节点或右子节点，最后将父节点压入栈中； - 如果是运算符，则不断弹出栈顶元素，直到栈为空、遇到左括号或者栈顶元素的运算符优先级小于等于当前运算符优先级为止。每次弹出两个节点作为当前右子树和左子树，创建一个父节点，并将其作为栈顶元素的左子节点或右子节点，最后将父节点压入栈中； - 最后，如果栈中还有元素，将其依次弹出，构建成一棵二叉树。 构建好表达式二叉树之后，可以使用 evaluate_expression_tree 函数递归求解表达式二叉树的值。这个函数接受表达式二叉树的根节点作为输入，返回表达式的值。函数首先判断当前节点是否为叶子节点，如果是，则返回节点的值；否则，递归求解左子树和右子树的值，然后根据当前节点的运算符进行计算，并返回结果。 最后，程序定义了先序、中序、后序遍历的函数，用于验证构建的表达式二叉树是否正确，以及输出表达式求值结果。