前面学习了如何用双亲表示法存储普通树,本节再学习一种存储普通树的方法——孩子表示法。
孩子表示法存储普通树采用的是 "顺序表+链表" 的组合结构,其存储过程是:从树的根节点开始,使用顺序表依次存储树中各个节点,需要注意的是,与双亲表示法不同,孩子表示法会给各个节点配备一个链表,用于存储各节点的孩子节点位于顺序表中的位置。
例如,使用孩子表示法存储图 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;
//孩子表示法存储普通树
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;
}
程序运行结果为:
使用孩子表示法存储的树结构,正好和双亲表示法相反,适用于查找某结点的孩子结点,不适用于查找其父结点。
其实,我们还可以将双亲表示法和孩子表示法合二为一,那么图 1a) 中普通树的存储效果如图 2所示:
使用图 2 结构存储普通树,既能快速找到指定节点的父节点,又能快速找到指定节点的孩子节点。该结构的实现方法很简单,只需整合这两节的代码即可,因此不再赘述。