在Python中实现二叉树遍历的函数

在Python中，可以使用递归和迭代两种方法来实现二叉树的遍历。

1. 递归方法：

递归方法是最简单直观的实现方式，通过递归函数可以实现前序、中序和后序遍历。

# 定义二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 前序遍历
def preorderTraversal(root):
    result = []
    if root:
        result.append(root.val)  # 处理根节点
        result += preorderTraversal(root.left)  # 处理左子树
        result += preorderTraversal(root.right)  # 处理右子树
    return result

# 中序遍历
def inorderTraversal(root):
    result = []
    if root:
        result += inorderTraversal(root.left)  # 处理左子树
        result.append(root.val)  # 处理根节点
        result += inorderTraversal(root.right)  # 处理右子树
    return result

# 后序遍历
def postorderTraversal(root):
    result = []
    if root:
        result += postorderTraversal(root.left)  # 处理左子树
        result += postorderTraversal(root.right)  # 处理右子树
        result.append(root.val)  # 处理根节点
    return result

# 创建测试二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 测试遍历函数
print("前序遍历结果：", preorderTraversal(root))
print("中序遍历结果：", inorderTraversal(root))
print("后序遍历结果：", postorderTraversal(root))

程序结果输出为：

前序遍历结果： [1, 2, 4, 5, 3]
中序遍历结果： [4, 2, 5, 1, 3]
后序遍历结果： [4, 5, 2, 3, 1]

2. 迭代方法：

迭代方法使用栈数据结构来辅助遍历，根据不同的遍历顺序，压入栈的方式也不同。

# 前序遍历
def preorderTraversal(root):
    result = []
    stack = []
    while stack or root:
        if root:
            result.append(root.val)  # 处理根节点
            stack.append(root)  # 压入栈
            root = root.left  # 处理左子树
        else:
            node = stack.pop()  # 弹出栈
            root = node.right  # 处理右子树
    return result

# 中序遍历
def inorderTraversal(root):
    result = []
    stack = []
    while stack or root:
        if root:
            stack.append(root)  # 压入栈
            root = root.left  # 处理左子树
        else:
            node = stack.pop()  # 弹出栈
            result.append(node.val)  # 处理根节点
            root = node.right  # 处理右子树
    return result

# 后序遍历
def postorderTraversal(root):
    result = []
    stack = []
    prev = None  # 记录上一次访问的节点
    while stack or root:
        if root:
            stack.append(root)  # 压入栈
            root = root.left  # 处理左子树
        else:
            node = stack[-1]  # 获取栈顶元素
            if node.right and node.right != prev:  # 处理右子树
                root = node.right
            else:
                stack.pop()  # 弹出栈
                result.append(node.val)  # 处理根节点
                prev = node  # 更新上一次访问的节点
    return result

# 创建测试二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 测试遍历函数
print("前序遍历结果：", preorderTraversal(root))
print("中序遍历结果：", inorderTraversal(root))
print("后序遍历结果：", postorderTraversal(root))

程序结果输出与前面方法相同。

通过以上两种方法，可以在Python中实现二叉树的前序、中序和后序遍历。