用c语言求树的高度(数据结构)题目描述一棵树有n个节点,其中1号节点为根节点.输入格式第一行是整数n,表示节点数后面若干行,每行两个整数a b,表示b是a的子节点.输出求这棵树的高度(根
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/04 02:29:57
![用c语言求树的高度(数据结构)题目描述一棵树有n个节点,其中1号节点为根节点.输入格式第一行是整数n,表示节点数后面若干行,每行两个整数a b,表示b是a的子节点.输出求这棵树的高度(根](/uploads/image/z/5170576-40-6.jpg?t=%E7%94%A8c%E8%AF%AD%E8%A8%80%E6%B1%82%E6%A0%91%E7%9A%84%E9%AB%98%E5%BA%A6%EF%BC%88%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%EF%BC%89%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0%E4%B8%80%E6%A3%B5%E6%A0%91%E6%9C%89n%E4%B8%AA%E8%8A%82%E7%82%B9%2C%E5%85%B6%E4%B8%AD1%E5%8F%B7%E8%8A%82%E7%82%B9%E4%B8%BA%E6%A0%B9%E8%8A%82%E7%82%B9.%E8%BE%93%E5%85%A5%E6%A0%BC%E5%BC%8F%E7%AC%AC%E4%B8%80%E8%A1%8C%E6%98%AF%E6%95%B4%E6%95%B0n%2C%E8%A1%A8%E7%A4%BA%E8%8A%82%E7%82%B9%E6%95%B0%E5%90%8E%E9%9D%A2%E8%8B%A5%E5%B9%B2%E8%A1%8C%2C%E6%AF%8F%E8%A1%8C%E4%B8%A4%E4%B8%AA%E6%95%B4%E6%95%B0a+b%2C%E8%A1%A8%E7%A4%BAb%E6%98%AFa%E7%9A%84%E5%AD%90%E8%8A%82%E7%82%B9.%E8%BE%93%E5%87%BA%E6%B1%82%E8%BF%99%E6%A3%B5%E6%A0%91%E7%9A%84%E9%AB%98%E5%BA%A6%EF%BC%88%E6%A0%B9)
用c语言求树的高度(数据结构)题目描述一棵树有n个节点,其中1号节点为根节点.输入格式第一行是整数n,表示节点数后面若干行,每行两个整数a b,表示b是a的子节点.输出求这棵树的高度(根
用c语言求树的高度(数据结构)
题目描述
一棵树有n个节点,其中1号节点为根节点.
输入格式
第一行是整数n,表示节点数
后面若干行,每行两个整数a b,表示b是a的子节点.
输出
求这棵树的高度(根节点为第1层)
样例输入
5
1 2
1 3
3 4
3 5
样例输出
3
用c语言求树的高度(数据结构)题目描述一棵树有n个节点,其中1号节点为根节点.输入格式第一行是整数n,表示节点数后面若干行,每行两个整数a b,表示b是a的子节点.输出求这棵树的高度(根
#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;
}