1. 概述
在本篇教程中，我们将重点介绍两种非常重要的数据结构：树（Tree） 与 图（Graph）。这两种结构在解决复杂问题时具有广泛的应用价值，尤其在算法设计、数据建模、路径查找等方面表现突出。
2. 树结构
树是一种递归定义的数据结构，由节点组成。 每个节点包含一个值和一组指向子节点的引用。如下图所示，树结构中的每个圆圈代表一个节点，连接线表示节点之间的边。
上图中，节点 A 是树的根节点，它有两个子节点 B 和 C。B 和 C 被称为“兄弟节点”，因为它们有相同的父节点 A。树具有明显的层级关系，A 是所有节点的祖先，而 B 和 C 各自拥有不同的后代。
注意：上图并不是一棵二叉树，而是一棵通用树（Generic Tree），它允许每个节点有多个子节点，且不强制排序。
我们通常使用树来表示具有层级关系的数据。例如，在象棋等策略游戏中，我们可以使用决策树来表示所有可能的走法。树结构在现实世界中应用广泛，比如文件系统、组织架构图、DOM 树等。
2.1. 二叉树（Binary Tree）
二叉树是一种特殊的树结构，每个节点最多只能有两个子节点：左子节点和右子节点。
与自然界中根在地下、枝叶向上的树不同，计算机科学中的树结构通常将根节点放在最上方，子节点向下延伸。
严格二叉树（Strictly Binary Tree） 是指每个非叶子节点都必须有两个子节点的二叉树。对于一个严格二叉树，若其叶子节点数量为 n，则总节点数为 2n - 1。
树的层级从根节点开始计算，根节点的层级为 0，其子节点为 1，依此类推。例如，在上图左侧的二叉树中，节点 H 的层级为 3。树的深度（Depth）是指树中最深叶子节点所在的层级。
2.2. 二叉搜索树（Binary Search Tree, BST）
二叉搜索树是二叉树的一种特殊形式，具有以下性质：
- 每个节点的左子树中的所有节点值都小于该节点的值
- 每个节点的右子树中的所有节点值都大于该节点的值
BST 的这种结构非常适合快速查找、插入和删除操作，其平均时间复杂度为 *O(log n)*。
3. 图结构
图是一种由节点（顶点）和边组成的数据结构。 它与树类似，但更加灵活，没有树结构的严格限制。
下图展示了一个包含 11 个城市之间单向路线的图结构：
当两个节点之间有边连接时，称它们为相邻节点（Adjacent Vertices）。
图的实现方式主要有两种：
- 邻接矩阵（Adjacency Matrix）：适合节点数量固定、边较多的图
- 邻接表（Adjacency List）：适合稀疏图，节省空间
图可以分为以下几种类型：
- 连通图（Connected） 与 非连通图（Disconnected）
- 完全图（Complete Graph）
- 有向图（Directed Graph） 与 无向图（Undirected Graph）
- 有权图（Weighted Graph） 与 无权图（Unweighted Graph）
选择哪种图结构取决于具体问题。例如，在计算城市之间的最短路径时，通常会使用有权图来表示不同路径的成本。
4. 树与图的关键区别
虽然树可以看作是图的一种特殊形式，但它们之间存在显著差异：
✅ 结构差异：
| 特性 | 树 | 图 |
|---|---|---|
| 结构类型 | 层级结构 | 网络结构 |
| 路径唯一性 | 任意两个节点之间只有一条路径 | 节点之间可能有多个路径 |
| 环路 | 不包含环 | 可以包含环甚至自环 |
| 边数 | 有固定关系：T-1 条边（T 为节点数） |
无固定关系 |
| 根节点 | 有唯一根节点 | 没有根节点概念 |
| 遍历方式 | 中序、前序、后序遍历 | BFS、DFS |
❌ 复杂性：
- 树结构简单，易于理解和实现
- 图结构更复杂，适合建模现实世界中的多维关系
⚠️ 常见误区：
- 不要误以为图只是树的扩展，它们是两种不同维度的数据模型
- 在图中，节点之间可以有任意连接，而树必须遵循严格的父子关系
5. 总结
本文简要介绍了树和图这两种重要的数据结构，并重点比较了它们之间的异同。树适用于表示具有层级关系的数据，而图则更适合建模复杂的关系网络。
无论你是做算法题、系统设计，还是研究社交网络、推荐系统，掌握树与图的基本概念和应用都是非常关键的。它们不仅是计算机科学的基础，也广泛应用于数学、物理等多个领域。