首页 > 代码库 > PAT1004 Counting Leaves (30) 数组链式建树

PAT1004 Counting Leaves (30) 数组链式建树

一开始尝试用二叉树,最后用结构

struct node{
int k;
int son[101];
};

son[i]记录子结点

#include<stdio.h>#include<string.h>struct node{    int k;    int son[101];};int height(struct node tree[],int root){//家族最大的代数     if(tree[root].k==0)    return 1;    else{        int max=0;        for(int i=0;i<tree[root].k;i++)        if(max<height(tree,tree[root].son[i]))        max=height(tree,tree[root].son[i]);        return max+1;    }}int salve(struct node tree[],int level,int root){    if(tree[root].k!=0&&level==1)    return 0;    else if(level==1)    return 1;    else{        int max=0;        for(int i=0;i<tree[root].k;i++){        max+=salve(tree,level-1,tree[root].son[i]);        }        return max;    }};int main(){    struct node tree[101];    memset(tree,0,101*sizeof(struct node));    int n,m,id,k,count;//0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes.    scanf("%d%d",&n,&m);        for(int i1=0;i1<m;i1++){//输入m行,建树 ????有问题         scanf("%d%d",&id,&k);        tree[id].k=k;        for(int i2=0;i2<tree[id].k;i2++){            scanf("%d",&tree[id].son[i2]);        }    }        int max=height(tree,01);        for(int i=1;i<=max;i++){        if(i!=1)        printf(" %d",salve(tree,i,01));        else        printf("%d",salve(tree,i,01));          }        return 0;} 

   

PAT1004 Counting Leaves (30) 数组链式建树