4、5阶B-树，除了根和叶子结点外，每个结点至少包含_____________个关键字。

在B树中，每个结点包含的关键字个数是有范围的，这个范围可以用一个参数m来表示，称为B树的阶。

对于5阶B树，它的每个结点除了根和叶子结点外至少包含2个关键字。这是因为，B树的性质之一是，除根结点外，每个结点至少包含m/2个关键字，且至多包含m个关键字。

因为5阶B树中，每个结点至少包含2个关键字，所以每个结点至多包含5-1=4个关键字。

相关问题

已知一棵树的由根至叶子结点按层次输入的结点序列及每个结点的度，试写出构造此树的孩子-兄弟链表的c语言算法

假设输入的结点序列为nodeList，每个结点的度为degreeList，孩子-兄弟链表为treeList，算法如下：

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

#define MAX_NODE_NUM 100 // 最大结点数

typedef struct TreeNode {
    int data;
    struct TreeNode *firstChild; // 第一个孩子结点
    struct TreeNode *nextSibling; // 下一个兄弟结点
} TreeNode;

TreeNode *createTree(int nodeList[], int degreeList[], int n) {
    TreeNode *treeList[MAX_NODE_NUM];
    int i, j;
    for (i = 0; i < n; i++) {
        TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
        node->data = nodeList[i];
        node->firstChild = NULL;
        node->nextSibling = NULL;
        treeList[i] = node;
    }
    TreeNode *root = treeList[0];
    TreeNode *queue[MAX_NODE_NUM];
    int front = 0, rear = 0;
    queue[rear++] = root;
    for (i = 1; i < n;) {
        TreeNode *parent = queue[front];
        front++;
        for (j = 0; j < degreeList[i]; j++) {
            parent->firstChild = treeList[i];
            i++;
            treeList[i - 1]->nextSibling = treeList[i];
            queue[rear++] = treeList[i - 1];
        }
    }
    return root;
}

void printTree(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        printTree(root->firstChild);
        printTree(root->nextSibling);
    }
}

int main() {
    int nodeList[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int degreeList[] = {2, 3, 0, 2, 0, 0, 1, 0, 0, 0};
    int n = sizeof(nodeList) / sizeof(int);
    TreeNode *root = createTree(nodeList, degreeList, n);
    printTree(root);
    return 0;
}

算法思路：

1. 根据结点序列和度数数组创建结点数组treeList，并初始化每个结点的firstChild和nextSibling指针为NULL。
2. 将第一个结点作为根节点，并加入队列中。
3. 从第二个结点开始，按输入顺序一次遍历每个结点，对于每个结点，将其作为其父节点的孩子结点，并将其加入队列中，直到所有结点都被遍历完毕。
4. 返回根节点。

时间复杂度为O(n)，空间复杂度为O(n)。

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

以下是构造孩子-兄弟链表的C语言代码：

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

#define MAXN 100005

typedef struct TreeNode {
    int data;
    struct TreeNode *firstChild;
    struct TreeNode *nextSibling;
} TreeNode;

TreeNode nodes[MAXN];
int degree[MAXN];

int buildTree(int n) {
    int root = -1;
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &nodes[i].data, &degree[i]);
        if (degree[i] == 0) continue;
        int firstChild = -1;
        for (int j = 0; j < degree[i]; ++j) {
            int child;
            scanf("%d", &child);
            if (firstChild == -1) {
                nodes[i].firstChild = &nodes[child];
                firstChild = child;
            } else {
                nodes[firstChild].nextSibling = &nodes[child];
                firstChild = child;
            }
        }
        if (root == -1) root = i;
    }
    return root;
}

void dfs(TreeNode *u, int path[], int depth) {
    path[depth] = u->data;
    if (u->firstChild == NULL) {
        for (int i = 0; i <= depth; ++i) {
            printf("%d ", path[i]);
        }
        printf("\n");
    }
    for (TreeNode *v = u->firstChild; v; v = v->nextSibling) {
        dfs(v, path, depth + 1);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int root = buildTree(n);
    int path[MAXN];
    dfs(&nodes[root], path, 0);
    return 0;
}

输入格式：

第一行一个整数 $n$，表示节点数。

接下来 $n$ 行，每行两个整数 $x$ 和 $k$，表示节点编号和该节点的度数，然后紧随其后 $k$ 个整数，表示该节点的 $k$ 个子节点编号。

输出格式：

若该树有 $m$ 个叶子结点，则输出 $m$ 行，每行是一条从根到叶子结点的路径，然后按照先序遍历的方式输出每一行。

样例输入：

7
0 4 1 2 3 4
1 2 5 6
2 0
3 1 7
4 0
5 0
6 0

样例输出：

0 1 5
0 1 6
0 2
0 3 7