浅谈树的孩子表示法

树的孩子表示法存储普通树采用的是 "顺序表+链表" 的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，具体办法是，把每个节点的孩子结点排列起来，以单链表作为结构，则n个结点有n个孩子链表，如果该结点是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。

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

例如，使用孩子表示法存储左图中的普通树，则最终存储状态如下图所示：

以下是孩子表示法的结构定义代码：

/*树的孩子表示法结构定义*/

#define MAX_TRUE_SIZE 100

typedef struct CTNode     //孩子结点

{

    int child;

    struct CTNode *next;

} *ChildPtr;



typedef struct       //表头结构,内含该结点存放的数据和孩子链表的头指针

{

    TElemType data;

    ChildPtr firstchild;

} CTBox;



typedef struct        //树结构

{

    CTBox nodes[MAX_TREE_SIZE];   //结点数组

    int r,n;     //根的位置和结点数

} CTree;    

这样的结构，若要查找某个节点的某个孩子，或者找某个结点的兄弟，只需要查找这个节点的孩子单链表即可。对于遍历整棵树也很方便，对头结点的数组循环即可。

完整代码实现如下：

#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;

/**

 * @Description: 孩子表示法存储普通树

 * @Param: CTree tree 树的结构体变量

 * @Return: CTree tree 结构体变量

 * @Author: Carlos

 */

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;

}

/**

 * @Description:查找节点

 * @Param: CTree tree 树的结构体，char a 要查找的节点

 * @Return: 无

 * @Author: Carlos

 */

void FindKids(CTree tree,char a){

    int hasKids=0;

    for(int i=0;inext;

            while(p){

                hasKids = 1;

                //打印所有孩子节点 p->child 孩子节点在数组中的位置

                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;

}

使用树的孩子表示法存储的树结构，正好和双亲表示法相反，适用于查找某结点的孩子结点，不适用于查找其父结点，而双亲表示法找子结点比较困难。想要了解树的双亲表示法的小伙伴可以观看本站的数据结构和算法教程，学习其他类型的树的存储方式。