目录

树数据结构简介

树是一种重要的非线性数据结构，由节点和边组成，具有层级关系。树结构在计算机科学中应用广泛，包括：

  • 文件系统的目录结构
  • 数据库索引（如B树、B+树）
  • 组织层级关系（公司架构）
  • AI决策树
  • 编译器中的语法树

二叉树可视化示例

A
B
C
D
E
F
G

图：二叉树结构示例（根节点为A）

Python中的常见树类型

二叉树

每个节点最多有两个子节点

二叉搜索树

左子树值 ≤ 节点值 ≤ 右子树值

AVL树

自平衡二叉搜索树

红黑树

另一种高效的自平衡树

树节点实现

在Python中，树节点可以通过类来实现：

class TreeNode: def __init__(self, value): self.value = value # 节点存储的值 self.left = None # 左子节点 self.right = None # 右子节点 def __str__(self): return f"Node({self.value})"

创建简单二叉树

# 创建节点 root = TreeNode('A') root.left = TreeNode('B') root.right = TreeNode('C') root.left.left = TreeNode('D') root.left.right = TreeNode('E') root.right.left = TreeNode('F') root.right.right = TreeNode('G')

树的遍历算法

遍历是树操作的核心，主要有四种方式：

遍历方式 访问顺序 应用场景
前序遍历 根节点 → 左子树 → 右子树 创建树的副本
中序遍历 左子树 → 根节点 → 右子树 二叉搜索树排序
后序遍历 左子树 → 右子树 → 根节点 删除树节点
层次遍历 按层级从上到下，从左到右 寻找最短路径

递归实现遍历

def preorder(node): if node: print(node.value, end=' ') # 访问当前节点 preorder(node.left) # 递归左子树 preorder(node.right) # 递归右子树 def inorder(node): if node: inorder(node.left) # 递归左子树 print(node.value, end=' ') # 访问当前节点 inorder(node.right) # 递归右子树 def postorder(node): if node: postorder(node.left) # 递归左子树 postorder(node.right) # 递归右子树 print(node.value, end=' ') # 访问当前节点

层次遍历实现（使用队列）

from collections import deque def level_order(root): if not root: return queue = deque([root]) while queue: node = queue.popleft() print(node.value, end=' ') if node.left: queue.append(node.left) if node.right: queue.append(node.right)

二叉搜索树操作

二叉搜索树（BST）是一种特殊的二叉树，满足：

  • 左子树所有节点值 ≤ 当前节点值
  • 右子树所有节点值 ≥ 当前节点值

BST插入操作

def insert(root, value): if not root: return TreeNode(value) if value < root.value: root.left = insert(root.left, value) else: root.right = insert(root.right, value) return root

时间复杂度: O(h) h为树的高度

BST查找操作

def search(root, value): if not root: return False if root.value == value: return True elif value < root.value: return search(root.left, value) else: return search(root.right, value)

时间复杂度: O(h)

BST删除操作

def delete(root, value): if not root: return root if value < root.value: root.left = delete(root.left, value) elif value > root.value: root.right = delete(root.right, value) else: # 节点只有一个子节点或没有子节点 if not root.left: return root.right elif not root.right: return root.left # 节点有两个子节点：找到右子树的最小节点 temp = find_min(root.right) root.value = temp.value root.right = delete(root.right, temp.value) return root def find_min(node): current = node while current.left: current = current.left return current

时间复杂度: O(h)

平衡树：AVL树实现

AVL树通过旋转操作保持树的平衡，确保树高度为O(log n)

AVL树节点

class AVLNode(TreeNode): def __init__(self, value): super().__init__(value) 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 right_rotate(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 def left_rotate(x): y = x.right T2 = y.left # 执行旋转 y.left = x x.right = T2 # 更新高度 x.height = 1 + max(get_height(x.left), get_height(x.right)) y.height = 1 + max(get_height(y.left), get_height(y.right)) return y

树结构的实际应用

  • 文件系统：目录树结构
  • 数据库索引：B树和B+树提高查询效率
  • 路由算法：网络路由中的决策树
  • 游戏开发：场景图管理
  • XML/HTML解析：DOM树表示文档结构
  • AI决策：决策树分类算法

最佳实践提示： 在Python中实现树结构时，考虑使用递归简化代码，但注意递归深度限制。对于大型树结构，使用迭代方法可以避免栈溢出问题。