树的中心
定义
在树中，如果节点 𝑥x
作为根节点时，从 𝑥x 出发的最长链最短，那么称 𝑥x 为这棵树的中心．
性质
- 树的中心不一定唯一，但最多有 22 个，且这两个中心是相邻的．
- 树的中心一定位于树的直径上．
- 树上所有点到其最远点的路径一定交会于树的中心．
- 当树的中心为根节点时，其到达直径端点的两条链分别为最长链和次长链．
- 当通过在两棵树间连一条边以合并为一棵树时，连接两棵树的中心可以使新树的直径最小．
- 树的中心到其他任意节点的距离不超过树直径的一半．
求法
寻找一个点 𝑥x，使其作为根节点时，最长链的长度最短．
具体步骤
- 维护 𝑙𝑒𝑛1𝑥len1x，表示节点 𝑥x 子树内的最长链．
- 维护 𝑙𝑒𝑛2𝑥len2x，表示不与 𝑙𝑒𝑛1𝑥len1x 重叠的最长链．
- 维护 𝑢𝑝𝑥upx，表示节点 𝑥x 子树外的最长链，该链必定经过 𝑥x 的父节点．
- 找到点 𝑥x 使得 max(𝑙𝑒𝑛1𝑥,𝑢𝑝𝑥)max(len1x,upx) 最小，那么 𝑥x 即为树的中心．
参考代码
---|---
### 示例
假设我们有一棵树，如下所示：
---|---
- 树的直径为 𝐷 →𝐵 →𝐴 →𝐶 →𝐹D→B→A→C→F．直径长度为 44．
- 树的中心为节点 𝐴A，因为从 𝐴A 出发的最长链（到 𝐷D 或 𝐹F）均为 22．
- 如果将 𝐵B 或 𝐶C 作为树的根，则从这些节点出发的最长链将增加，因此它们不是树的中心．
时间复杂度
上述算法的时间复杂度为 𝑂(𝑛)O(n)，其中 𝑛n 是树中节点的数量．
参考
- TutorialsPoint: Centers of a Tree
- ProofWiki: Definition of Center of Tree
- Wikipedia: Tree (graph theory)
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：littleparrot12345, Tiphereth-A 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用