c语言 30306：树的存储

解题思路:

注意事项:

参考代码:

#include <stdio.h>

#include <stdlib.h>

#define MAX_N 10000

// 邻接表节点结构体

typedef struct Node {

    int val;

    struct Node *next;

} Node;

// 邻接表头结构体

typedef struct AdjList {

    Node *head;

} AdjList;

// 图结构体，这里用它来表示树结构

typedef struct Graph {

    AdjList *array;

} Graph;

// 创建邻接表节点

Node *createNode(int v) {

    Node *newNode = (Node *)malloc(sizeof(Node));

    newNode->val = v;

    newNode->next = NULL;

    return newNode;

}

// 创建图（树）

Graph *createGraph(int n) {

    Graph *graph = (Graph *)malloc(sizeof(Graph));

    graph->array = (AdjList *)malloc((n + 1) * sizeof(AdjList));

    for (int i = 1; i <= n; i++) {

        graph->array[i].head = NULL;

    }

    return graph;

}

// 添加边，构建树的结构，这里是有向边（从u指向v）

void addEdge(Graph *graph, int u, int v) {

    Node *newNode = createNode(v);

    newNode->next = graph->array[u].head;

    graph->array[u].head = newNode;

}

// 释放邻接表节点内存

void freeList(Node *node) {

    Node *next;

    while (node!= NULL) {

        next = node->next;

        free(node);

        node = next;

    }

}

// 释放整个图（树）的邻接表内存

void freeGraph(Graph *graph, int n) {

    for (int i = 1; i <= n; i++) {

        freeList(graph->array[i].head);

    }

    free(graph->array);

    free(graph);

}

int main() {

    int n;

    scanf("%d", &n);

    Graph *graph = createGraph(n);

    // 构建树结构，这里简单按照输入边的方式，假设输入n-1条边

    for (int i = 0; i < n - 1; i++) {

        int u, v;

        scanf("%d %d", &u, &v);

        addEdge(graph, u, v);

    }

    // 按照要求输出每个节点的相关信息

    for (int i = 1; i <= n; i++) {

        Node *temp = graph->array[i].head;

        int son_count = 0;

        while (temp!= NULL) {

            son_count++;

            temp = temp->next;

        }

        printf("%d %d", i, son_count);

        temp = graph->array[i].head;

        while (temp!= NULL) {

            printf(" %d", temp->val);

            temp = temp->next;

        }

        printf("\n");

    }

    freeGraph(graph, n);

    return 0;

}