树（Tree）完全详解 - 从零到红黑树¶
重要性：⭐⭐⭐⭐⭐ 难度：⭐⭐⭐⭐ 学习时间：5-7天 前置知识：递归、链表
📚 目录¶
树的基础¶
什么是树？¶
树是一种非线性、分层的数据结构，由节点（Node）和边（Edge）组成。
生活中的例子¶
想象一个公司的组织结构：
Text Only
CEO
│
┌─────────┼─────────┐
│ │ │
CTO CFO COO
│ │ │
┌───┼───┐ │ ┌───┼───┐
│ │ │ │ │ │ │
开发 测试 产品 财务 销售 市场 客服
- 根节点：CEO（唯一的起点）
- 父/子节点：CTO是开发、测试、产品的父节点
- 叶子节点：没有子节点的节点（开发、测试等）
- 深度：从根到节点的层数
- 高度：树的最大层数
为什么学树？¶
✅ 应用广泛： - 文件系统（目录结构） - HTML DOM树 - 数据库索引（B树、B+树） - 编译器（语法树） - AI决策树
✅ 面试常考： - 二叉树遍历 - 二叉搜索树 - 平衡树（AVL、红黑树） - 树的直径、深度
树的基本概念¶
Text Only
术语图解：
A ← 根节点（Root）
/ \
B C ← 内部节点（Internal Node）
/ \ \
D E F ← 叶子节点（Leaf）
/ \
G H ← 子树（Subtree）
相关概念：
- 节点A的深度：0（根节点深度为0）
- 节点D的深度：2
- 节点G的深度：3
- 树的高度：3（最大深度）
- 节点A的度：2（子节点个数）
- 节点D的度：2
- 节点G的度：0（叶子节点）
二叉树¶
什么是二叉树？¶
二叉树是每个节点最多有两个子节点的树结构。
二叉树的特性¶
Text Only
性质1：二叉树第i层最多有 2^(i-1) 个节点
性质2：深度为k的二叉树最多有 2^k - 1 个节点
性质3：叶子节点数 = 度为2的节点数 + 1
图示：
深度0: 1 个节点 (2^0 = 1)
[A]
深度1: 2 个节点 (2^1 = 2)
[A]
/ \
B C
深度2: 4 个节点 (2^2 = 4)
[A]
/ \
B C
/ \ / \
D E F G
二叉树的类型¶
1. 满二叉树（Full Binary Tree）¶
2. 完全二叉树（Complete Binary Tree）¶
Text Only
定义：除最后一层外，每层都填满，最后一层从左到右填充
示例：
[A]
/ \
B C
/ \ /
D E F
第1层：填满 ✓
第2层：填满 ✓
第3层：从左到右填充（D, E, F） ✓
3. 完美二叉树（Perfect Binary Tree）¶
Text Only
定义：所有叶子节点都在同一层，且每个内部节点都有2个子节点
示例：
[A]
/ \
B C
/ \ / \
D E F G
所有内部节点都有2个子节点 ✓
所有叶子节点都在同一层 ✓
二叉树的实现¶
Python
class TreeNode:
"""二叉树节点"""
def __init__(self, val=0, left=None, right=None):
self.val = val # 节点值
self.left = left # 左子节点
self.right = right # 右子节点
def __repr__(self):
return f"TreeNode({self.val})"
def create_sample_tree():
"""创建示例二叉树"""
"""
创建如下二叉树：
1
/ \
2 3
/ \ \
4 5 6
"""
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
return root
# 可视化打印
def print_tree(root, level=0, prefix="Root: "):
"""打印二叉树结构"""
if root is not None:
print(" " * level * 4 + prefix + str(root.val))
if root.left or root.right:
if root.left:
print_tree(root.left, level + 1, "L--- ")
if root.right:
print_tree(root.right, level + 1, "R--- ")
# 测试
root = create_sample_tree()
print("二叉树结构:")
print_tree(root)
# 输出：
# 二叉树结构:
# Root: 1
# L--- 2
# L--- 4
# R--- 5
# R--- 3
# R--- 6
二叉树的遍历¶
1. 前序遍历（Preorder Traversal）¶
顺序：根 → 左 → 右
Python
def preorder_traversal(root):
"""
前序遍历（递归）
时间：O(n)
空间：O(h)，h是树的高度
"""
if not root:
return []
result = []
result.append(root.val) # 访问根
result.extend(preorder_traversal(root.left)) # 遍历左子树
result.extend(preorder_traversal(root.right)) # 遍历右子树
return result
def preorder_iterative(root):
"""前序遍历（迭代）"""
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# 先右后左（栈是LIFO）
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
# 测试
root = create_sample_tree()
print("前序遍历（递归）:", preorder_traversal(root)) # [1, 2, 4, 5, 3, 6]
print("前序遍历（迭代）:", preorder_iterative(root)) # [1, 2, 4, 5, 3, 6]
前序遍历图解：
Text Only
1
/ \
2 3
/ \ \
4 5 6
前序遍历顺序：
1. 访问根：1
2. 遍历左子树：
a. 访问根：2
b. 遍历左子树：访问4
c. 遍历右子树：访问5
3. 遍历右子树：
a. 访问根：3
b. 遍历左子树：无
c. 遍历右子树：访问6
结果：[1, 2, 4, 5, 3, 6]
2. 中序遍历（Inorder Traversal）¶
顺序：左 → 根 → 右
Python
def inorder_traversal(root):
"""中序遍历（递归）"""
if not root:
return []
result = []
result.extend(inorder_traversal(root.left)) # 遍历左子树
result.append(root.val) # 访问根
result.extend(inorder_traversal(root.right)) # 遍历右子树
return result
def inorder_iterative(root):
"""中序遍历（迭代）"""
if not root:
return []
result = []
stack = []
current = root
while current or stack:
# 一直向左走
while current:
stack.append(current)
current = current.left
# 访问节点
current = stack.pop()
result.append(current.val)
# 转向右子树
current = current.right
return result
# 测试
print("中序遍历（递归）:", inorder_traversal(root)) # [4, 2, 5, 1, 3, 6]
print("中序遍历（迭代）:", inorder_iterative(root)) # [4, 2, 5, 1, 3, 6]
中序遍历图解：
Text Only
1
/ \
2 3
/ \ \
4 5 6
中序遍历顺序：
1. 遍历左子树：
a. 遍历左子树：访问4
b. 访问根：2
c. 遍历右子树：访问5
2. 访问根：1
3. 遍历右子树：
a. 遍历左子树：无
b. 访问根：3
c. 遍历右子树：访问6
结果：[4, 2, 5, 1, 3, 6]
3. 后序遍历（Postorder Traversal）¶
顺序：左 → 右 → 根
Python
def postorder_traversal(root):
"""后序遍历（递归）"""
if not root:
return []
result = []
result.extend(postorder_traversal(root.left)) # 遍历左子树
result.extend(postorder_traversal(root.right)) # 遍历右子树
result.append(root.val) # 访问根
return result
def postorder_iterative(root):
"""后序遍历（迭代）"""
if not root:
return []
result = []
stack = []
last_visited = None
current = root
while current or stack:
if current:
stack.append(current)
current = current.left
else:
peek_node = stack[-1] # 负索引：从末尾倒数访问元素
if peek_node.right and last_visited != peek_node.right:
current = peek_node.right
else:
result.append(peek_node.val)
last_visited = stack.pop()
return result
# 测试
print("后序遍历（递归）:", postorder_traversal(root)) # [4, 5, 2, 6, 3, 1]
print("后序遍历（迭代）:", postorder_iterative(root)) # [4, 5, 2, 6, 3, 1]
4. 层序遍历（Level Order）¶
Python
from collections import deque
def level_order(root):
"""
层序遍历（BFS）
时间：O(n)
空间：O(n)
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
def level_order_detailed(root):
"""层序遍历（详细版：分层返回）"""
if not root:
return []
result = []
queue = deque([root])
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
# 测试
print("层序遍历:", level_order(root)) # [1, 2, 3, 4, 5, 6]
print("层序遍历（分层）:", level_order_detailed(root)) # [[1], [2, 3], [4, 5, 6]]
三种遍历对比：
Text Only
1
/ \
2 3
/ \ \
4 5 6
前序（根左右）：[1, 2, 4, 5, 3, 6]
中序（左根右）：[4, 2, 5, 1, 3, 6]
后序（左右根）：[4, 5, 2, 6, 3, 1]
层序（逐层）：[[1], [2, 3], [4, 5, 6]]
二叉搜索树（BST）¶
什么是BST？¶
二叉搜索树（Binary Search Tree）是一种特殊的二叉树，满足： - 左子树的所有节点值 < 根节点值 - 右子树的所有节点值 > 根节点值 - 左右子树也分别是BST
BST的可视化¶
Text Only
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
BST性质：
- 8的左子树所有值 < 8 ✓
- 8的右子树所有值 > 8 ✓
- 3的左子树所有值 < 3 ✓
- 3的右子树所有值 > 3 ✓
- ...（所有子树都满足）
BST的实现¶
Python
class BST:
"""二叉搜索树"""
def __init__(self):
self.root = None
def insert(self, val):
"""插入值"""
if not self.root:
self.root = TreeNode(val)
print(f"插入根节点: {val}")
return
current = self.root
parent = None
while current:
parent = current
if val < current.val:
current = current.left
elif val > current.val:
current = current.right
else:
print(f"值{val}已存在，不插入")
return
# 插入到合适位置
if val < parent.val:
parent.left = TreeNode(val)
print(f"插入{val}到{parent.val}的左子节点")
else:
parent.right = TreeNode(val)
print(f"插入{val}到{parent.val}的右子节点")
def search(self, val):
"""查找值"""
current = self.root
depth = 0
while current:
print(f"第{depth}层: 比较{val}和{current.val}")
if val == current.val:
print(f" 找到！")
return True
elif val < current.val:
current = current.left
else:
current = current.right
depth += 1
print(f" 未找到")
return False
def inorder(self):
"""中序遍历（BST的中序遍历是有序的！）"""
return inorder_traversal(self.root)
# 测试
bst = BST()
print("=" * 60)
print("BST测试")
print("=" * 60)
# 插入
values = [8, 3, 10, 1, 6, 14, 4, 7, 13]
for val in values:
bst.insert(val)
# 查找
print("\n查找6:")
bst.search(6)
print("\n查找9:")
bst.search(9)
# 中序遍历
print("\n中序遍历:", bst.inorder())
# 输出：
# ============================================================
# BST测试
# ============================================================
# 插入根节点: 8
# 插入3到8的左子节点
# 插入10到8的右子节点
# 插入1到3的左子节点
# 插入6到3的右子节点
# 插入14到10的右子节点
# 插入4到6的左子节点
# 插入7到6的右子节点
# 插入13到14的左子节点
#
# 查找6:
# 第0层: 比较6和8
# 第1层: 比较6和3
# 第2层: 比较6和6
# 找到！
#
# 查找9:
# 第0层: 比较9和8（9>8，向右）
# 第1层: 比较9和10（9<10，向左）
# 左子节点为空，未找到
#
# 中序遍历: [1, 3, 4, 6, 7, 8, 10, 13, 14]
BST操作复杂度¶
| 操作 | 平均 | 最坏 | 说明 |
|---|---|---|---|
| 查找 | O(log n) | O(n) | 树平衡时 |
| 插入 | O(log n) | O(n) | 树平衡时 |
| 删除 | O(log n) | O(n) | 树平衡时 |
| 最小值 | O(log n) | O(n) | 一直向左 |
| 最大值 | O(log n) | O(n) | 一直向右 |
平衡树¶
为什么需要平衡树？¶
问题：BST在最坏情况下会退化成链表。
解决方案：使用自平衡二叉搜索树。
AVL树¶
AVL树是最早的自平衡BST，保证任意节点的两个子树的高度差不超过1。
Python
class AVLNode:
"""AVL树节点"""
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.height = 1 # 节点高度
class AVLTree:
"""AVL树（自平衡二叉搜索树）"""
def __init__(self):
self.root = None
def _height(self, node):
"""获取节点高度"""
return node.height if node else 0
def _update_height(self, node):
"""更新节点高度"""
node.height = 1 + max(self._height(node.left),
self._height(node.right))
def _balance_factor(self, node):
"""计算平衡因子"""
if not node:
return 0
return self._height(node.left) - self._height(node.right)
def _rotate_right(self, y):
"""右旋"""
print(f" 右旋: {y.val}")
x = y.left
T2 = x.right
# 旋转
x.right = y
y.left = T2
# 更新高度
self._update_height(y)
self._update_height(x)
return x
def _rotate_left(self, x):
"""左旋"""
print(f" 左旋: {x.val}")
y = x.right
T2 = y.left
# 旋转
y.left = x
x.right = T2
# 更新高度
self._update_height(x)
self._update_height(y)
return y
def insert(self, val):
"""插入值"""
print(f"\n插入{val}:")
self.root = self._insert(self.root, val)
def _insert(self, node, val):
"""递归插入"""
# 标准BST插入
if not node:
print(f" 创建节点{val}")
return AVLNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
else:
return node # 不允许重复值
# 更新高度
self._update_height(node)
# 获取平衡因子
balance = self._balance_factor(node)
print(f" 节点{node.val}平衡因子: {balance}")
# 不平衡情况1：左左（LL）
if balance > 1 and val < node.left.val:
print(f" 左左不平衡，右旋")
return self._rotate_right(node)
# 不平衡情况2：右右（RR）
if balance < -1 and val > node.right.val:
print(f" 右右不平衡，左旋")
return self._rotate_left(node)
# 不平衡情况3：左右（LR）
if balance > 1 and val > node.left.val:
print(f" 左右不平衡，先左旋后右旋")
node.left = self._rotate_left(node.left)
return self._rotate_right(node)
# 不平衡情况4：右左（RL）
if balance < -1 and val < node.right.val:
print(f" 右左不平衡，先右旋后左旋")
node.right = self._rotate_right(node.right)
return self._rotate_left(node)
return node
# 测试
avl = AVLTree()
print("=" * 60)
print("AVL树测试")
print("=" * 60)
# 插入元素
values = [10, 20, 30, 40, 50, 25]
for val in values:
avl.insert(val)
# 输出：
# ============================================================
# AVL树测试
# ============================================================
#
# 插入10:
# 创建节点10
#
# 插入20:
# 创建节点20
# 节点10平衡因子: -1
#
# 插入30:
# 创建节点30
# 节点20平衡因子: -1
# 节点10平衡因子: -2
# 右右不平衡，左旋
# 左旋: 10
#
# 插入40:
# 创建节点40
# 节点30平衡因子: -1
# 节点20平衡因子: -1
# 节点10平衡因子: -1
#
# 插入50:
# 创建节点50
# 节点40平衡因子: -1
# 节点30平衡因子: -2
# 右右不平衡，左旋
# 左旋: 30
#
# 插入25:
# 创建节点25
# 节点30平衡因子: 0
# 节点20平衡因子: -1
# 节点10平衡因子: -1
AVL树旋转图解：
Text Only
右旋（LL情况）：
旋转前： 旋转后：
y x
/ \ / \
x T3 → T1 y
/ \ / \
T1 T2 T2 T3
左旋（RR情况）：
旋转前： 旋转后：
x y
/ \ / \
T1 y → x T3
/ \ / \
T2 T3 T1 T2
堆和优先队列¶
什么是堆？¶
堆是一种特殊的完全二叉树，分为： - 大顶堆：父节点 >= 子节点 - 小顶堆：父节点 <= 子节点
堆的可视化¶
堆的实现¶
Python
import heapq
# Python的heapq模块实现小顶堆
class Heap:
"""堆（小顶堆）"""
def __init__(self):
self.heap = []
def push(self, val):
"""入堆：O(log n)"""
heapq.heappush(self.heap, val)
print(f"入堆: {val}, 堆: {self.heap}")
def pop(self):
"""出堆：O(log n)"""
if not self.heap:
raise IndexError("堆为空")
val = heapq.heappop(self.heap)
print(f"出堆: {val}, 堆: {self.heap}")
return val
def peek(self):
"""查看堆顶：O(1)"""
if not self.heap:
raise IndexError("堆为空")
return self.heap[0]
def heapify(self, nums):
"""建堆：O(n)"""
heapq.heapify(nums)
self.heap = nums
print(f"建堆: {self.heap}")
# 测试
heap = Heap()
print("=" * 60)
print("堆测试")
print("=" * 60)
# 建堆
nums = [4, 10, 3, 5, 1]
heap.heapify(nums)
# 入堆
heap.push(2)
heap.push(7)
# 出堆
heap.pop()
heap.pop()
# 输出：
# ============================================================
# 堆测试
# ============================================================
# 建堆: [1, 4, 3, 5, 10]
# 入堆: 2, 堆: [1, 4, 2, 5, 10, 3]
# 入堆: 7, 堆: [1, 4, 2, 5, 10, 3, 7]
# 出堆: 1, 堆: [2, 4, 3, 5, 10, 7]
# 出堆: 2, 堆: [3, 4, 7, 5, 10]
经典面试题¶
题目1：二叉树的最大深度 ⭐⭐⭐¶
问题：给定一个二叉树，找出其最大深度。
Python
def max_depth(root):
"""
最大深度
时间：O(n)
空间：O(h)
"""
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
题目2：翻转二叉树 ⭐⭐⭐¶
问题：翻转二叉树。
Python
def invert_tree(root):
"""
翻转二叉树
时间：O(n)
空间：O(h)
"""
if not root:
return None
# 交换左右子节点
root.left, root.right = root.right, root.left
# 递归翻转
invert_tree(root.left)
invert_tree(root.right)
return root
题目3：对称二叉树 ⭐⭐⭐¶
问题：判断二叉树是否对称。
Python
def is_symmetric(root):
"""
判断对称二叉树
时间：O(n)
空间：O(h)
"""
if not root:
return True
def check(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
check(left.left, right.right) and
check(left.right, right.left))
return check(root.left, root.right)
📝 总结¶
核心要点¶
✅ 树的特点： - 分层结构、非线性 - 根节点、叶子节点、深度、高度
✅ 二叉树： - 每个节点最多2个子节点 - 4种遍历：前、中、后、层序
✅ BST： - 左 < 根 < 右 - 查找、插入、删除O(log n)
✅ 平衡树： - AVL树、红黑树 - 自平衡旋转
✅ 堆： - 大顶堆、小顶堆 - 优先队列
下一步¶
继续学习： - 图算法 - Dijkstra、Floyd、MST - 贪心算法 - 贪心思想
继续查看图算法...