利用二叉树求解表达式的值
时间: 2024-01-03 19:05:20 浏览: 145
利用二叉树求解表达式的值可以通过后序遍历的方式实现。
具体步骤如下:
1. 从根节点开始,如果当前节点是数字节点,则将其值入栈。
2. 如果当前节点是操作符节点,则从栈中弹出两个数字,按照操作符进行计算,将结果入栈。
3. 遍历完整个二叉树后,栈中剩下的就是表达式的值。
下面是一个示例代码:
```python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def evaluate(root):
if root is None:
return 0
if root.left is None and root.right is None:
return int(root.value)
left_sum = evaluate(root.left)
right_sum = evaluate(root.right)
if root.value == '+':
return left_sum + right_sum
elif root.value == '-':
return left_sum - right_sum
elif root.value == '*':
return left_sum * right_sum
else:
return left_sum / right_sum
# 构造二叉树
root = Node('*')
root.left = Node('+')
root.left.left = Node('3')
root.left.right = Node('2')
root.right = Node('+')
root.right.left = Node('4')
root.right.right = Node('5')
# 输出结果
print(evaluate(root)) # 45
```
在这个例子中,我们构造了一个二叉树来表示表达式 `(3+2)*(4+5)`,然后使用 `evaluate` 函数计算了表达式的值,结果为 `45`。
阅读全文