Python中树的种类及实现详解

树结构基础概念

树是由节点和边组成的层次结构，具有以下特点：

• 每个树有一个根节点
• 除根节点外，每个节点有且仅有一个父节点
• 节点可以有零个或多个子节点
• 没有子节点的节点称为叶节点

Python中常见的树结构

1. 二叉树 (Binary Tree)

每个节点最多有两个子节点的树结构，分别称为左子节点和右子节点。

应用场景： 表达式树、哈夫曼编码、二叉堆

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

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

2. 二叉搜索树 (Binary Search Tree)

特殊的二叉树，满足：左子树所有节点值小于根节点，右子树所有节点值大于根节点。

应用场景： 数据排序、查找操作、数据库索引

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return BSTNode(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

# 创建二叉搜索树
bst_root = None
keys = [50, 30, 70, 20, 40, 60, 80]
for key in keys:
    bst_root = insert(bst_root, key)

3. 平衡二叉树 (AVL树)

自平衡二叉搜索树，任何节点的两个子树的高度差最多为1。

应用场景： 需要频繁插入/删除的场景，如数据库系统

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def get_height(node):
    if not node:
        return 0
    return node.height

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def rotate_right(y):
    x = y.left
    T2 = x.right
    
    x.right = y
    y.left = T2
    
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    
    return x

4. 红黑树 (Red-Black Tree)

另一种自平衡二叉搜索树，通过对节点着色和旋转操作保持平衡。

应用场景： Java的TreeMap、C++的STL、Linux内核调度

class RBNode:
    def __init__(self, key, color='R'):
        self.key = key
        self.color = color  # 'R' for red, 'B' for black
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.root = None
    
    def insert(self, key):
        # 插入逻辑和平衡调整
        pass
    
    def fix_insert(self, node):
        # 修复红黑树性质
        pass

5. B树和B+树

多路平衡搜索树，设计用于磁盘或其他直接存取辅助设备。

应用场景： 文件系统、数据库索引

class BTreeNode:
    def __init__(self, leaf=True):
        self.keys = []
        self.children = []
        self.leaf = leaf

class BTree:
    def __init__(self, t):
        self.root = BTreeNode()
        self.t = t  # 最小度数
    
    def insert(self, key):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            new_root = BTreeNode(False)
            new_root.children.append(self.root)
            self.root = new_root
            self.split_child(new_root, 0)
            self.insert_non_full(new_root, key)
        else:
            self.insert_non_full(root, key)

6. 字典树 (Trie)

用于高效存储和检索字符串集合的树结构。

应用场景： 自动补全、拼写检查、IP路由

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

7. 堆 (Heap)

特殊的树结构（通常是二叉树），满足堆属性：父节点值总是大于/小于子节点值。

应用场景： 优先队列、堆排序、图算法

import heapq

# 使用Python内置堆实现
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)

print(heapq.heappop(heap))  # 输出1
print(heapq.heappop(heap))  # 输出2

树结构选择指南

树结构遍历方法

树结构常用的遍历方式：

• 深度优先遍历(DFS): 前序、中序、后序遍历
• 广度优先遍历(BFS): 层次遍历

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.value)
        inorder_traversal(root.right)

from collections import deque

def level_order_traversal(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)