先序遍历表达式二叉树得到表达式的前缀表示的代码
时间: 2024-11-30 08:17:48 浏览: 26
先序遍历表达式二叉树(Preorder Traversal)的步骤通常是根节点 -> 左子树 -> 右子树,对于二叉树中表示的数学表达式来说,这意味着会首先输出操作符,然后是它的两个操作数。这里是一个简单的Python示例,假设我们有一个自定义的`Node`类用于表示二叉树节点:
```python
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def prefix_traversal(node):
if node is not None:
# 输出当前节点的值(通常操作符)
print(node.value, end="")
# 递归遍历左子树
prefix_traversal(node.left)
# 递归遍历右子树
prefix_traversal(node.right)
# 示例:假设二叉树代表表达式 (A + B) * C
root = Node('*')
a = Node('A')
b = Node('B')
c = Node('C')
# 将 A、B 分别链接到 root 的左右子节点
root.left = a
root.right = b
# 开始先序遍历
prefix_traversal(root)
```
运行这个程序会输出`( * A B C )`这样的前缀表示。
阅读全文