C++树的重心和直径 求解C语言中树的中心节点与最长路径(2)

C++树的重心和直径

枚举所有节点，计算删除每一个节点后所有子树中的最大节点数量。从结果可知，只有当删除节点1后，得到子树的最大值是最小的，故节点1为此树的重心。

重心的特点：

• 树的重心如果不唯一，则至多有两个，且这两个重心相邻。如下图所示，节点3和7都是树的重心，且在树上是相邻的。

• 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
• 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
• 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
• 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

查找树重心的算法思想：

直观来讲，删除一节点后，计算所有子树的最大值。但是，具体如何实施？

如删除节点3后，从逻辑上讲，整棵树被分成两个部分。节点3的子树部分和其它部分。

以节点3为根节点，使用DFS搜索算法，可以容易得到子树以及以3为根节点的树的节点数量，因为整棵树的节点数量是已知，如果知道了以节点3为根节点的子树的节点数，则其它部分的节点数量可以轻松计算出来：整棵树的节点数n-以3为根节点的子树的数量。

当然，在此过程中，需要记录最大值。如下图所示，最大值为5。