双亲表示法PTree 转 孩子兄弟表达式CSTree（严蔚敏《数据结构》6.66）

题目来源：严蔚敏《数据结构》C语言版本习题册 6.66

【题目】6.66
假设有n个结点的树T采用了双亲表示法，写出由此建立树的孩子-兄弟链表的算法。

【答案】

/*---------------------------------
 |6.66 双亲表示法-->孩子兄弟表达式|
 ---------------------------------*/
#define MAX_TREE_SIZE 50
typedef struct PTNode{
    TElemType data;
    int parent; //双亲的位置域
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;
}PTree;
CSTree CreateCSTreeByPTree(PTree T) {
    CSNode *tmp[MAX_TREE_SIZE]; //创建一个辅助的数组，仿照PTree结点的位置存放
    CSNode *p, *q;
    int i,parent;
    if (T.n<=0) return NULL;
    for (i=0; i<T.n; i++) { //双亲表按层序存储
        //创建新结点
        p = (CSNode *)malloc(sizeof(CSNode)); if(!p) exit(OVERFLOW);
        //赋值
        p->data = T.nodes[i].data;p->firstchild=p->nextsibling=NULL;
        //连接
        parent=T.nodes[i].parent; //父亲
        if (parent!=-1) { //不是根结点
            if (tmp[parent]->firstchild==NULL) tmp[parent]->firstchild=p; //第一个孩子
            else { //不是第一个孩子
                for (q=tmp[parent]->firstchild; q->nextsibling; q=q->nextsibling) ; //找到最后一个孩子
                q->nextsibling = p; //连接
            }
        }
        tmp[i]=p;
    }
    return tmp[0];
}

【完整代码】

/*-------------------
 |树-孩子兄弟表达法 |
 -------------------*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#ifndef BASE
#define BASE
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int bool;
#endif

#define TElemType char
typedef struct CSNode{
    TElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;



/*-------------------
 |6.59 输出T的所有边 |
 -------------------*/
void TreePrintEdge(CSTree T) {
    CSNode *p;
    for (p=T->firstchild; p; p=p->nextsibling) {
        printf("(%c,%c)\n", T->data, p->data); //输出T的孩子
        TreePrintEdge(p); //输出p的孩子
    }
}

/*-------------------------
 |6.60 统计叶子结点的个数 |
 -------------------------*/
int TreeLeafCnt(CSTree T) {
    // 树的叶子结点-->没有孩子
    int ret=0;
    CSNode *p;
    if (!T) return 0;
    else if (!T->firstchild) return 1;
    else {
        for (p=T->firstchild; p; p=p->nextsibling) ret += TreeLeafCnt(p);
        return ret;
    }
}


/*-------------------------
 |6.61 求树的度           |
 -------------------------*/
int TreeDegree(CSTree T) {
    // 最大的孩子数
    int max=-1;
    int cnt=0;
    CSNode *child;
    if (!T) return -1; //空树
    else if (!T->firstchild) return 0; //只有一个根结点，度为0
    else {
        for (cnt=0,child=T->firstchild; child; child=child->nextsibling) cnt++; //求自己的度
        max = cnt; //当前的最大值
        for (child=T->firstchild; child; child=child->nextsibling) {
            cnt = TreeDegree(child);
            if (cnt>max) max=cnt;
        }
        return max;
    }
}

/*-------------------------
 |6.62 求树的深度         |
 -------------------------*/
int TreeDepth(CSTree T) {
    int h1,h2;
    if (!T) return 0;
    else {
        h1 = TreeDepth(T->firstchild)+1; //T孩子的深度+1
        h2 = TreeDepth(T->nextsibling); //T兄弟的深度
        return h1>h2 ? h1 : h2;
    }
}

/*---------------------------------
 |6.66 双亲表示法-->孩子兄弟表达式|
 ---------------------------------*/
#define MAX_TREE_SIZE 50

typedef struct PTNode{
    TElemType data;
    int parent; //双亲的位置域
}PTNode;
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;
}PTree;
CSTree CreateCSTreeByPTree(PTree T) {
    CSNode *tmp[MAX_TREE_SIZE]; //创建一个辅助的数组，仿照PTree结点的位置存放
    CSNode *p, *q;
    int i,parent;

    if (T.n<=0) return NULL;
    for (i=0; i<T.n; i++) { //双亲表按层序存储
        //创建新结点
        p = (CSNode *)malloc(sizeof(CSNode)); if(!p) exit(OVERFLOW);
        //赋值
        p->data = T.nodes[i].data;p->firstchild=p->nextsibling=NULL;
        //连接
        parent=T.nodes[i].parent; //父亲
        if (parent!=-1) { //不是根结点
            if (tmp[parent]->firstchild==NULL) tmp[parent]->firstchild=p; //第一个孩子
            else { //不是第一个孩子
                for (q=tmp[parent]->firstchild; q->nextsibling; q=q->nextsibling) ; //找到最后一个孩子
                q->nextsibling = p; //连接
            }
        }
        tmp[i]=p;
    }

    return tmp[0];
}


int main() {
    PTree PT;
    CSTree CST;

    PT.n=10;PT.r=0;
    PT.nodes[0].data='R';PT.nodes[0].parent=-1;
    PT.nodes[1].data='A';PT.nodes[1].parent=0;
    PT.nodes[2].data='B';PT.nodes[2].parent=0;
    PT.nodes[3].data='C';PT.nodes[3].parent=0;
    PT.nodes[4].data='D';PT.nodes[4].parent=1;
    PT.nodes[5].data='E';PT.nodes[5].parent=1;
    PT.nodes[6].data='F';PT.nodes[6].parent=3;
    PT.nodes[7].data='G';PT.nodes[7].parent=6;
    PT.nodes[8].data='H';PT.nodes[8].parent=6;
    PT.nodes[9].data='I';PT.nodes[9].parent=6;

    CST = CreateCSTreeByPTree(PT);

    TreePrintEdge(CST);

    return 0;
}