树、字典树和堆
树是一种重要的非线性数据结构，广泛应用于各种算法和系统中。本章将深入讲解二叉树、二叉搜索树、字典树和堆等重要的树形数据结构。
树的基础
树的定义
树是由 n（n≥0）个节点组成的有限集合。当 n=0 时，称为空树；当 n>0 时，有一个特殊的节点称为根节点，其余节点可以分为 m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树，称为子树。
树的术语
- 节点：树中的每个元素
- 根节点：没有父节点的节点
- 叶子节点：没有子节点的节点
- 深度：从根节点到该节点的路径长度
- 高度：从该节点到最深叶子节点的路径长度
- 度：节点的子节点数量
二叉树（Binary Tree）
二叉树的特点
- 每个节点最多有两个子节点（左子节点和右子节点）
- 左子树和右子树是有序的
二叉树的实现
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
二叉树的遍历
1. 前序遍历（Preorder）
def preorder_traversal(root):
if not root:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
# 迭代实现
def preorder_iterative(root):
if not root:
return []
stack = [root]
result = []
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
2. 中序遍历（Inorder）
def inorder_traversal(root):
if not root:
return []
return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
# 迭代实现
def inorder_iterative(root):
stack = []
result = []
current = root
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
3. 后序遍历（Postorder）
def postorder_traversal(root):
if not root:
return []
return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]
# 迭代实现
def postorder_iterative(root):
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
4. 层序遍历（Level Order）
from collections import deque
def level_order_traversal(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
二叉搜索树（BST）
BST 的特点
- 左子树所有节点的值 < 根节点的值
- 右子树所有节点的值 > 根节点的值
- 左右子树都是 BST
BST 的基本操作
1. 查找
def search_bst(root, val):
if not root or root.val == val:
return root
if val < root.val:
return search_bst(root.left, val)
return search_bst(root.right, val)
2. 插入
def insert_bst(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst(root.left, val)
else:
root.right = insert_bst(root.right, val)
return root
3. 删除
def delete_bst(root, val):
if not root:
return root
if val < root.val:
root.left = delete_bst(root.left, val)
elif val > root.val:
root.right = delete_bst(root.right, val)
else:
if not root.left:
return root.right
if not root.right:
return root.left
# 找到右子树的最小节点
min_node = find_min(root.right)
root.val = min_node.val
root.right = delete_bst(root.right, min_node.val)
return root
def find_min(root):
while root.left:
root = root.left
return root
字典树（Trie）
字典树是一种用于快速检索字符串的数据结构。
Trie 的特点
- 每个节点代表一个字符
- 从根节点到某个节点的路径表示一个字符串
- 常用于前缀匹配、字符串搜索
Trie 的实现
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = 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 = 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
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
Trie 的应用
- 前缀匹配
- 自动补全
- 拼写检查
- IP 路由表
堆（Heap）
堆是一种特殊的完全二叉树，满足堆性质。
堆的类型
- 最大堆：父节点的值 ≥ 子节点的值
- 最小堆：父节点的值 ≤ 子节点的值
堆的实现
Python 中使用 heapq 模块：
import heapq
# 最小堆
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap)) # 1
# 最大堆（使用负数）
heap = []
heapq.heappush(heap, -3)
heapq.heappush(heap, -1)
heapq.heappush(heap, -2)
print(-heapq.heappop(heap)) # 3
堆的应用
1. Top K 问题
import heapq
def find_k_largest(nums, k):
return heapq.nlargest(k, nums)
def find_k_smallest(nums, k):
return heapq.nsmallest(k, nums)
2. 合并 K 个有序数组
import heapq
def merge_k_sorted_arrays(arrays):
heap = []
result = []
# 初始化：将每个数组的第一个元素加入堆
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(arrays[arr_idx]):
heapq.heappush(heap, (arrays[arr_idx][elem_idx + 1], arr_idx, elem_idx + 1))
return result
常见题目
1. 二叉树的最大深度
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
2. 验证二叉搜索树
def is_valid_bst(root):
def validate(node, min_val, max_val):
if not node:
return True
if node.val <= min_val or node.val >= max_val:
return False
return validate(node.left, min_val, node.val) and validate(node.right, node.val, max_val)
return validate(root, float('-inf'), float('inf'))
3. 实现 Trie
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node['#'] = True
def search(self, word):
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return '#' in node
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
总结
树结构是算法面试中的重要内容：
- 二叉树：掌握前序、中序、后序、层序遍历
- BST：理解查找、插入、删除操作
- Trie：用于字符串前缀匹配和搜索
- 堆：用于 Top K 问题和优先队列
通过大量练习，你将能够熟练处理各种树相关问题。
接下来，让我们学习哈希表，这是一种高效的查找数据结构。