stillcare
前面学习了如何用双亲表示法存储普通树，本节再学习一种存储普通树的方法——孩子表示法。
孩子表示法存储普通树采用的是 "顺序表链表" 的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。
如果节点没有孩子节点（叶子节点），则该节点的链表为空链表。
例如，使用孩子表示法存储图 1a) 中的普通树，则最终存储状态如图 1b) 所示：
图 1 孩子表示法存储普通树示意图
图 1 所示转化为 c 语言代码为：
#include#include #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; //孩子表示法存储普通树 ctree inittree(ctree tree) { printf("输入节点数量：\n"); scanf("%d", &(tree.n)); for (int i = 0; i < tree.n; i ) { printf("输入第 %d 个节点的值：\n", i 1); getchar(); scanf("%c", &(tree.nodes[i].data)); tree.nodes[i].firstchild = (childptr*)malloc(sizeof(childptr)); tree.nodes[i].firstchild->next = null; printf("输入节点 %c 的孩子节点数量：\n", tree.nodes[i].data); int num; scanf("%d", &num); if (num != 0) { childptr * p = tree.nodes[i].firstchild; for (int j = 0; 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; } } } return tree; } void findkids(ctree tree, char a) { int haskids = 0; for (int i = 0; i < tree.n; i ) { if (tree.nodes[i].data == a) { childptr * p = tree.nodes[i].firstchild->next; while (p) { haskids = 1; printf("%c ", tree.nodes[p->child].data); p = p->next; } break; } } if (haskids == 0) { printf("此节点为叶子节点"); } } int main() { ctree tree; for (int i = 0; i < max_size; i ) { tree.nodes[i].firstchild = null; } tree = inittree(tree); //默认数根节点位于数组notes[0]处 tree.r = 0; printf("找出节点 f 的所有孩子节点："); findkids(tree, 'f'); return 0; }
程序运行结果为：
输入节点数量：
10
输入第 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 双亲孩子表示法
使用图 2 结构存储普通树，既能快速找到指定节点的父节点，又能快速找到指定节点的孩子节点。该结构的实现方法很简单，只需整合这两节的代码即可，因此不再赘述。
