2029: 获取树的规模（C语言）

解题思路:

    见代码及注释。

注意事项:

参考代码:

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

// 树结点结构体
typedef struct node {
    struct node *father;
    struct node *child[5];
    int child_count;
} Node;

// 递归计算树的规模
int treeSize(Node *node) {
    int total = 1;
    for (int i = 0; i < node->child_count; i++) {
        total += treeSize(node->child[i]);
    }
    return total;
}

// 创建一个新的树结点
Node *createNode() {
    Node *nd = (Node *) malloc(sizeof(Node));
    nd->father = NULL;
    nd->child_count = 0;
    return nd;
}

int main() {
    int n;
    scanf("%d", &n);

    // 存放所有树结点的数组
    Node *nodes[n + 1];
    for (int i = 0; i < n + 1; i++) {
        nodes[i] = NULL;
    }
    int fi, si;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &fi, &si);

        // si为空
        if (nodes[si] == NULL) {
            nodes[si] = createNode();
        }

        // fi为0，说明当前si为根结点
        if (fi == 0) {
            nodes[si]->father = NULL;
            continue;
        }

        // fi为空
        if (nodes[fi] == NULL) {
            nodes[fi] = createNode();
        }

        // 设置父结点指针
        nodes[si]->father = nodes[fi];

        // 当前si是否在fi的子结点中
        int find = -1;
        for (int j = 0; j < nodes[fi]->child_count; j++) {
            if (nodes[fi]->child[j] == nodes[si]) {
                find = j;
                break;
            }
        }
        if (find != -1) {
            break;
        }
        // 将si的指针存到fi的孩子结点指针数组中
        nodes[fi]->child[nodes[fi]->child_count++] = nodes[si];
    }
    int k;
    scanf("%d", &k);

    // 找到指定结点所在树的根结点
    Node *root = nodes[k];
    while (root->father != NULL) {
        root = root->father;
    }

    // 计算树的规模大小
    int size = treeSize(root);
    printf("%d\n", size);

    // 释放
    for (int i = 0; i < n + 1; i++) {
        free(nodes[i]);
    }
    return 0;
}