编写递归实现二叉树的中序、先序和后序遍历算法。函数名分别为inorder,preorder,postorder
时间: 2023-07-21 09:03:44 浏览: 81
以下是Python代码实现:
```python
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 递归实现中序遍历
def inorder(root):
if not root:
return []
res = []
res += inorder(root.left)
res.append(root.val)
res += inorder(root.right)
return res
# 递归实现先序遍历
def preorder(root):
if not root:
return []
res = []
res.append(root.val)
res += preorder(root.left)
res += preorder(root.right)
return res
# 递归实现后序遍历
def postorder(root):
if not root:
return []
res = []
res += postorder(root.left)
res += postorder(root.right)
res.append(root.val)
return res
```
其中,二叉树的节点类包含节点值(val)、左子树(left)和右子树(right)三个属性。每个遍历函数都是递归实现,如果当前节点为空,则返回空列表;否则,先递归遍历左子树,再将当前节点加入结果列表,最后递归遍历右子树。
测试代码:
```python
# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 测试中序遍历
print(inorder(root))
# [4, 2, 5, 1, 3]
# 测试先序遍历
print(preorder(root))
# [1, 2, 4, 5, 3]
# 测试后序遍历
print(postorder(root))
# [4, 5, 2, 3, 1]
```
阅读全文