~/posts/树基础（树的概念&直径&重心&最小生成树）.md

树基础（树的概念&直径&重心&最小生成树）

// 系统介绍树的基础概念、直径、重心以及最小生成树，配有交互式动画演示

周五 3月 27 2026
5258 字 · 28 分钟
$ cd tech # algorithm # data-structure # tree # graph # mst # visualization

树是图论中最基础也最重要的数据结构之一。它具有优美的性质和广泛的应用，从文件系统到决策树，从 HTML 文档到组织架构，树无处不在。本文将从基础概念出发，逐步深入探讨树的直径、重心以及最小生成树等重要专题。

第一部分：树基础

树的定义

无根树

无根树是指没有固定根节点的树。它有多种等价定义：

  1. 有 nn 个节点和 n−1n-1 条边的连通无向图
  2. 无环的连通无向图
  3. 任意两点间有且仅有一条简单路径的图
  4. 任意添加一条边都会形成环的图

这些定义从不同角度描述了树的本质特征：连通、无环、边数等于点数减一。

有根树

有根树是在无根树的基础上，指定一个节点作为”根”所形成的树。根节点赋予了树明确的层级关系，形成了自上而下的结构。

交互演示 无根树 ⇄ 有根树

点击"选择根节点"后，再点击树上任意节点作为根

树的术语

通用术语

术语定义
森林每个连通分量都是树的图，即多棵树的集合
生成树包含图中所有顶点且连通的 n−1n-1 条边构成的子图
叶节点在无根树中度数不超过 1 的节点；在有根树中没有子节点的节点
度数与节点相连的边数（无根树）或子节点数（有根树）

有根树专属术语

  • 父亲 (Parent)：节点到根路径上的相邻上级节点
  • 子节点 (Child)：节点的相邻下级节点
  • 兄弟 (Sibling)：具有相同父亲的节点
  • 祖先 (Ancestor)：从节点到根路径上的所有节点
  • 后代 (Descendant)：以该节点为根的子树中的所有节点
  • 深度 (Depth)：节点到根节点的路径边数
  • 高度 (Height)：所有节点深度的最大值，也称为树的深度
  • 子树 (Subtree)：删除与父亲相连的边后，该节点所在的子图
交互演示 树的术语可视化
点击上方按钮查看不同术语的图示说明

特殊的树

链 (Chain)

所有节点度数不超过 2 的树。链可以看作是一条线性路径，是最”瘦长”的树结构。

PLAINTEXT
1 --- 2 --- 3 --- 4 --- 5

菊花图 / 星星 (Star)

除了一个中心节点外，其余所有节点都只与该中心节点相连。这是最”扁平”的树结构。

PLAINTEXT
    2
    |
4 - 1 - 3
    |
    5

二叉树

每个节点最多只有两个子节点的有根树，分为左子节点和右子节点。

二叉树的分类：

类型定义
完整二叉树每个节点的子节点数要么是 0，要么是 2
完全二叉树除最后一层外全满，且最后一层节点靠左排列
完美二叉树所有叶节点深度相同，所有非叶节点都有两个子节点
交互演示 特殊树类型
链 (Chain)：所有节点度数 ≤ 2，最"瘦长"的树结构

树的存储方式

只记录父节点

使用数组 parent[N] 记录每个节点的父节点。

CPP
int parent[N];
// parent[i] = j 表示节点 i 的父节点是 j

适用于需要自底向上递推的场景，但无法快速找到子节点。

邻接表

使用 std::vector 记录每个节点的所有相邻节点（无根树）或子节点（有根树）。

CPP
vector<int> adj[N];  // 无根树：存储所有相邻节点
vector<int> children[N];  // 有根树：只存储子节点

最常用的存储方式，支持高效的遍历操作。

左孩子右兄弟表示法

记录节点的第一个子节点和它的下一个兄弟节点，可以将任意多叉树转化为二叉树结构。

CPP
struct Node {
    int firstChild;   // 第一个子节点
    int nextSibling;  // 下一个兄弟节点
};

树的遍历

深度优先搜索 (DFS)

普通树 DFS

对于无向图形式的树，需要记录 from 参数避免重复访问：

CPP
void dfs(int u, int from) {
    for (int v : adj[u]) {
        if (v != from) {
            dfs(v, u);
        }
    }
}

二叉树的三种 DFS 遍历

遍历方式访问顺序
先序遍历 (Preorder)根 → 左 → 右
中序遍历 (Inorder)左 → 根 → 右
后序遍历 (Postorder)左 → 右 → 根

广度优先搜索 (BFS)

利用队列实现层序遍历，严格按照从上到下、从左到右的层级访问节点。

CPP
void bfs(int root) {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : children[u]) {
            q.push(v);
        }
    }
}
交互演示 树的遍历
遍历序列： -
未访问 正在访问 已访问

练习题推荐

第二部分：树的直径

树的直径（Tree Diameter）是树上任意两节点之间最长的简单路径。它是树论中最基础也最重要的问题之一，广泛应用于网络设计、路径规划等领域。

求解方法

求树的直径有两种时间复杂度为 O(n)O(n) 的经典方法：

方法一：两次 DFS

思路：从任意节点出发找到最远点 zz，再从 zz 出发找到最远点 z′z'，则 zz 到 z′z' 的路径即为直径。

原理证明：

  1. 设直径端点为 u,vu, v
  2. 从任意点 yy 出发，最远点 zz 一定是 uu 或 vv 之一（否则可构造更长的路径，矛盾）
  3. 再从 zz 出发找最远点，得到另一个端点
交互演示 两次 DFS 求直径
1 从任意点出发 DFS
2 找到最远点 z
3 从 z 出发 DFS
4 找到最远点 z'
直径： -

方法二：树形 DP

思路：对每个节点，计算从它向下延伸的最长链 d1d_1 和次长链 d2d_2（两条链不能共享边），直径即为所有 d1+d2d_1 + d_2 的最大值。

状态转移： d1[u]=max⁡(d1[v]+w(u,v))对所有子节点 vd_1[u] = \max(d_1[v] + w(u,v)) \quad \text{对所有子节点 } v d2[u]=次大值d_2[u] = \text{次大值}

交互演示 树形 DP 求直径
diameter = max(d₁ + d₂) d₁=最长链, d₂=次长链
节点 d₁ d₂ d₁+d₂

方法对比

特性两次 DFS树形 DP
时间复杂度O(n)O(n)O(n)O(n)
空间复杂度O(n)O(n)O(n)O(n)
负权边❌ 不支持✅ 支持
记录路径✅ 简单⚠️ 稍复杂
实现难度简单中等

重要性质：中点重合

当树上所有边权均为正数时，一个优美的性质成立：

所有直径的中点必定重合。

证明（反证法）： 设两条直径 u→vu \to v 和 u′→v′u' \to v' 的中点分别为 mm 和 m′m'，且 m≠m′m \neq m'。

由于两条直径长度相等，我们可以构造一条更长的路径：

  • 从 mm 出发沿直径到 uu
  • 再从 uu 通过公共部分到 u′u'
  • 最后从 u′u' 沿另一条直径到 v′v'

这样构造的路径长度必然大于原直径，矛盾！

交互演示 直径的中点重合

当边权为正时，所有直径的中点必定重合。

点击下方按钮查看不同直径。

代码实现

两次 DFS（C++）

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int dist[N], parent[N];

void dfs(int u, int fa, int d) {
    dist[u] = d;
    parent[u] = fa;
    for (int v : adj[u]) {
        if (v != fa) dfs(v, u, d + 1);
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 第一次 DFS
    dfs(1, -1, 0);
    int z = max_element(dist + 1, dist + n + 1) - dist;

    // 第二次 DFS
    dfs(z, -1, 0);
    int z2 = max_element(dist + 1, dist + n + 1) - dist;

    cout << "直径长度: " << dist[z2] << endl;

    // 输出直径路径
    vector<int> path;
    for (int u = z2; u != -1; u = parent[u]) {
        path.push_back(u);
    }
    // path 即为直径路径

    return 0;
}

树形 DP（C++）

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<pair<int,int>> adj[N]; // (邻点, 边权)
int d1[N], d2[N]; // 最长链、次长链
int diameter = 0;

void dp(int u, int fa) {
    d1[u] = d2[u] = 0;

    for (auto [v, w] : adj[u]) {
        if (v == fa) continue;

        dp(v, u);

        int d = d1[v] + w;
        if (d > d1[u]) {
            d2[u] = d1[u];
            d1[u] = d;
        } else if (d > d2[u]) {
            d2[u] = d;
        }
    }

    diameter = max(diameter, d1[u] + d2[u]);
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i < n; i++) {
        int u, v, w = 1;
        cin >> u >> v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dp(1, -1);
    cout << "直径长度: " << diameter << endl;

    return 0;
}

练习题推荐

题目难度说明
洛谷 B4016 树的直径↗⭐入门题，求直径长度
洛谷 P2491 消防↗⭐⭐⭐SDOI2011，直径上的最优选点
洛谷 P3629 巡逻↗⭐⭐⭐APIO2010，加边后的直径变化
LeetCode 1245. 树的直径↗⭐⭐无向树的直径

小结

  1. 两次 DFS 实现简单，方便记录路径，但不支持负权边
  2. 树形 DP 更通用，支持负权边，是竞赛中的首选方法
  3. 中点重合 是正权树的重要性质，可用于优化和证明

第三部分：树的重心

树的重心（Tree Centroid）是树论中的核心概念之一。删去重心后，树会被相对均匀地分割成若干部分，这一性质使其成为点分治（重心分解）算法的基础。

定义

如果在树中删去某个节点 vv 后，得到的每个连通分量的大小均不超过原树节点总数的一半，那么节点 vv 就是整棵树的重心。

重量：删去某节点后，得到的最大连通分量的大小称为该节点的重量。重心即重量不超过 n/2n/2 的节点。

交互演示 树的重心
当前选中： -
最大连通块： -
是否为重心： -

点击节点查看删除后的连通块大小

等价定义与性质

等价定义

重心有多种等价的描述方式：

等价定义说明
连通分量极值删去重心得到的最大连通分量是所有删点方案中最小的
距离和最小树中所有节点到重心的距离之和最小
有根树视角以重心为根时，任意真子树大小都不超过 n/2n/2
交互演示 距离和最小 = 重心
节点 距离和 状态

重心 = 距离和最小的节点

核心性质

性质 1：重心数量

一棵树最多有两个重心；如果有两个重心，它们必定相邻。

交互演示 双重心现象

一棵树最多有两个重心。

如果有两个重心，它们必定相邻。

橙色节点为重心

性质 2：动态稳定性

添加或删除一个叶子节点，新树的重心最多移动一条边的距离。

这一性质在动态维护重心时非常有用。

性质 3：合并性质

将两棵树通过一条边合并，新树的重心必在原来两棵重心之间的路径上。

重心的求法

方法：一次 DFS

通过一次 DFS 统计每个节点的子树大小，同时计算删去该节点后各连通块的最大值。

算法流程：

  1. DFS 遍历，计算每个节点 uu 的子树大小 size[u]
  2. 对于节点 uu，删去它后的连通块有：
    • 各子树：size[v]（vv 是 uu 的子节点）
    • 向上的部分：n - size[u]
  3. 取这些值的最大值作为 uu 的重量
  4. 重量 ≤n/2\le n/2 的节点即为重心
交互演示 DFS 求重心
size[u] = 1 + Σ size[v] up_size = n - size[u]
节点 size max_part 重心?

重心条件: max_part ≤ n/2

代码实现

C++ 模板

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int size_[N];      // 子树大小
int max_part[N];   // 删去该节点后的最大连通块
int n;
vector<int> centroids;

void dfs(int u, int fa) {
    size_[u] = 1;
    max_part[u] = 0;

    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        size_[u] += size_[v];
        max_part[u] = max(max_part[u], size_[v]);
    }

    // 向上的连通块
    max_part[u] = max(max_part[u], n - size_[u]);

    // 判断是否为重心
    if (max_part[u] <= n / 2) {
        centroids.push_back(u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);

    cout << "重心: ";
    for (int c : centroids) {
        cout << c << " ";
    }
    cout << endl;

    return 0;
}

换根 DP 方法

利用「距离和最小」的性质，通过两次 DFS 计算：

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int n, size_[N], dep[N];
long long dp[N];  // dp[u] = 以u为根的距离和

void dfs1(int u, int fa) {
    size_[u] = 1;
    dp[u] = dep[u];
    for (int v : adj[u]) {
        if (v == fa) continue;
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        size_[u] += size_[v];
        dp[u] += dp[v];
    }
}

void dfs2(int u, int fa) {
    for (int v : adj[u]) {
        if (v == fa) continue;
        dp[v] = dp[u] - size_[v] + (n - size_[v]);
        dfs2(v, u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs1(1, -1);
    dfs2(1, -1);

    // 距离和最小的节点即为重心
    int centroid = min_element(dp + 1, dp + n + 1) - dp;
    cout << "重心: " << centroid << endl;

    return 0;
}

经典应用

点分治（重心分解）

重心最重要的应用是点分治算法。每次选择子树的重心作为分治中心，可以保证：

  • 每层分治后子树大小不超过原来的一半
  • 递归深度为 O(log⁡n)O(\log n)
  • 总时间复杂度 O(nlog⁡n)O(n \log n)

例题：CF 359B Kay and Snowflake

求每棵子树的重心。

关键性质：子树的重心一定在其直接子节点子树的重心到该节点本身的路径上。

利用这一性质可以 O(n)O(n) 求出所有子树的重心。

练习题推荐

题目难度说明
洛谷 P1364 医院设置↗⭐距离和最小应用
CF 715C Digit Tree↗⭐⭐⭐点分治经典题
洛谷 P2634 聪聪可可↗⭐⭐⭐点分治入门

小结

要点内容
定义删去后最大连通块 ≤n/2\le n/2
等价定义距离和最小 / 子树大小都不超过 n/2n/2
数量最多 2 个，若有 2 个则相邻
求法一次 DFS，O(n)O(n)
应用点分治的核心基础

第四部分：最小生成树

最小生成树（Minimum Spanning Tree, MST）是图论中最经典的问题之一。给定一个带权无向连通图，最小生成树是一棵包含所有顶点、边权和最小的生成树。

核心定义

生成树：对于一个有 nn 个顶点的连通图，生成树是包含全部 nn 个顶点且恰好有 n−1n-1 条边的连通子图。

最小生成树：所有生成树中，边权总和最小的那一棵。

求解算法

求最小生成树有两种经典算法，都基于贪心策略：

Kruskal 算法

思想：将所有边按边权从小到大排序，依次尝试加入。如果某条边的两个端点不在同一个连通块内（用并查集判断），则加入该边，直到加入了 n−1n-1 条边。

算法步骤：

  1. 将所有边按边权排序
  2. 初始化并查集，每个节点自成一个集合
  3. 按顺序遍历每条边 (u,v,w)(u, v, w)：
    • 如果 find(u) != find(v)，则加入该边，执行 union(u, v)
    • 直到选了 n−1n-1 条边
交互演示 Kruskal 算法
边列表（按权重排序）
已选边数： 0 / 5
当前总权重： 0

点击"开始演示"查看 Kruskal 算法执行过程

时间复杂度：O(mlog⁡m)O(m \log m)，主要来自排序。适合稀疏图（边数较少）。

Prim 算法

思想：从任意一个节点开始，每次从未加入树的节点中，选择一个与已加入节点集合距离最近的节点加入，直到所有节点都被加入。

算法步骤：

  1. 选择一个起始节点加入集合 SS
  2. 维护每个节点到集合 SS 的最小距离
  3. 每次选择距离最小的未加入节点，加入 SS 并更新其他节点的距离
  4. 重复直到所有节点都加入
交互演示 Prim 算法
已加入集合 S
（空）
候选边
（空）
已加入节点： 0 / 6
当前总权重： 0

点击"开始演示"查看 Prim 算法执行过程

时间复杂度：

  • 朴素实现：O(n2)O(n^2)，适合稠密图
  • 堆优化：O(mlog⁡n)O(m \log n)

算法对比

特性KruskalPrim
时间复杂度O(mlog⁡m)O(m \log m)O(n2)O(n^2) 或 O(mlog⁡n)O(m \log n)
适用场景稀疏图稠密图
数据结构并查集优先队列
实现难度简单中等
思路从边出发从点出发

代码实现

Kruskal 算法（C++）

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int parent[N], rank_[N];

// 并查集查找（带路径压缩）
int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

// 并查集合并（按秩合并）
bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (rank_[x] < rank_[y]) swap(x, y);
    parent[y] = x;
    if (rank_[x] == rank_[y]) rank_[x]++;
    return true;
}

struct Edge {
    int u, v, w;
    bool operator<(const Edge& e) const { return w < e.w; }
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // 初始化并查集
    for (int i = 1; i <= n; i++) parent[i] = i;

    // Kruskal
    sort(edges.begin(), edges.end());
    int totalWeight = 0, edgeCount = 0;

    for (auto& e : edges) {
        if (unite(e.u, e.v)) {
            totalWeight += e.w;
            edgeCount++;
            cout << "选中边: " << e.u << " - " << e.v
                 << " (权重 " << e.w << ")" << endl;
            if (edgeCount == n - 1) break;
        }
    }

    if (edgeCount == n - 1) {
        cout << "最小生成树总权重: " << totalWeight << endl;
    } else {
        cout << "图不连通，无法生成最小生成树" << endl;
    }

    return 0;
}

Prim 算法（C++）

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const int INF = 1e9;

int n, m;
vector<pair<int, int>> adj[N]; // (邻点, 边权)
int minDist[N];   // 到已选集合的最小距离
int parent[N];    // 记录生成树的父节点
bool inMST[N];

int prim(int start) {
    fill(minDist, minDist + n + 1, INF);
    fill(inMST, inMST + n + 1, false);
    fill(parent, parent + n + 1, -1);

    minDist[start] = 0;
    int totalWeight = 0;

    for (int i = 0; i < n; i++) {
        // 找最小距离的未选节点
        int u = -1, minD = INF;
        for (int v = 1; v <= n; v++) {
            if (!inMST[v] && minDist[v] < minD) {
                minD = minDist[v];
                u = v;
            }
        }

        if (u == -1) break; // 图不连通

        inMST[u] = true;
        totalWeight += minDist[u];

        if (parent[u] != -1) {
            cout << "选中边: " << parent[u] << " - " << u
                 << " (权重 " << minDist[u] << ")" << endl;
        }

        // 更新邻接节点的最小距离
        for (auto [v, w] : adj[u]) {
            if (!inMST[v] && w < minDist[v]) {
                minDist[v] = w;
                parent[v] = u;
            }
        }
    }

    return totalWeight;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    int totalWeight = prim(1);
    cout << "最小生成树总权重: " << totalWeight << endl;

    return 0;
}

Prim 算法堆优化版本

CPP
int prim_heap(int start) {
    fill(minDist, minDist + n + 1, INF);
    fill(inMST, inMST + n + 1, false);

    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>> pq;

    minDist[start] = 0;
    pq.push({0, start});
    int totalWeight = 0, cnt = 0;

    while (!pq.empty() && cnt < n) {
        auto [d, u] = pq.top(); pq.pop();

        if (inMST[u]) continue;
        inMST[u] = true;
        totalWeight += d;
        cnt++;

        for (auto [v, w] : adj[u]) {
            if (!inMST[v] && w < minDist[v]) {
                minDist[v] = w;
                parent[v] = u;
                pq.push({w, v});
            }
        }
    }

    return totalWeight;
}

正确性证明

两种算法的正确性都可以通过切分定理（Cut Property）证明：

切分定理：将图的顶点集任意分成两个非空集合 SS 和 V−SV-S，则所有连接这两个集合的边中，权值最小的边一定在某个最小生成树中。

Kruskal：每次选择的边都是某个切分的最小边（因为按权重排序）。

Prim：每次选择的节点对应的边，就是当前切分的最小边。

练习题推荐

题目难度说明
洛谷 P3366 最小生成树↗⭐模板题
洛谷 P1547 Out of Hay↗⭐⭐最小生成树的最大边
洛谷 P2872 Roads↗⭐⭐构图 + MST
洛谷 P1991 无线通讯网↗⭐⭐⭐二分 + MST / 第 k 大边
LeetCode 1584. 连接所有点的最小费用↗⭐⭐构图 + Prim

小结

  1. Kruskal 从边出发，按权重排序后贪心选择，用并查集判环，适合稀疏图
  2. Prim 从点出发，逐步扩展生成树，类似 Dijkstra，适合稠密图
  3. 两种算法都基于贪心，正确性由切分定理保证
  4. 实际竞赛中，Kruskal 实现简单，是最常用的 MST 算法

总结

本文系统介绍了树论的核心内容：

专题核心要点
树基础无根树/有根树定义、术语、存储、DFS/BFS 遍历
树的直径两次 DFS（简单但不支持负权）、树形 DP（通用）
树的重心删去后最大连通块 ≤n/2\le n/2，点分治的基础
最小生成树Kruskal（稀疏图）、Prim（稠密图）

这些知识点环环相扣：树的遍历是基础算法，直径和重心是重要的树上结构性质，而最小生成树则是树在图论中的重要应用。掌握这些内容，将为解决更复杂的树论问题打下坚实基础。

Thanks for reading!

树基础（树的概念&直径&重心&最小生成树）

周五 3月 27 2026
5258 字 · 28 分钟
$ cd tech # algorithm # data-structure # tree # graph # mst # visualization

© LangQi99 | CC BY-NC-SA 4.0

分享这篇博客

X (Twitter) Telegram Reddit Facebook Email

目录