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

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

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

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

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

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

#define MAX_TRUE_SIZE 100

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

{

????int child;

????struct CTNode *next;

} *ChildPtr;



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

{

????TElemType data;

????ChildPtr firstchild;

} CTBox;



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

{

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

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

} CTree; ???

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

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

#include

#include

#define MAX_SIZE 20

#define TElemType char

typedef struct CTNode{

    //鏈表中每個結(jié)點存儲的不是數(shù)據(jù)本身，而是數(shù)據(jù)在數(shù)組中存儲的位置下標！！

    int child;

    struct CTNode * next;

}ChildPtr;

typedef struct {

    //結(jié)點的數(shù)據(jù)類型

    TElemType data;

    //孩子鏈表的頭指針

    ChildPtr* firstchild;

}CTBox;

typedef struct{

    //存儲結(jié)點的數(shù)組

    CTBox nodes[MAX_SIZE];

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

    int n,r;

}CTree;

/**

 * @Description: 孩子表示法存儲普通樹

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

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

 * @Author: Carlos

 */

CTree InitTree(CTree tree){

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

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

    for(int i=0;inext=NULL;



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

        int Num;

        scanf("%d",&Num);

        if(Num!=0){

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

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

            for(int j = 0 ;jnext=NULL;

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

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

                p->next= newEle;

                p=p->next;

            }

        }

    }

    return tree;

}

/**

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

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

 * @Return: 無

 * @Author: Carlos

 */

void FindKids(CTree tree,char a){

    int hasKids=0;

    for(int i=0;inext;

            while(p){

                hasKids = 1;

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

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

                p=p->next;

            }

            break;

        }

    }

    if(hasKids==0){

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

    }

}



int main()

{

    CTree tree;

    tree = InitTree(tree);

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

    tree.r=0;

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

    FindKids(tree,'F');

    return 0;

}

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