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算法，计算每个点为根的树高度。具体来说，需要维护一个dis数组表示每个点到根的距离，初始值为0。在DFS过程中，对于当前节点，其子节点的dis值为当前节点的dis值加一。因此，需要在DFS过程中传递一个参数表示当前节点的dis值。对于叶子节点，即没有子节点的节点，其树高度为0。计算完以每个点为根的树高度后，再遍历一遍数组，找到最大的树高度，然后找到对应的最小编号。注意，本题有多组测试数据，在读入数据时需要使用while循环。

参考代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 100005

int n, head[MAXN], tot;
int dis[MAXN], height[MAXN];

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

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

void dfs(int u, int fa, int d) {
    dis[u] = d;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa) {
            dfs(v, u, d + 1);
        }
    }
    height[u] = d;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        tot = 0;
        memset(head, -1, sizeof(head));
        memset(dis, 0, sizeof(dis));
        memset(height, 0, sizeof(height));
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }
        for (int i = 1; i <= n; i++) {
            dfs(i, 0, 0);
        }
        int minNode = 1, maxHeight = height[1];
        for (int i = 2; i <= n; i++) {
            if (height[i] > maxHeight) {
                maxHeight = height[i];
                minNode = i;
            } else if (height[i] == maxHeight && i < minNode) {
                minNode = i;
            }
        }
        printf("%d %d\n", minNode, maxHeight);
    }
    return 0;
}

代码解析：

使用addEdge函数添加边，head数组存储每个节点的邻接表头指针。
使用dfs函数进行深度优先搜索，dis数组记录每个节点到根的距离，height数组记录以每个节点为根的树高度。
在main函数中，先读取输入数据，然后对每个节点进行DFS，最后遍历height数组找到最大高度和对应的最小编号。

总结：

通过上述代码和分析，我们可以使用C语言编程，通过DFS算法求解树的最大高度和根节点。该算法简单易懂，效率较高，可以应用于解决类似的图论问题。