树的孩子表示法
此前介绍过用双亲表示法存储普通树，本篇文章将讲解另一种存储普通树的方法...
另一种方法是孩子表示法！！！
孩子表示法存储普通树采用的是：顺序表和链表的组合结构
其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置（而双亲表示法会配置一个整型变量，用来保存双亲的位置）
如果节点没有孩子节点（叶子节点），则该节点的链表为空链表
例如，使用孩子表示法存储下图左侧的普通树，则最终存储状态如下图右侧所示：
通过上图右侧的存储状态，我们就能很容易声明某些节点：
typedef struct CTNode{
int child; // 代表孩子结点的索引位置
struct CTNode *next; // 指向下一个孩子结点
} ChildPtr;
typedef struct{
char data; // 结点数据域
ChildPtr *firstchild; // 孩子链表的头指针
} CTBox;
typedef struct{
CTBox nodes[MAX_SIZE]; // 存储结点的数组
int n, r; // 结点数量和树根位置
} CTree;树的孩子表示法的代码实现
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 20
typedef struct CTNode{
int child; // 代表孩子结点的索引位置
struct CTNode *next; // 指向下一个孩子结点
} ChildPtr;
typedef struct{
char 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));
// 孩子链表头指针有值，但是在主函数中已经将指针指向 NULL了，此处重新在堆区申请
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 = newEle;
}
}
}
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(void){
CTree tree;
for(int i = 0; i < MAX_SIZE; i++){
tree.nodes[i].firstchild = NULL;
tree.nodes[i].data = ' ';
}
tree = initTree(tree);
// 默认数根节点位于数组 notes[0]处
tree.r = 0;
findKids(tree, 'F');
return 0;
}树的孩子和双亲表示法结合的介绍及代码实现（优化）
先谈一下孩子双亲表示法！！！
使用孩子表示法存储的树结构，正好和双亲表示法相反，适用于查找某结点的孩子结点，不适用于查找其父结点，如果可以将双亲表示法和孩子表示法合二为一！！！
例如，使用孩子表示法结合双亲表示法存储此前的普通树，则最终存储状态如下图所示：
?通过上图的存储状态，我们就能很容易声明某些节点：
typedef struct CTNode{
int child; // 代表孩子结点的索引位置
struct CTNode *next; // 指向下一个孩子结点
} ChildPtr;
typedef struct{
char data; // 结点数据域
int parent; // 保存双亲的位置
ChildPtr *firstchild; // 孩子链表的头指针
} CTBox;
typedef struct{
CTBox nodes[MAX_SIZE]; // 存储结点的数组
int n, r; // 结点数量和树根位置
} CTree;
?再谈其具体代码实现！！！
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 20
typedef struct CTNode{
int child; // 代表孩子结点的索引位置
struct CTNode *next; // 指向下一个孩子结点
} ChildPtr;
typedef struct{
char data; // 结点数据域
int parent; // 保存双亲的位置
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);
printf("请输入第 %d 个结点的值和其双亲位于数组中的位置下标:\n", i+1);
getchar();
scanf("%c %d", &(tree.nodes[i].data), &(tree.nodes[i].parent));
// 孩子链表头指针有值，但是在主函数中已经将指针指向 NULL了，此处重新在堆区申请
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 = newEle;
}
}
}
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("此节点为叶子节点");
}
}
// 查找某结点的双亲结点
void FindParent(CTree tree){
char a;
int isfind = 0; // 是否找到的标志
printf("请输入要查询的结点值:\n");
getchar(); // 作用： 读取回车符
scanf("%c", &a); // F
for(int i = 0; i < tree.n; i++){
if(tree.nodes[i].data == a){
isfind = 1;
int ad = tree.nodes[i].parent;
printf("%c的父节点为 %c,存储位置下标为 %d", a, tree.nodes[ad].data, ad);
break;
}
}
if(isfind == 0){
printf("树中无此节点");
}
}
int main(void){
CTree tree;
for(int i = 0; i < MAX_SIZE; i++){
tree.nodes[i].firstchild = NULL;
tree.nodes[i].data = ' ';
}
tree = initTree(tree);
// 默认数根节点位于数组 notes[0]处
tree.r = 0;
findKids(tree, 'F');
FindParent(tree);
return 0;
}