[科普中国]-孩子链表示法

孩子链表示法是树的一种存储方式，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。如果节点没有孩子节点（叶子节点），则该节点的链表为空链表。

定义孩子链表示法是指同一双亲的孩子链成单链，每个节点带有指向孩子链的指针。树的所有结点都有唯一的父节点，但是每个结点都有不确定数量的子结点1。每个结点由三部分组成：存储数据元素值的数据部分、指向它的第一个子结点的指针、指向它的兄弟结点的指针。孩子链表示法是树最常用的存储方式。2

孩子表示法也用一组连续的存储空间来存放树的所有结点，每个空间存放一个结点的信息；但是附加信息不再存放本结点的双亲结点的位置信息，而是存放本结点的孩子结点的位置信息。由于树的结点可能会有多个孩子结点，因此孩子结点的位置信息无法直接存放，可以把每个结点的孩子结点的位置信息排列起来成为一个线性表，以单链表作为存储结构（这样n个结点就有n个孩子链表），每个结点的附加信息里存放上本结点的孩子链表的地址信息3。

#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;inext=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 ;jnext=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;inext; while(p){ hasKids = 1; printf("%c ",tree.nodes[p->child].data); p=p->next; } break; } } if(hasKids==0){ printf("此节点为叶子节点"); }}int main(){ CTree tree; tree = initTree(tree); //默认数根节点位于数组notes[0]处 tree.r=0; printf("找出节点 F 的所有孩子节点："); findKids(tree,'F'); return 0;}树在计算机科学中，树（tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。它具有以下的特点：

1、每个节点都只有有限个子节点或无子节点；

2、没有父节点的节点称为根节点；

3、每一个非根节点有且只有一个父节点；

4、除了根节点外，每个子节点可以分为多个不相交的子树；

5、树里面没有环路(cycle)。

双亲表示法与孩子兄弟表示法双亲表示法，树的一种存储方式。让每个结点记住其父结点的位置。存储数据元素的结点由两部分组成：存储数据元素值的数据字段，以及存储父结点位置的父指针字段。树的所有结点可存放在一个数组中（称“静态双亲表示法”），也可组织成一个链表（称“动态双亲表示法”）。双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。

孩子兄弟表示法就是既表示出每个结点的第一个孩子结点，也表示出每个结点的下一个兄弟结点。孩子兄弟表示法需要为每个结点设计三个域：一个数据元素域、一个指向该结点的第一个孩子结点的指针域、一个指向该结点的下一个兄弟结点的指针域。孩子兄弟表示法的最大优点是可以方便地实现树和二叉树的相互转换，但是它的缺点也和孩子表示法的缺点一样：就是从当前结点查找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找4。

本词条内容贡献者为:

徐恒山 - 讲师 - 西北农林科技大学