中缀表达式构建二叉树

### 使用中缀表达式构造二叉树 #### 构造方法概述 为了将中缀表达式转换成二叉树，可以采用递归下降解析法。该方法通过识别操作数和运算符来逐步建立二叉树节点。对于每一个遇到的操作符，创建一个新的内部节点作为当前子树的根；而对于操作数，则直接将其设为叶节点。 #### 实现细节 具体来说，当处理一个完整的算术表达式时： - 首先定位最内层的一对匹配括号内的表达式； - 如果不存在这样的括号，则寻找优先级最低的运算符（即最先计算的那个），以此为中心划分左右两部分； - 对于找到的关键运算符，新建一个非终端节点表示它，并继续对其两侧的部分重复上述过程直到整个字符串被完全解析完毕[^2]。 #### Python代码示例 下面是一个简单的Python函数用于展示这一过程: ```python class Node: def __init__(self, value): self.left = None self.right = None self.value = value def build_expression_tree(expression): precedence = {'+':1,'-':1,'*':2,'/':2} def parse_factor(): global index if expression[index].isdigit() or (index < len(expression)-1 and expression[index]=='-' and expression[index+1].isdigit()): start = index while index < len(expression) and expression[index].isdigit(): index += 1 node = Node(int(expression[start:index])) return node elif expression[index] == '(': index += 1 subtree_root = parse_expression() if expression[index] != ')': raise Exception("Mismatched parentheses") index += 1 return subtree_root def parse_term(): result_node = parse_factor() while index < len(expression) and expression[index] in '*/': op_token = expression[index] index += 1 next_operand = parse_factor() new_op_node = Node(op_token) new_op_node.left = result_node new_op_node.right = next_operand result_node = new_op_node return result_node def parse_expression(): nonlocal index result_node = parse_term() while index < len(expression) and expression[index] in '+-': op_token = expression[index] index += 1 next_operand = parse_term() new_op_node = Node(op_token) new_op_node.left = result_node new_op_node.right = next_operand result_node = new_op_node return result_node # Remove spaces from the input string. cleaned_expr = ''.join(expression.split()) index = 0 try: tree_root = parse_expression() if index != len(cleaned_expr): raise ValueError('Invalid Expression') return tree_root except IndexError as e: print(f"Parsing error at position {index}: ", str(e)) ``` 此程序定义了一个`Node`类用来存储二叉树中的各个元素，并实现了三个辅助函数——`parse_factor()`、`parse_term()` 和 `parse_expression()` 来按照运算符优先级顺序依次解析因子、项以及最终的整体表达式。