樹的孩子表示法存儲普通樹采用的是 "順序表+鏈表" 的組合結構，其存儲過程是：從樹的根節點開始，使用順序表依次存儲樹中各個節點，具體辦法是，把每個節點的孩子結點排列起來，以單鏈表作為結構，則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;

}

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