C语言实现树的最大高度问题：寻找最佳树根

问题描述：

在图论中，树是任意两个顶点间有且只有一条路径的图。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。

有一个根的树叫做有根树。

有根树中的节点可以根据到根的距离分层。一棵有根数的层数叫做这棵树的高度。

我们知道，只要确定树根，就可以构造出一棵树。

选取不同的结点当作树根可以构造不同树高的树，你的任务就是选取编号最小的结点，使得以该结点为树根的树的高度最大。

输入：

输入数据的第一行为一个整数N (2<=N<=100,000)，表示树的结点数量，结点编号分别为1，2，3，…，N。之后有N-1行，每行有两个整数A和B，表示A结点和B结点之间有一条边。输入数据保证可以构造出一棵有根树。

有多组测试数据，输入以EOF结束。

输出：

输出两个整数minNode和Hight，表示以编号minNode为树根的树的最大高度为Hight，如果存在多种情况使得高度Hight最大，输出编号最小的minNode。

样例输入：

样例输出：

6 5

思路：

任选一个结点为根，遍历整棵树，找到离该根结点最远的结点，将其设为新的根，再次遍历整棵树，找到离新根结点最远的结点，输出该结点和距离即为所求。

代码：

#include <stdio.h>
#include <stdlib.h>
#define MAXN 100005

int n, head[MAXN], cnt;
int depth[MAXN], vis[MAXN];

struct Edge {
    int to, next;
}edge[MAXN * 2];

void addEdge(int u, int v) {
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void dfs(int u, int fa, int dep) {
    depth[u] = dep;
    vis[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa && !vis[v]) {
            dfs(v, u, dep + 1);
        }
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        cnt = 0;
        for (int i = 1; i <= n; i++) {
            head[i] = -1;
            depth[i] = 0;
            vis[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }
        // 从结点1开始遍历
        dfs(1, -1, 1);
        int maxNode = 1, maxHeight = depth[1];
        // 找到离根结点最远的结点
        for (int i = 2; i <= n; i++) {
            if (depth[i] > maxHeight) {
                maxHeight = depth[i];
                maxNode = i;
            }
        }
        // 将最远结点设为新的根
        for (int i = 1; i <= n; i++) {
            vis[i] = 0;
        }
        dfs(maxNode, -1, 1);
        // 再次遍历，找到新的根结点下的最远结点
        maxHeight = depth[maxNode];
        for (int i = 1; i <= n; i++) {
            if (depth[i] > maxHeight) {
                maxHeight = depth[i];
                maxNode = i;
            }
        }
        printf("%d %d\n", maxNode, maxHeight);
    }
    return 0;
}

代码解析：

使用邻接表存储树的边信息。
使用深度优先搜索(DFS)遍历树，计算每个结点到根结点的距离(深度)。
首先从结点1开始遍历，找到离根结点最远的结点。
将最远结点设为新的根，再次进行DFS遍历，找到新的根结点下的最远结点。
最终输出最远结点和距离。

优化建议：

可以使用更快的遍历算法，例如广度优先搜索(BFS)，进一步提高效率。
可以使用更简洁的代码结构，例如使用递归函数进行DFS遍历。
可以添加更多测试用例，验证代码的正确性和鲁棒性。

总结：

本文介绍了使用C语言实现树的最大高度问题，并提供了详细的代码实现和优化建议。通过学习本文，可以加深对树的结构和遍历算法的理解，并掌握使用C语言解决实际问题的技巧。