用c语言求树的高度（数据结构）

Question

题目描述

一棵树有n个节点，其中1号节点为根节点。

输入格式

第一行是整数n，表示节点数
后面若干行，每行两个整数a b，表示b是a的子节点。

输出

求这棵树的高度（根节点为第1层）

样例输入
5
1 2
1 3
3 4
3 5
样例输出
3

Answer 1

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
}Link;

void insertNode(Link *head, int data) {
    Link *p = head;
    Link *q = (Link *)malloc(sizeof(Link));
    q->data = data;
    q->next = NULL;
    while(p->next != NULL) p=p->next;
    p->next = q;
}
void freeNode(Link *head) {
    Link *p = head->next;
    Link *q;
    head->next = NULL;
    while(p != NULL){
        q = p;
        p=p->next;
        free(q);
    }
}

int deep(Link ** tree, int start) {
    int depth = 1;
    Link *p;
    if(tree[start]->next == NULL) {
        return depth;
    }
    p= tree[start]->next;
    while(p!= NULL){
        int tmp = deep(tree, p->data - 1);
        if(tmp > depth) depth = tmp;
        p=p->next;
    }

    return depth + 1;
}

int main(){
    int count, i;
    int a, b;
    Link **tree;
    
    scanf("%d", &count);
    tree = (Link **)malloc(sizeof(Link*)*count);
    for(i=0;i<count;++i) {
        tree[i] = (Link *)malloc(sizeof(Link));
        tree[i]->next = NULL;
    }
    while((scanf("%d%d",&a, &b))!=EOF){
        if(a>0 && b>0) {
            insertNode(tree[a-1], b);
        }
    }
    printf("%d\n", deep(tree, 0));
    for(i=0;i<count;++i) {
        freeNode(tree[i]);
        free(tree[i]);
    }
    free(tree);
    return 0;
}

追问

亲，能详细说明一下你的代码吗？我是新手对链表不是特别熟

追答

tree[i]，i=0-n放父节点，它后面的链表放每个直接子节点，例如1 2
1 3

tree[0]放的是1，它后面的链表放的是2和3

算法就是 从1开始递归查找每个子节点的树高，取最大值，