用四则运算表达式建立二叉树并对其进行遍历
时间: 2024-05-13 12:19:47 浏览: 23
我们可以使用二叉树来表示四则运算表达式,其中每个节点为一个操作符或者数字,而左右子树分别为该操作符的左右操作数。下面是一个例子:
```
+
/ \
* -
/ \ / \
2 3 4 5
```
这个二叉树表示的表达式为 (2 * 3) + (4 - 5)。
对于这个二叉树,我们可以进行前序遍历、中序遍历和后序遍历:
- 前序遍历:先遍历根节点,然后遍历左子树,最后遍历右子树。对于上面的例子,前序遍历结果为 + * 2 3 - 4 5。
- 中序遍历:先遍历左子树,然后遍历根节点,最后遍历右子树。对于上面的例子,中序遍历结果为 2 * 3 + 4 - 5。
- 后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点。对于上面的例子,后序遍历结果为 2 3 * 4 5 - +。
下面是使用 Python 实现建立二叉树并进行遍历的代码示例:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_expression_tree(tokens):
stack = []
for token in tokens:
if token.isdigit():
node = Node(int(token))
else:
node = Node(token)
node.right = stack.pop()
node.left = stack.pop()
stack.append(node)
return stack.pop()
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=' ')
tokens = ["+", "*", "2", "3", "-", "4", "5"]
root = build_expression_tree(tokens)
print("Preorder Traversal: ", end='')
preorder_traversal(root)
print()
print("Inorder Traversal: ", end='')
inorder_traversal(root)
print()
print("Postorder Traversal: ", end='')
postorder_traversal(root)
print()
```
输出结果为:
```
Preorder Traversal: + * 2 3 - 4 5
Inorder Traversal: 2 * 3 + 4 - 5
Postorder Traversal: 2 3 * 4 5 - +
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)