（3）已知一棵树的由根至叶子结点按层次输入的结点序列及每个结点的度（每层中自左至右输入），试写出构造此树的孩子-兄弟链表的算法。输入：一个正整数N结点数；然后输入N行，每行输入两个数字，中间用空格分开，代表节点及其对应的度。输出：若该树有M个叶结点，则输出M行，每行是一条从根到叶子结点的路径，然后按照先序遍历的方式输出每一行用c语言实现

以下是用C语言实现的算法：

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

typedef struct node {
    int data;
    struct node *first_child;
    struct node *next_sibling;
} Node;

// 创建一个节点
Node *create_node(int data, int degree) {
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->first_child = NULL;
    new_node->next_sibling = NULL;

    if (degree > 0) {
        Node *p = new_node, *q;
        for (int i = 0; i < degree - 1; i++) {
            q = (Node*)malloc(sizeof(Node));
            q->data = -1;
            q->first_child = NULL;
            q->next_sibling = NULL;
            p->next_sibling = q;
            p = q;
        }
        q = (Node*)malloc(sizeof(Node));
        q->data = -1;
        q->first_child = NULL;
        q->next_sibling = NULL;
        p->next_sibling = q;
    }

    return new_node;
}

// 根据输入的层次遍历序列和度数构造树
Node *construct_tree(int n) {
    Node *root = NULL;
    Node *queue[n];
    int front = 0, rear = 0;
    int data, degree;

    // 输入根节点
    printf("请输入根节点：");
    scanf("%d %d", &data, &degree);
    root = create_node(data, degree);
    queue[rear++] = root;

    // 输入其他节点
    for (int i = 1; i < n; i++) {
        Node *parent = queue[front];
        front++;

        printf("请输入节点%d的信息：", i);
        scanf("%d %d", &data, &degree);

        Node *p = create_node(data, degree);
        parent->first_child = p;
        queue[rear++] = p;

        for (int j = 1; j < degree; j++) {
            printf("请输入节点%d的信息：", i+j);
            scanf("%d %d", &data, &degree);

            Node *q = create_node(data, degree);
            p->next_sibling = q;
            p = q;
            queue[rear++] = q;
        }
    }

    return root;
}

// 输出从根到叶子的路径
void print_path(Node *root, int path[], int path_len) {
    if (root == NULL) {
        return;
    }

    // 将当前节点的值加入路径
    path[path_len] = root->data;
    path_len++;

    // 如果当前节点是叶子节点，输出路径
    if (root->first_child == NULL) {
        for (int i = 0; i < path_len; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
    } else {
        // 否则递归遍历子节点
        print_path(root->first_child, path, path_len);
        Node *p = root->first_child->next_sibling;
        while (p != NULL) {
            print_path(p, path, path_len);
            p = p->next_sibling;
        }
    }
}

int main() {
    int n;
    printf("请输入节点数：");
    scanf("%d", &n);

    Node *root = construct_tree(n);

    // 统计叶子节点数
    int count = 0;
    Node *p = root;
    while (p != NULL) {
        if (p->first_child == NULL) {
            count++;
        }
        p = p->next_sibling;
    }

    // 输出从根到叶子的路径
    int path[count];
    print_path(root, path, 0);

    return 0;
}

输入格式：

请输入节点数：9
请输入根节点：1 3
请输入节点1的信息：2 2
请输入节点2的信息：4 0
请输入节点3的信息：3 1
请输入节点4的信息：5 0
请输入节点5的信息：6 1
请输入节点6的信息：7 1
请输入节点7的信息：8 0
请输入节点8的信息：9 0

输出格式：

1 2 4
1 2
1 3 5
1 3 6 7 8 9