树 树是图论中一种极为重要的特殊图。它不仅在数学中具有基础地位，在计算机科学（如数据结构、算法）、运筹学、生物学（如进化树）等领域也有广泛应用。我们可以从多个层面来理解它的定义和性质。 第一步：树的定义与基本性质 一个图要被称为“树”，必须同时满足以下三个条件中的任意两个（只要满足两个，第三个就会自动成立）： 连通 ：图中任意两个顶点之间都存在一条路径。 无环 ：图中不包含任何回路（即首尾顶点相同的路径）。 边数公式 ：如果一个树有 n 个顶点，那么它恰好有 n-1 条边。 这三个条件是等价的。例如，我们可以将树定义为“一个无环的连通图”。根据这个定义，我们可以推导出它必然有 n-1 条边。反之，我们也可以将其定义为“一个有 n 个顶点和 n-1 条边的连通图”，那么它必然是无环的。 第二步：树的实例与相关概念 最简单的树是只有一个顶点的树（平凡树），它没有边。有两个顶点的树是一条边，有三个顶点的树是两条边组成的路径。任何一条“路径”本身都是一个树，因为它连通且无环。 与树相关的几个关键概念： 叶子（或悬挂点） ：在树中，度数为1的顶点称为叶子。每一个非平凡树（顶点数 ≥ 2）都至少有两个叶子。 森林 ：一个“无环”的图称为森林。因此，森林是由一棵或多棵互不连接的树组成的。森林是树的推广。 第三步：树的核心定理与特征 树有一个非常核心的特征，这个特征也常常被用作它的定义： “唯一路径”性质 ：在一个树中，任意两个顶点之间都存在 唯一的一条 路径。 连通性 保证了路径的存在性。 无环性 保证了路径的唯一性。因为如果存在两条不同的路径连接同一对顶点，那么这两条路径就可以组合形成一个环，这与无环的定义矛盾。 这个“唯一路径”性质是树在许多应用中（如网络路由、决策树）如此有用的根本原因。 第四步：生成树 生成树的概念将“树”与一个给定的图联系起来，极大地扩展了树的应用范围。 定义 ：对于一个连通图 G ，它的 生成树 是 G 的一个子图，它必须满足： 包含 G 的所有顶点。 它本身是一棵树。 简单来说，生成树就是从一个连通图中“修剪”掉一些边，直到它没有环为止，但同时保持了所有顶点的连通性。生成树就像是图的“骨架”或“主干”。 存在性 ：每一个连通图都至少有一棵生成树。 应用 ：生成树在网络设计中有核心应用。例如，要为一个建筑的多个房间部署网络线路，希望线路总长度最短且不形成环路（环路会导致广播风暴），那么问题就转化为在带权图中寻找一棵总权重最小的生成树，即“最小生成树”问题。 第五步：根树 当我们为树中的某一个顶点赋予特殊的地位时，就得到了根树。 定义 ：一棵指定了 根顶点 的树称为根树。根是树的起点或参照点。 层次结构 ：在根树中，我们可以定义顶点的“深度”（从根到该顶点的路径长度）和“高度”（从根到最远叶子的深度）。这使得树呈现出清晰的层次结构。 家族关系 ：基于根，我们可以定义父顶点、子顶点、兄弟顶点、祖先和后代等关系。这种结构完美地模拟了家族树或组织结构图。 应用 ：根树是计算机科学中最基本的数据结构之一。二叉树、决策树、文件系统目录结构、游戏决策树等都是根树的直接体现。