作者：解学武

前面学习了如何用双亲表示法存储普通树，本节再学习一种存储普通树的方法——孩子表示法。

孩子表示法存储普通树采用的是 "顺序表+链表" 的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点。需要注意，与双亲表示法不同的是，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。

如果节点没有孩子节点（叶子节点），则该节点的链表为空链表。

例如，使用孩子表示法存储图 1a) 中的普通树，则最终存储状态如图 1b) 所示：
图 1 所示转化为 C 语言代码为：

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 20
#define TElemType char
//孩子表示法
typedef struct CTNode {
    int child;//链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标
    struct CTNode* next;
}ChildPtr;
typedef struct {
    TElemType data;//结点的数据类型
    ChildPtr* firstchild;//孩子链表的头指针
}CTBox;
typedef struct {
    CTBox nodes[MAX_SIZE];//存储结点的数组
    int n, r;//结点数量和树根的位置
}CTree;
//孩子表示法存储普通树
void initTree(CTree* tree) {
    int i, num;
    printf("从根结点开始输入各个结点的值：\n");
    for (i = 0; i < tree->n; i++) {
        printf("--输入第 %d 个节点的值：", i + 1);
        scanf("%c", &(tree->nodes[i].data));
        tree->nodes[i].firstchild = NULL;
        printf("----输入节点 %c 的孩子节点数量：", tree->nodes[i].data);
        scanf("%d", &num);
        if (num != 0) {
            tree->nodes[i].firstchild = (ChildPtr*)malloc(sizeof(ChildPtr));
            tree->nodes[i].firstchild->next = NULL;
            printf("------输入第 1 个孩子结点在顺序表中的位置：");
            scanf("%d", &(tree->nodes[i].firstchild->child));
            ChildPtr* p = tree->nodes[i].firstchild;
            for (int j = 1; j < num; j++) {
                ChildPtr* newEle = (ChildPtr*)malloc(sizeof(ChildPtr));
                newEle->next = NULL;
                printf("------输入第 %d 个孩子节点在顺序表中的位置：", j + 1);
                scanf("%d", &(newEle->child));
                p->next = newEle;
                p = p->next;
            }
        }
        scanf("%*[^\n]"); scanf("%*c");
    }
}
//找某个结点的孩子
void findKids(CTree tree, char a) {
    int i, hasKids = 0;
    for (i = 0; i < tree.n; i++) {
        if (tree.nodes[i].data == a) {
            ChildPtr* p = tree.nodes[i].firstchild;
            while (p) {
                hasKids = 1;
                printf("%c ", tree.nodes[p->child].data);
                p = p->next;
            }
            break;
        }
    }
    if (hasKids == 0) {
        printf("此节点为叶子节点");
    }
}
//释放各个链表占用的内存
void deleteTree(CTree tree) {
    int i;
    //逐个遍历链表
    for (i = 0; i < tree.n; i++) {
        ChildPtr* p = tree.nodes[i].firstchild;
        //释放链表中的各个结点
        while (p) {
            ChildPtr* next = p;
            p = p->next;
            free(next);
        }
    }
}
int main()
{
    CTree tree = { 0 };
    tree.n = 10;
    tree.r = 0;
    initTree(&tree);
    printf("找出节点 F 的所有孩子节点：");
    findKids(tree, 'F');
    deleteTree(tree);
    return 0;
}

程序运行结果为：

从根结点开始输入各个结点的值：
--输入第 1 个节点的值：R
----输入节点 R 的孩子节点数量：3
------输入第 1 个孩子结点在顺序表中的位置：1
------输入第 2 个孩子节点在顺序表中的位置：2
------输入第 3 个孩子节点在顺序表中的位置：3
--输入第 2 个节点的值：A
----输入节点 A 的孩子节点数量：2
------输入第 1 个孩子结点在顺序表中的位置：4
------输入第 2 个孩子节点在顺序表中的位置：5
--输入第 3 个节点的值：B
----输入节点 B 的孩子节点数量：0
--输入第 4 个节点的值：C
----输入节点 C 的孩子节点数量：1
------输入第 1 个孩子结点在顺序表中的位置：6
--输入第 5 个节点的值：D
----输入节点 D 的孩子节点数量：0
--输入第 6 个节点的值：E
----输入节点 E 的孩子节点数量：0
--输入第 7 个节点的值：F
----输入节点 F 的孩子节点数量：3
------输入第 1 个孩子结点在顺序表中的位置：7
------输入第 2 个孩子节点在顺序表中的位置：8
------输入第 3 个孩子节点在顺序表中的位置：9
--输入第 8 个节点的值：G
----输入节点 G 的孩子节点数量：0
--输入第 9 个节点的值：H
----输入节点 H 的孩子节点数量：0
--输入第 10 个节点的值：K
----输入节点 K 的孩子节点数量：0
找出节点 F 的所有孩子节点：G H K

总结

使用孩子表示法存储的树结构，正好和双亲表示法相反，查找孩子结点的效率很高，而不擅长做查找父结点的操作。

我们还可以将双亲表示法和孩子表示法合二为一，那么图 1a) 中普通树的存储效果如图 2 所示：
使用图 2 结构存储普通树，既能快速找到指定节点的父节点，又能快速找到指定节点的孩子节点。该结构的实现方法很简单，只需整合这两节的代码即可，这里不再赘述。
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。