按树形状打印二叉树（严蔚敏《数据结构》6.69）

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

【题目】6.69
假设以二叉链表存储的二叉树中，每个结点所含数据元素均为单字母，试编写算法，按树形状打印二叉树的算法。例如：左下二叉树印为右下形状。

【思路】

1. 观察例子—>打印的顺序为：CFEADB
2. 顺序肯定与递归顺序有关—>写出三种递归序列
   - 先序：ABDCEF—>没有发现规律
   - 中序：BDAEFC—>发现将此序列逆序，就成了打印的顺序CFEADB
3. 前面的空格—>与层数有关—>层数为i—>空格就有i-1个

【答案】

void PrintAsTree(BiTree T, int i) { //i代表所在层次
    int j;
    if (T) {
        PrintAsTree(T->rchild, i+1); //访问右子树
        for (j=0; j<i-1; ++j) printf(" ");
        printf("%c\n",    T->data);
        PrintAsTree(T->lchild, i+1); //访问左子树
    }
}

【完整代码】

#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 //固定为char，若修改需要修改方法
typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
void visit(TElemType e) {
    printf("%c", e);
}


Status PreCreate(BiTree *pT); // 先序遍历创建二叉树

// 6.69 按树状打印
/* 思考：
    1. 观察例子-->打印的顺序为：CFEADB
    2. 顺序肯定与递归顺序有关-->写出三种递归序列
        - 先序：ABDCEF-->没有发现规律
        - 中序：BDAEFC-->逆序即是打印的顺序
    3. 前面的空格-->与层数有关-->层数为i-->空格就有i-1个
*/
void PrintAsTree(BiTree T, int i) { //i代表所在层次
    int j;
    if (T) {
        PrintAsTree(T->rchild, i+1); //访问右子树

        for (j=0; j<i-1; ++j) printf(" ");
        printf("%c\n",    T->data);

        PrintAsTree(T->lchild, i+1); //访问左子树
    }
}

int main() {
/* 6.69
AB#D##CE#F###
*/

    BiTree T;

    PreCreate(&T);

    PrintAsTree(T, 1);
    return 0;
}

// 先序遍历创建二叉树
Status PreCreate(BiTree *pT) {
    char ch;
    scanf("%c", &ch);
    if ('#' == ch ) *pT=NULL;
    else {
        *pT = (BiTNode *)malloc(sizeof(BiTNode));
        if (!*pT) exit(OVERFLOW);
        (*pT)->data = ch;
        PreCreate( &(*pT)->lchild );
        PreCreate( &(*pT)->rchild );
    }
    return OK;
}