樹(shù)的孩子表示法存儲(chǔ)普通樹(shù)采用的是 "順序表+鏈表" 的組合結(jié)構(gòu)，其存儲(chǔ)過(guò)程是：從樹(shù)的根節(jié)點(diǎn)開(kāi)始，使用順序表依次存儲(chǔ)樹(shù)中各個(gè)節(jié)點(diǎn)，具體辦法是，把每個(gè)節(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，以單鏈表作為結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，如果該結(jié)點(diǎn)是葉子結(jié)點(diǎn)則此單鏈表為空。然后n個(gè)頭指針又組成一個(gè)線性表，采用順序存儲(chǔ)結(jié)構(gòu)，存放進(jìn)一個(gè)一維數(shù)組中。

需要注意的是，與雙親表示法不同，孩子表示法會(huì)給各個(gè)節(jié)點(diǎn)配備一個(gè)鏈表，用于存儲(chǔ)各節(jié)點(diǎn)的孩子節(jié)點(diǎn)位于順序表中的位置。

如果節(jié)點(diǎn)沒(méi)有孩子節(jié)點(diǎn)（葉子節(jié)點(diǎn)），則該節(jié)點(diǎn)的鏈表為空鏈表。

例如，使用孩子表示法存儲(chǔ)左圖中的普通樹(shù)，則最終存儲(chǔ)狀態(tài)如下圖所示：

以下是孩子表示法的結(jié)構(gòu)定義代碼：

/*樹(shù)的孩子表示法結(jié)構(gòu)定義*/

#define MAX_TRUE_SIZE 100

typedef struct CTNode ????//孩子結(jié)點(diǎn)

{

????int child;

????struct CTNode *next;

} *ChildPtr;



typedef struct ??????//表頭結(jié)構(gòu),內(nèi)含該結(jié)點(diǎn)存放的數(shù)據(jù)和孩子鏈表的頭指針

{

????TElemType data;

????ChildPtr firstchild;

} CTBox;



typedef struct ???????//樹(shù)結(jié)構(gòu)

{

????CTBox nodes[MAX_TREE_SIZE]; ??//結(jié)點(diǎn)數(shù)組

????int r,n; ????//根的位置和結(jié)點(diǎn)數(shù)

} CTree; ???

這樣的結(jié)構(gòu)，若要查找某個(gè)節(jié)點(diǎn)的某個(gè)孩子，或者找某個(gè)結(jié)點(diǎn)的兄弟，只需要查找這個(gè)節(jié)點(diǎn)的孩子單鏈表即可。對(duì)于遍歷整棵樹(shù)也很方便，對(duì)頭結(jié)點(diǎn)的數(shù)組循環(huán)即可。

完整代碼實(shí)現(xiàn)如下：

#include

#include

#define MAX_SIZE 20

#define TElemType char

typedef struct CTNode{

    //鏈表中每個(gè)結(jié)點(diǎn)存儲(chǔ)的不是數(shù)據(jù)本身，而是數(shù)據(jù)在數(shù)組中存儲(chǔ)的位置下標(biāo)！！

    int child;

    struct CTNode * next;

}ChildPtr;

typedef struct {

    //結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型

    TElemType data;

    //孩子鏈表的頭指針

    ChildPtr* firstchild;

}CTBox;

typedef struct{

    //存儲(chǔ)結(jié)點(diǎn)的數(shù)組

    CTBox nodes[MAX_SIZE];

    //結(jié)點(diǎn)數(shù)量和樹(shù)根的位置

    int n,r;

}CTree;

/**

 * @Description: 孩子表示法存儲(chǔ)普通樹(shù)

 * @Param: CTree tree 樹(shù)的結(jié)構(gòu)體變量

 * @Return: CTree tree 結(jié)構(gòu)體變量

 * @Author: Carlos

 */

CTree InitTree(CTree tree){

    printf("輸入節(jié)點(diǎn)數(shù)量：\n");

    scanf("%d",&(tree.n));

    for(int i=0;inext=NULL;



        printf("輸入節(jié)點(diǎn) %c 的孩子節(jié)點(diǎn)數(shù)量：\n",tree.nodes[i].data);

        int Num;

        scanf("%d",&Num);

        if(Num!=0){

            //帶頭結(jié)點(diǎn)的鏈表

            ChildPtr * p = tree.nodes[i].firstchild;

            for(int j = 0 ;jnext=NULL;

                printf("輸入第 %d 個(gè)孩子節(jié)點(diǎn)在順序表中的位置",j+1);

                scanf("%d",&(newEle->child));

                p->next= newEle;

                p=p->next;

            }

        }

    }

    return tree;

}

/**

 * @Description:查找節(jié)點(diǎn)

 * @Param: CTree tree 樹(shù)的結(jié)構(gòu)體，char a 要查找的節(jié)點(diǎn)

 * @Return: 無(wú)

 * @Author: Carlos

 */

void FindKids(CTree tree,char a){

    int hasKids=0;

    for(int i=0;inext;

            while(p){

                hasKids = 1;

                //打印所有孩子節(jié)點(diǎn) p->child 孩子節(jié)點(diǎn)在數(shù)組中的位置

                printf("%c ",tree.nodes[p->child].data);

                p=p->next;

            }

            break;

        }

    }

    if(hasKids==0){

        printf("此節(jié)點(diǎn)為葉子節(jié)點(diǎn)");

    }

}



int main()

{

    CTree tree;

    tree = InitTree(tree);

    //默認(rèn)數(shù)根節(jié)點(diǎn)位于數(shù)組notes[0]處

    tree.r=0;

    printf("找出節(jié)點(diǎn) F 的所有孩子節(jié)點(diǎn)：");

    FindKids(tree,'F');

    return 0;

}

使用樹(shù)的孩子表示法存儲(chǔ)的樹(shù)結(jié)構(gòu)，正好和雙親表示法相反，適用于查找某結(jié)點(diǎn)的孩子結(jié)點(diǎn)，不適用于查找其父結(jié)點(diǎn)，而雙親表示法找子結(jié)點(diǎn)比較困難。想要了解樹(shù)的雙親表示法的小伙伴可以觀看本站的數(shù)據(jù)結(jié)構(gòu)和算法教程，學(xué)習(xí)其他類(lèi)型的樹(shù)的存儲(chǔ)方式。