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

思路：

枚举每个节点做根节点，然后求出该节点为根节点的树的高度，最后找到最大高度的节点即可。判断树高度可以使用DFS或BFS。

代码：

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

int n, head[MAXN], cnt, dep[MAXN], maxDep, minNode;
struct edge {
    int to, next;
} e[MAXN << 1];

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

void dfs(int u, int fa, int d) {
    dep[u] = d;
    if (d > maxDep) {
        maxDep = d;
        minNode = u;
    }
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v != fa) {
            dfs(v, u, d + 1);
        }
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        cnt = 0;
        for (int i = 1; i <= n; i++) head[i] = 0;
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }
        maxDep = 0;
        minNode = 1;
        for (int i = 1; i <= n; i++) {
            dfs(i, 0, 1);
        }
        printf("%d %d\n", minNode, maxDep);
    }
    return 0;
}

代码解析：

addEdge 函数用于添加边，使用邻接表存储图。
dfs 函数用于深度优先搜索，计算每个节点为根节点的树的高度。
在 main 函数中，首先读取输入数据，然后枚举每个节点作为根节点，调用 dfs 函数计算树的高度，最后输出高度最大的节点。

总结：

本篇文章介绍了如何使用C语言解决树的最大高度问题，并给出了相应的代码实现。该代码使用了DFS算法，遍历所有节点，找到高度最大的树根节点。这是一种常见的图论问题，可以用来解决各种与树相关的应用问题。