什么是二叉运算树
二叉运算树（Binary Expression Tree），也称为二叉表达式树，是一种数据结构，用于求解数学表达式或算术表达式。它是一种二叉树，其中每个节点表示一个操作符或操作数，并且具有以下特点：
- 叶子节点（没有子节点）表示操作数，如整数或变量。
- 内部节点表示操作符，如加法、减法、乘法、除法等。
- 树的根节点表示整个表达式的最外层操作符。
- 每个内部节点的左子节点和右子节点分别表示操作符的操作数或子表达式。
二叉运算树使我们能够以树状结构的方式组织和表示数学表达式，可以轻松进行表达式求值。通过遍历这棵树，可以按照正确的操作符优先级和结合性计算表达式的值。
例如，对于表达式 "3 + 4 * 2"，可以构建如下的二叉运算树：
这个树的根节点是加法操作符，左子节点是操作数 3，右子节点是乘法操作符。乘法操作符的左子节点是操作数 4，右子节点是操作数 2。通过遍历这棵树，可以按照正确的顺序执行操作，计算表达式的值。
二叉运算树用于编译器、解释器和数学表达式求解中，它提供了一种有效的方式来表示和处理复杂的数学表达式。
Python代码示例
1 # 步骤1：定义操作数和操作符的优先级 2 operator_precedence = { 3 '+': 1, 4 '-': 1, 5 '*': 2, 6 '/': 2, 7 '^': 3 # 假设有指数运算 8 } 9 10 11 # 步骤2: 创建节点类 12 class TreeNode: 13 def __init__(self, value): 14 self.value = value 15 self.left = None 16 self.right = None 17 18 19 # 步骤3: 解析表达式并构建二叉运算树 20 def build_expression_tree(expression): 21 stack = [] 22 operator_stack = [] 23 tokens = expression.split() 24 25 for token in tokens: 26 if token == '(': 27 operator_stack.append(token) 28 elif token == ')': 29 while operator_stack and operator_stack[-1] != '(': 30 operator = operator_stack.pop() 31 right = stack.pop() 32 left = stack.pop() 33 node = TreeNode(operator) 34 node.left = left 35 node.right = right 36 stack.append(node) 37 operator_stack.pop() # 弹出左括号 38 elif token.isnumeric(): 39 node = TreeNode(token) 40 stack.append(node) 41 elif token in operator_precedence: 42 while (operator_stack and operator_stack[-1] != '(' and 43 operator_precedence[token] <= operator_precedence.get(operator_stack[-1], 0)): 44 operator = operator_stack.pop() 45 right = stack.pop() 46 left = stack.pop() 47 node = TreeNode(operator) 48 node.left = left 49 node.right = right 50 stack.append(node) 51 operator_stack.append(token) 52 53 while operator_stack: 54 operator = operator_stack.pop() 55 right = stack.pop() 56 left = stack.pop() 57 node = TreeNode(operator) 58 node.left = left 59 node.right = right 60 stack.append(node) 61 62 return stack[0] 63 64 65 # expression = "( 3 + 4 ) * 2 ^ ( 2 - 1 )" # 14 66 expression = "( 3 + 4 ) * 2 * 3" 67 root_tree = build_expression_tree(expression) 68 69 70 # 打印二叉运算树 71 def print_tree(node): 72 if node: 73 print(node.value) 74 print_tree(node.left) 75 print_tree(node.right) 76 77 78 print_tree(root_tree) 79 80 81 # 使用二叉运算树计算表达式 82 def evaluate_expression_tree(root): 83 if root is None: 84 return 0 85 86 if root.left is None and root.right is None: 87 return int(root.value) 88 89 left_result = evaluate_expression_tree(root.left) 90 right_result = evaluate_expression_tree(root.right) 91 92 # AttributeError: 'int' object has no attribute 'isnumeric' 93 # if root.value == '+' and left_result.isnumeric() and right_result.isnumeric(): 94 if root.value == '+' and isinstance(left_result, int) and isinstance(right_result, int): 95 return left_result + right_result 96 elif root.value == '-' and isinstance(left_result, int) and isinstance(right_result, int): 97 return left_result - right_result 98 elif root.value == '*' and isinstance(left_result, int) and isinstance(right_result, int): 99 return left_result * right_result 100 elif root.value == '/' and isinstance(left_result, int) and isinstance(right_result, int): 101 return left_result / right_result 102 elif root.value == '^' and isinstance(left_result, int) and isinstance(right_result, int): 103 return left_result ** right_result 104 105 106 print(evaluate_expression_tree(root_tree))
输出：
* * + 3 4 2 3 42