将树（孩子兄弟链表CSTree）打印成树状（严蔚敏《数据结构》6.71）

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

【题目】6.71
假设树上每个结点所含的数据元素为一个字母，并且以孩子-兄弟链表为树的存储结构，试写一个按凹入表方式打印一棵树的算法。例如：左下所示树印为右下形状。

【思路】

1. 观察题目输出的序列ABEFCGD
2. 此为树的先根遍历—>对应为二叉树存储的先序遍历
3. 前面的空格是该结点所在的层数

【答案】

/*-----------------------------------------
 |6.71 以树状的形式输出                   |
 -----------------------------------------*/
void PrintAsTree(CSTree T,int i) {
    int cnt;
    if (T) {
        //输出空格
        for (cnt=1; cnt<i; cnt++) printf(" ");
        //输出字符
        visit(T->data);
        printf("\n");
        PrintAsTree(T->firstchild, i+1);
        PrintAsTree(T->nextsibling, i);
    }
}

【完整代码】可以运行

#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
void visit(TElemType e) {
    printf("%c ", e);
}
typedef struct CSNode{
    TElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

#define maxSize 50
/*-----------------------------------------
 |6.68 层次序列+每个结点的度-->构造CSTree |
 -----------------------------------------*/
CSTree CreateCSTreeByLevelDegree(char *levelstr, int *num) {
    int cnt,i,parent;
    CSNode *p;
    CSNode *tmp[maxSize];

    //先创建结点
    for (i=0; i < strlen(levelstr); ++i) {
        p = (CSNode *)malloc(sizeof(CSNode)); if (!p) exit(OVERFLOW);
        p->data = levelstr[i];p->firstchild=p->nextsibling=NULL;
        tmp[i]=p;
    }
    //连接
    parent=0; //孩子的爸爸
    cnt=0; //计数器：表示已经找了几个孩子
    i=1; //遍历结点，为他们找爸爸
    while (i<strlen(levelstr)) {
        if (num[parent]==0 || cnt==num[parent]) { //这个父亲没有孩子 || parent的孩子已经找完了
            cnt=0; //计数器归0
            parent++; //位移一位
            continue;
        }
        //这个父亲有孩子（i是parent的孩子）
        cnt++;
        if (cnt==1) { //i是parent的第一个孩子
            tmp[parent]->firstchild = tmp[i];
        } else { //不是第一个孩子
            tmp[i-1]->nextsibling = tmp[i]; //它是前面的兄弟
        }

        i++;
    }

    return tmp[0];
}

/*-----------------------------------------
 |6.71 以树状的形式输出                   |
 -----------------------------------------*/
void PrintAsTree(CSTree T,int i) {
    /*思路：
        1. 观察题目输出的序列ABEFCGD
        2. 此为树的先根遍历-->对应为二叉树存储的先序遍历
        3. 前面的空格是该结点所在的层数
    */
    int cnt;
    if (T) {
        //输出空格
        for (cnt=1; cnt<i; cnt++) printf(" ");
        //输出字符
        visit(T->data);
        printf("\n");

        PrintAsTree(T->firstchild, i+1);
        PrintAsTree(T->nextsibling, i);
    }
}
int main() {
/*6.71输出成树状
测试数据一：
RABCDEFGHI
3 2 0 1 0 0 3 0 0 0
测试数据二：
ABCDEFG
3 2 1 0 0 0 0
*/
    CSTree CST;
    char levelstr[50]; //层次遍历的序列
    int num[50]; //每个结点的度
    int i;


    scanf("%s", levelstr); //输入层次序列
    for (i=0; i<strlen(levelstr); i++) scanf("%d", &num[i]); //每个结点的度
    CST = CreateCSTreeByLevelDegree(levelstr, num); //6.68

    PrintAsTree(CST, 1); //6.71

    return 0;
}