Python二叉树详解

二叉树基本概念

二叉树是每个节点最多有两个子节点的树结构，通常称为左子节点和右子节点。二叉树在计算机科学中有广泛应用，如表达式树、二叉搜索树、堆等数据结构。

Python实现二叉树

节点类定义

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val      # 节点存储的值
4        self.left = left    # 左子节点
5        self.right = right  # 右子节点

创建简单二叉树

1# 创建一个简单的二叉树
2#       1
3#      / \
4#     2   3
5#    / \
6#   4   5
7
8root = TreeNode(1)
9root.left = TreeNode(2)
10root.right = TreeNode(3)
11root.left.left = TreeNode(4)
12root.left.right = TreeNode(5)

二叉树遍历方法

1. 深度优先遍历(DFS)

前序遍历(根-左-右)

1def preorder_traversal(root):
2    if root:
3        print(root.val, end=" ")  # 访问根节点
4        preorder_traversal(root.left)
5        preorder_traversal(root.right)

中序遍历(左-根-右)

1def inorder_traversal(root):
2    if root:
3        inorder_traversal(root.left)
4        print(root.val, end=" ")  # 访问根节点
5        inorder_traversal(root.right)

后序遍历(左-右-根)

1def postorder_traversal(root):
2    if root:
3        postorder_traversal(root.left)
4        postorder_traversal(root.right)
5        print(root.val, end=" ")  # 访问根节点

2. 广度优先遍历(BFS)/层次遍历

1from collections import deque
2
3def level_order_traversal(root):
4    if not root:
5        return
6    
7    queue = deque([root])
8    while queue:
9        node = queue.popleft()
10        print(node.val, end=" ")
11        if node.left:
12            queue.append(node.left)
13        if node.right:
14            queue.append(node.right)

二叉树常见操作

计算树的高度

1def tree_height(root):
2    if not root:
3        return 0
4    return 1 + max(tree_height(root.left), tree_height(root.right))

查找节点

1def find_node(root, target):
2    if not root:
3        return False
4    if root.val == target:
5        return True
6    return find_node(root.left, target) or find_node(root.right, target)

统计节点数量

1def count_nodes(root):
2    if not root:
3        return 0
4    return 1 + count_nodes(root.left) + count_nodes(root.right)

特殊二叉树类型

1. 二叉搜索树(BST)

左子树所有节点值小于根节点值
右子树所有节点值大于根节点值
左右子树也都是二叉搜索树

1def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
2    if not root:
3        return True
4    if root.val <= min_val or root.val >= max_val:
5        return False
6    return (is_valid_bst(root.left, min_val, root.val) and 
7            is_valid_bst(root.right, root.val, max_val))

2. 平衡二叉树(AVL树)

任意节点的左右子树高度差不超过1

1def is_balanced(root):
2    def check_height(node):
3        if not node:
4            return 0
5        left = check_height(node.left)
6        right = check_height(node.right)
7        if left == -1 or right == -1 or abs(left - right) > 1:
8            return -1
9        return 1 + max(left, right)
10    
11    return check_height(root) != -1

实际应用场景

文件系统结构：目录和子目录的关系
数据库索引：B树和B+树是二叉树的扩展
压缩算法：哈夫曼编码树
游戏AI：决策树的构建
网络路由：路由表的高效查找