数据结构——树
如果说数组、链表是“线性”世界的代表，那么树（Tree）则开启了“层次化”结构的大门。树是一种非线性的数据结构，它通过节点之间的父子关系，优雅地表达了层次分明的数据组织方式。从文件系统到网页的 DOM 树，从数据库索引到人工智能的决策树，树的影子无处不在。
本文将从树的基本概念入手，逐步深入到二叉树、二叉搜索树、树的遍历方式，并简要介绍平衡树和堆等变体，最后总结树的应用场景和复杂度。让我们一起走进这个层次化的递归世界。
一、什么是树？
树是由 n（n ≥ 0）个节点组成的有限集合。当 n = 0 时，称为空树。当 n > 0 时，存在一个特殊的节点称为根节点（Root），其余节点被划分为 m（m ≥ 0）个互不相交的有限集合，每个集合本身又是一棵树，称为根节点的子树（Subtree）。
这种定义具有递归性：树由根和若干子树组成，而子树又是树。正是这种递归特性，使得很多树相关的算法天然适合用递归实现。
树的基本术语
-
节点：树中的基本元素，包含数据以及指向子节点的引用。
-
根节点：树的最顶层节点，没有父节点。
-
叶子节点：没有子节点的节点。
-
父节点、子节点、兄弟节点：节点之间的相对关系。
-
节点的度：节点拥有的子树的个数。
-
树的度：树中所有节点的度的最大值。
-
深度（Depth）：从根节点到该节点所经过的边的数量（根深度为 0）。
-
高度（Height）：从该节点到最远叶子节点的边的数量（叶子高度为 0）。
-
层（Level）：根节点在第 1 层（或第 0 层，视定义而定），其子节点在第 2 层，依此类推。
二、二叉树（Binary Tree）
二叉树是树结构中最重要、最基础的一种，它的每个节点最多只有两个子节点，分别称为左孩子和右孩子。二叉树的性质使其在计算机科学中占据了核心地位。
二叉树的分类
-
满二叉树：所有叶子节点都在同一层，且每个非叶子节点都有两个子节点。
-
完全二叉树：除了最后一层外，其余层节点数达到最大，且最后一层的节点都靠左排列。
-
平衡二叉树：任意节点的左右子树高度差不超过 1（AVL 树、红黑树等）。
二叉树的存储方式
链式存储
每个节点是一个对象，包含数据域和左右指针。这是最常用的方式。
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
顺序存储（数组）
将二叉树按层序编号，存入数组。对于下标 i 的节点：
-
左子节点下标：
2i + 1 -
右子节点下标：
2i + 2 -
父节点下标：
(i - 1) // 2
这种方式适合完全二叉树，对普通二叉树会有空间浪费。
三、二叉搜索树（BST）
二叉搜索树（Binary Search Tree）是一种特殊的二叉树，它满足左小右大的性质：
-
左子树上所有节点的值均小于根节点的值。
-
右子树上所有节点的值均大于根节点的值。
-
左右子树也分别为二叉搜索树。
这个性质使得 BST 支持高效的查找、插入和删除操作。
BST 的基本操作
1. 查找
def search(root, target):
if root is None or root.value == target:
return root
if target < root.value:
return search(root.left, target)
else:
return search(root.right, target)
2. 插入
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
# 若相等，通常不插入或根据需求处理
return root
3. 删除
删除节点较为复杂，分三种情况：
-
叶子节点：直接删除。
-
只有一个子节点：用子节点替代。
-
有两个子节点：用右子树的最小节点（或左子树的最大节点）替换，并删除该最小节点。
def delete(root, value):
if root is None:
return None
if value < root.value:
root.left = delete(root.left, value)
elif value > root.value:
root.right = delete(root.right, value)
else:
# 找到要删除的节点
if root.left is None:
return root.right
if root.right is None:
return root.left
# 有两个孩子，找到右子树的最小节点
min_node = find_min(root.right)
root.value = min_node.value
root.right = delete(root.right, min_node.value)
return root
def find_min(root):
while root.left:
root = root.left
return root
BST 的复杂度分析
-
查找、插入、删除：平均 O(log n)，最坏 O(n)（当树退化为链表时）。
-
空间复杂度：O(n)。
四、树的遍历
遍历是树最核心的操作之一。根据访问根节点的顺序，分为深度优先遍历（DFS）和广度优先遍历（BFS）。
深度优先遍历（DFS）
前序遍历（Preorder）：根 → 左 → 右
def preorder(root):
if root:
print(root.value, end=' ')
preorder(root.left)
preorder(root.right)
中序遍历（Inorder）：左 → 根 → 右
对 BST 进行中序遍历可以得到有序序列。
def inorder(root):
if root:
inorder(root.left)
print(root.value, end=' ')
inorder(root.right)
后序遍历（Postorder）：左 → 右 → 根
常用于释放树节点或计算表达式树。
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.value, end=' ')
广度优先遍历（BFS）：层序遍历
按层从上到下、从左到右依次访问。通常使用队列实现。
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)
遍历的时间复杂度
所有遍历方式都访问每个节点一次，因此时间复杂度均为 O(n)，空间复杂度取决于递归栈或队列的大小，最坏 O(n)。
五、平衡二叉树
BST 的性能依赖于树的平衡程度。为了解决最坏情况下的 O(n) 复杂度，人们发明了自平衡二叉搜索树，在插入和删除后通过旋转操作保持树的平衡。
AVL 树
AVL 树是最早发明的自平衡 BST，它通过维护每个节点的平衡因子（左子树高度 - 右子树高度）来确保任意节点的平衡因子绝对值 ≤ 1。插入或删除后，如果平衡被破坏，则通过左旋、右旋等操作恢复平衡。
-
查找、插入、删除均为 O(log n)。
-
实现相对复杂，但提供了严格平衡。
红黑树
红黑树是一种近似平衡的 BST，它通过为节点着色（红或黑）并满足五条性质来保证树的高度大致为 2log n。与 AVL 相比，红黑树的插入删除旋转次数更少，因此在实际应用中更广泛（如 Java 的 TreeMap、C++ 的 std::map 等）。
-
查找、插入、删除均为 O(log n)。
六、堆（Heap）
堆是一种特殊的完全二叉树，它满足堆序性：
-
最大堆：每个节点的值 ≥ 其子节点的值（根最大）。
-
最小堆：每个节点的值 ≤ 其子节点的值（根最小）。
堆通常用数组存储，因为完全二叉树可以紧凑地映射到数组。堆常用于实现优先队列，支持在 O(log n) 时间内插入和删除最大（或最小）元素，在 O(1) 时间内获取最大（或最小）元素。
堆的基本操作（以最大堆为例）
-
上浮（sift up）：插入元素时，将其放在末尾，然后不断与父节点比较并交换，直到满足堆序。
-
下沉（sift down）：删除堆顶时，将末尾元素移到堆顶，然后不断与较大的子节点交换，直到满足堆序。
class MaxHeap:
def __init__(self):
self.heap = []
def push(self, val):
self.heap.append(val)
self._sift_up(len(self.heap) - 1)
def pop(self):
if not self.heap:
return None
self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
val = self.heap.pop()
if self.heap:
self._sift_down(0)
return val
def _sift_up(self, idx):
parent = (idx - 1) // 2
while idx > 0 and self.heap[idx] > self.heap[parent]:
self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
idx = parent
parent = (idx - 1) // 2
def _sift_down(self, idx):
n = len(self.heap)
while True:
left = 2 * idx + 1
right = 2 * idx + 2
largest = idx
if left < n and self.heap[left] > self.heap[largest]:
largest = left
if right < n and self.heap[right] > self.heap[largest]:
largest = right
if largest == idx:
break
self.heap[idx], self.heap[largest] = self.heap[largest], self.heap[idx]
idx = largest
堆的应用
-
优先队列（操作系统任务调度、Dijkstra 算法等）
-
堆排序（O(n log n) 的不稳定排序）
-
求 Top K 问题（维护大小为 K 的堆）
-
中位数查找（使用两个堆）
七、树的经典应用
树形结构因其天然的层次性和递归特性，在计算机科学中应用极广：
-
文件系统：目录和文件的层级结构。
-
数据库索引：B 树、B+ 树是关系型数据库的核心索引结构。
-
编译原理：语法树（AST）表示程序的结构。
-
网络路由：路由表可以用树结构组织。
-
人工智能：决策树、博弈树（如 AlphaGo 的蒙特卡洛树搜索）。
-
数据压缩：哈夫曼树用于构建最优前缀编码（哈夫曼编码）。
-
表达式求值：表达式树可以方便地计算中缀表达式。
-
XML/HTML 解析：DOM 树是文档对象模型的基础。
八、树与递归
树的结构天然与递归绑定。几乎所有的树操作都可以用简洁的递归算法实现，例如遍历、查找、插入、删除等。递归的魅力在于它直接反映了树的定义：对根操作，然后递归地对子树操作。
然而，递归也有栈溢出的风险（深度过大时）。对于深度很大的树，可以考虑使用迭代（栈或队列）来实现遍历。
九、复杂度总结
| 数据结构 | 查找平均 | 查找最坏 | 插入平均 | 插入最坏 | 删除平均 | 删除最坏 |
|---|---|---|---|---|---|---|
| 普通 BST | O(log n) | O(n) | O(log n) | O(n) | O(log n) | O(n) |
| AVL 树 | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| 红黑树 | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| 堆（优先队列） | O(1)（取最值） | O(1) | O(log n) | O(log n) | O(log n) | O(log n) |
| 遍历（任意树） | O(n) | O(n) | - | - | - | - |
十、总结
树是数据结构中“分治”思想的完美体现。通过这篇文章，我们了解了：
-
树的基本概念和术语，以及递归定义。
-
二叉树及其常见类型（满、完全、平衡）。
-
二叉搜索树的查找、插入、删除操作及复杂度。
-
四种遍历方式（前序、中序、后序、层序）及其实现。
-
平衡树（AVL、红黑树）如何解决 BST 的退化问题。
-
堆作为特殊树的应用和实现。
-
树在计算机科学中的广泛应用。
树的学习不仅有助于解决特定问题，更能培养抽象思维和递归思考能力。如果你正在学习数据结构，不妨从实现一个简单的二叉搜索树开始，然后尝试将其改写为 AVL 树，这将是一次绝佳的练习。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
8
0- 0
已为社区贡献3条内容
所有评论(0)