二叉树的遍历
时间: 2023-06-21 21:16:42 浏览: 24
二叉树的遍历有三种方式,分别为前序遍历、中序遍历和后序遍历。
1. 前序遍历(Pre-order Traversal):先访问根节点,然后递归地访问左子树和右子树。
伪代码实现:
```
def preorderTraversal(root):
if root is None:
return
print(root.val)
preorderTraversal(root.left)
preorderTraversal(root.right)
```
2. 中序遍历(In-order Traversal):先递归地访问左子树,然后访问根节点,最后递归地访问右子树。
伪代码实现:
```
def inorderTraversal(root):
if root is None:
return
inorderTraversal(root.left)
print(root.val)
inorderTraversal(root.right)
```
3. 后序遍历(Post-order Traversal):先递归地访问左子树和右子树,最后访问根节点。
伪代码实现:
```
def postorderTraversal(root):
if root is None:
return
postorderTraversal(root.left)
postorderTraversal(root.right)
print(root.val)
```
这三种遍历方式都可以用递归实现,也可以用栈来实现非递归遍历。其中,前序遍历和后序遍历的非递归实现较为容易,而中序遍历的非递归实现比较复杂。