91.png

    1. /*
    2.     从所给的树的层次遍历及其节点度数，构造孩子兄弟链表
    3.     分析：
    4.         这里设计到层次遍历，还有孩子-兄弟链表，较为复杂。我们可以设立一个类型为树节点的数组，
    5.         将层次序列里面的所有值放到该数组中，将其所有节点的fch和sub值为空
    6.         然后一次去遍历节点，取出度数d，若d>0,说明该节点有孩子，将第一个孩子放到左指针fch，其他孩子
    7.         一次放到sub中，注意这里会有变化，代码里再详说
    8. */
    9. typedef struct node {
    10.     char data;
    11.     node *fch, *nsib;
    12. }Tree;
    13. #include<stdio.h>
    14. #include <stdlib.h>
    15. void createCSTree_degree(char *level, int *degree, node **pointer, int n) {
    16.     int k = 0;//判断到了哪个节点
    17.     for (int i = 0; i < n; i++) {//初始化pointer
    18.         pointer[i]->data = level[i];
    19.         pointer[i]->fch = NULL;
    20.         pointer[i]->nsib = NULL;
    21.     }
    22.     for (int i = 0; i < n; i++) {
    23.         int d = degree[i];
    24.         if (d) {
    25.             k++;//k为子女节点序号
    26.             pointer[i]->fch = pointer[k];
    27.             for (int j = 0; j < d - 1; j++) {
    28.                 k++;
    29.                 pointer[k - 1]->nsib = pointer[k];
    30.             }
    31.         }
    32.     }
    34. }
    35. void inOrder(node *T) {
    36.     if (T) {
    37.         inOrder(T->fch);
    38.         printf("%c ", T->data);
    39.         inOrder(T->nsib);
    40.     }
    41. };
    42. int main() {
    43.     char level[6] = { 'A','B','E','G','D','F' };//层次遍历，用数组存储
    44.     int degree[] = { 3,2,0,0,0,0 };
    45.     node* *pointer = (node* *)malloc(sizeof(node*) * 6);
    46.     for (int i = 0; i < 6; i++) {
    47.         pointer[i] = (node*)malloc(sizeof(node*));
    48.     }
    49.     createCSTree_degree(level, degree, pointer, 6);
    50.     inOrder(pointer[0]);
    51. }