编写递归实现二叉树的中序、先序和后序遍历算法。函数名分别为 inorder, preorder, postorder.
时间: 2023-07-21 15:03:47 浏览: 77
二叉树的非递归先序中序后序(数据结构和算法分析)
以下是递归实现二叉树的中序、先序和后序遍历算法的 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 root is None:
return
inorder(root.left)
print(root.val)
inorder(root.right)
# 先序遍历
def preorder(root):
if root is None:
return
print(root.val)
preorder(root.left)
preorder(root.right)
# 后序遍历
def postorder(root):
if root is None:
return
postorder(root.left)
postorder(root.right)
print(root.val)
```
其中,二叉树结点类定义了三个属性:`val` 表示结点的值,`left` 表示左子结点,`right` 表示右子结点。三个遍历函数都采用递归实现。在中序遍历中,先遍历左子树,再输出当前结点的值,最后遍历右子树;在先序遍历中,先输出当前结点的值,再遍历左子树和右子树;在后序遍历中,先遍历左子树和右子树,最后输出当前结点的值。
阅读全文