Python二叉树遍历案例怎么写？

本文目录导读：

1. 基础版：实现二叉树节点和遍历方法
2. 测试案例
3. 实用版：带功能树的示例
4. 简洁版：直接可用的函数
5. 输出示例

我来给你几个Python二叉树遍历的完整案例。

基础版：实现二叉树节点和遍历方法

class TreeNode:
    """二叉树节点"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class BinaryTree:
    """二叉树类，包含各种遍历方法"""
    def __init__(self, root=None):
        self.root = root
    # ---------- 前序遍历 ----------
    # 1. 递归实现
    def preorder_recursive(self, node=None, result=None):
        """前序遍历（根-左-右）"""
        if result is None:
            result = []
        if node is None:
            return result
        result.append(node.val)  # 访问根节点
        self.preorder_recursive(node.left, result)  # 遍历左子树
        self.preorder_recursive(node.right, result)  # 遍历右子树
        return result
    # 2. 迭代实现
    def preorder_iterative(self):
        """前序遍历（迭代）"""
        if not self.root:
            return []
        result = []
        stack = [self.root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            # 先压右子树，再压左子树（因为栈是后进先出）
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result
    # ---------- 中序遍历 ----------
    # 1. 递归实现
    def inorder_recursive(self, node=None, result=None):
        """中序遍历（左-根-右）"""
        if result is None:
            result = []
        if node is None:
            return result
        self.inorder_recursive(node.left, result)  # 遍历左子树
        result.append(node.val)  # 访问根节点
        self.inorder_recursive(node.right, result)  # 遍历右子树
        return result
    # 2. 迭代实现
    def inorder_iterative(self):
        """中序遍历（迭代）"""
        result = []
        stack = []
        current = self.root
        while current or stack:
            # 一直向左走，把沿途节点入栈
            while current:
                stack.append(current)
                current = current.left
            # 弹出栈顶节点并访问
            current = stack.pop()
            result.append(current.val)
            # 转到右子树
            current = current.right
        return result
    # ---------- 后序遍历 ----------
    # 1. 递归实现
    def postorder_recursive(self, node=None, result=None):
        """后序遍历（左-右-根）"""
        if result is None:
            result = []
        if node is None:
            return result
        self.postorder_recursive(node.left, result)  # 遍历左子树
        self.postorder_recursive(node.right, result)  # 遍历右子树
        result.append(node.val)  # 访问根节点
        return result
    # 2. 迭代实现（使用两个栈）
    def postorder_iterative(self):
        """后序遍历（迭代）"""
        if not self.root:
            return []
        result = []
        stack1 = [self.root]
        stack2 = []
        while stack1:
            node = stack1.pop()
            stack2.append(node)
            if node.left:
                stack1.append(node.left)
            if node.right:
                stack1.append(node.right)
        while stack2:
            result.append(stack2.pop().val)
        return result
    # ---------- 层序遍历 ----------
    def level_order(self):
        """层序遍历（广度优先）"""
        if not self.root:
            return []
        result = []
        queue = [self.root]
        while queue:
            level_size = len(queue)
            level_nodes = []
            for _ in range(level_size):
                node = queue.pop(0)
                level_nodes.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level_nodes)
        return result

测试案例

def test_binary_tree():
    """测试二叉树遍历"""
    # 构建一棵二叉树：
    #       1
    #      / \
    #     2   3
    #    / \   \
    #   4   5   6
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)
    tree = BinaryTree(root)
    print("二叉树遍历测试")
    print("-" * 40)
    # 前序遍历
    print("前序遍历（递归）:", tree.preorder_recursive())
    print("前序遍历（迭代）:", tree.preorder_iterative())
    print()
    # 中序遍历
    print("中序遍历（递归）:", tree.inorder_recursive())
    print("中序遍历（迭代）:", tree.inorder_iterative())
    print()
    # 后序遍历
    print("后序遍历（递归）:", tree.postorder_recursive())
    print("后序遍历（迭代）:", tree.postorder_iterative())
    print()
    # 层序遍历
    print("层序遍历:", tree.level_order())
# 运行测试
test_binary_tree()

实用版：带功能树的示例

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
class TreeTraversal:
    """实用的二叉树遍历工具类"""
    @staticmethod
    def traverse_actions(root, action="print"):
        """
        执行遍历并应用操作
        action: "print" 打印值, "sum" 求和, "count" 计数
        """
        results = []
        def preorder_visit(node):
            if node:
                if action == "print":
                    results.append(node.val)
                elif action == "sum":
                    results.append(node.val)
                elif action == "count":
                    results.append(1)
                preorder_visit(node.left)
                preorder_visit(node.right)
        preorder_visit(root)
        if action == "sum":
            return sum(results)
        elif action == "count":
            return len(results)
        else:
            return results
    @staticmethod
    def find_max_depth(root):
        """查找二叉树的最大深度"""
        if not root:
            return 0
        left_depth = TreeTraversal.find_max_depth(root.left)
        right_depth = TreeTraversal.find_max_depth(root.right)
        return max(left_depth, right_depth) + 1
    @staticmethod
    def is_bst(root):
        """判断是否是二叉搜索树（中序遍历法）"""
        def inorder_check(node, prev):
            if not node:
                return True
            if not inorder_check(node.left, prev):
                return False
            if prev[0] is not None and node.val <= prev[0]:
                return False
            prev[0] = node.val
            return inorder_check(node.right, prev)
        return inorder_check(root, [None])
# 实用示例
def practical_example():
    """实际应用示例"""
    # 构建文件系统树
    #         /
    #       /   \
    #    docs   images
    #    /  \     /  \
    #  readme  src logo icon
    root = TreeNode("/")
    root.left = TreeNode("docs")
    root.right = TreeNode("images")
    root.left.left = TreeNode("readme.md")
    root.left.right = TreeNode("src")
    root.right.left = TreeNode("logo.png")
    root.right.right = TreeNode("icon.png")
    traversal = TreeTraversal()
    print("文件系统遍历:")
    print("所有文件:", traversal.traverse_actions(root, "print"))
    print("文件总数:", traversal.traverse_actions(root, "count"))
    print("最大深度:", traversal.find_max_depth(root))
    # 二叉搜索树判断
    bst_root = TreeNode(10)
    bst_root.left = TreeNode(5)
    bst_root.right = TreeNode(15)
    bst_root.left.left = TreeNode(3)
    bst_root.left.right = TreeNode(7)
    print("\n二叉搜索树判断:")
    print("是否是BST:", traversal.is_bst(bst_root))
practical_example()

简洁版：直接可用的函数

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 前序遍历
def preorder(root):
    return [root.val] + preorder(root.left) + preorder(root.right) if root else []
# 中序遍历
def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []
# 后序遍历
def postorder(root):
    return postorder(root.left) + postorder(root.right) + [root.val] if root else []
# 层序遍历
def levelorder(root):
    if not root: return []
    result, queue = [], [root]
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result
# 测试
if __name__ == "__main__":
    # 构建二叉树
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    print("前序:", preorder(root))    # [1, 2, 4, 5, 3]
    print("中序:", inorder(root))     # [4, 2, 5, 1, 3]
    print("后序:", postorder(root))   # [4, 5, 2, 3, 1]
    print("层序:", levelorder(root))  # [1, 2, 3, 4, 5]

输出示例

二叉树遍历测试
----------------------------------------
前序遍历（递归）: [1, 2, 4, 5, 3, 6]
前序遍历（迭代）: [1, 2, 4, 5, 3, 6]
中序遍历（递归）: [4, 2, 5, 1, 3, 6]
中序遍历（迭代）: [4, 2, 5, 1, 3, 6]
后序遍历（递归）: [4, 5, 2, 6, 3, 1]
后序遍历（迭代）: [4, 5, 2, 6, 3, 1]
层序遍历: [[1], [2, 3], [4, 5, 6]]

这些代码涵盖了二叉树遍历的所有常见方式：

• 前序、中序、后序的递归和迭代实现
• 层序遍历（广度优先）
• 实际应用场景（文件系统遍历、二叉搜索树判断等）

你可以根据实际需求选择合适的版本使用。

标签： 迭代遍历