树的重心总结

树的重心也叫树的质心

定义

找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心 。[ 子树最大者最小 ]
解释
子树最大针对的是去除当前结点，剩余最大的部分
子树最小针对的是剩余最大部分在总体所有情形是最少的

性质

树的重心有下面几条常见性质：
定义1：找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心。
定义2：以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。
性质1：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
性质2：把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
性质3：把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

实例说明

例如下图的 C 为重心

判断原因

1. ABCDEFG，每次选择一个结点做根，并将其去除，找到其剩余部分的最大值
2. 找出每种情形的最大值，所有情形最大值中的最小值 ，那个情形的根就是重心

• 解释
  • 如下图将A去除，剩余部分最大的数量就是**CEFG ，其数量为 4**
  • 如下图将C去除，剩余部分最大的数量就是ABD，其数量为 3
  • 通过验证不难发现，C为根的值3是最小的，故C为重心