Python语言二叉树应用实例详解（从零开始掌握二叉树的构建与遍历）

第一步：定义二叉树节点类

在 Python 中，我们通常使用类（class）来表示二叉树的节点：

class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right

这个 TreeNode 类包含三个属性：

• val：节点存储的值
• left：指向左子节点
• right：指向右子节点

第二步：创建一个简单的二叉树

让我们手动构建如下所示的二叉树：

      1     / \    2   3   / \  4   5

对应的 Python 代码如下：

# 创建根节点root = TreeNode(1)# 创建左右子节点root.left = TreeNode(2)root.right = TreeNode(3)# 为左子节点添加子节点root.left.left = TreeNode(4)root.left.right = TreeNode(5)

第三步：二叉树的三种基本遍历方式

遍历是访问二叉树所有节点的过程。主要有三种方式：

1. 前序遍历（根 → 左 → 右）

def preorder_traversal(root):    if root is None:        return []    result = []    result.append(root.val)              # 访问根节点    result += preorder_traversal(root.left)   # 遍历左子树    result += preorder_traversal(root.right)  # 遍历右子树    return result

2. 中序遍历（左 → 根 → 右）

def inorder_traversal(root):    if root is None:        return []    result = []    result += inorder_traversal(root.left)    # 遍历左子树    result.append(root.val)                  # 访问根节点    result += inorder_traversal(root.right)   # 遍历右子树    return result

3. 后序遍历（左 → 右 → 根）

def postorder_traversal(root):    if root is None:        return []    result = []    result += postorder_traversal(root.left)   # 遍历左子树    result += postorder_traversal(root.right)  # 遍历右子树    result.append(root.val)                    # 访问根节点    return result

对上面构建的树进行测试：

print("前序遍历:", preorder_traversal(root))   # 输出: [1, 2, 4, 5, 3]print("中序遍历:", inorder_traversal(root))   # 输出: [4, 2, 5, 1, 3]print("后序遍历:", postorder_traversal(root)) # 输出: [4, 5, 2, 3, 1]

第四步：二叉搜索树（BST）简介

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，它满足以下性质：

• 左子树中所有节点的值 < 根节点的值
• 右子树中所有节点的值 > 根节点的值
• 左右子树也分别是二叉搜索树

这种结构使得查找、插入、删除操作的平均时间复杂度为 O(log n)，非常适合用于实现字典或集合。

总结

通过本教程，你已经掌握了：

• 如何用 Python 定义二叉树节点
• 如何手动构建一棵二叉树
• 三种基本的二叉树遍历方法
• 二叉搜索树的基本概念

这些知识是学习更高级数据结构教程的基础。建议你动手敲一遍代码，加深理解！

关键词回顾：Python二叉树、二叉树遍历、二叉搜索树、数据结构教程