前序、中序、后序遍历算法的实现
时间: 2023-11-03 10:06:04 浏览: 69
前序、中序、后序遍历是二叉树遍历算法中常用的三种方法,下面分别介绍它们的实现。
假设有如下二叉树:
```
1
/ \
2 3
/ \ \
4 5 6
```
1. 前序遍历
前序遍历的顺序是先访问根节点,再访问左子树,最后访问右子树。对于上面的二叉树,前序遍历的结果为:1 2 4 5 3 6。
前序遍历算法的实现如下:
```python
def preorder_traversal(root):
if root:
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
```
2. 中序遍历
中序遍历的顺序是先访问左子树,再访问根节点,最后访问右子树。对于上面的二叉树,中序遍历的结果为:4 2 5 1 3 6。
中序遍历算法的实现如下:
```python
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
```
3. 后序遍历
后序遍历的顺序是先访问左子树,再访问右子树,最后访问根节点。对于上面的二叉树,后序遍历的结果为:4 5 2 6 3 1。
后序遍历算法的实现如下:
```python
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=' ')
```