#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
 
 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
 
#define MAXSIZE 100    /* 存储空间初始分配量 */
 
typedef int Status;
 
typedef char TElemType; /* 假定二叉树的元素都是字符类型*/
TElemType Nil = ' ';
 
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
 
 
/* 模拟生成char数组， 用于构造二叉树所生产的数据***************/
int index$ = 1;
typedef char String[24];
String str;
 
/* 将chars 用String结构体表示*/
Status StrAssign(String S,char *chars)
{
    int i;
    if (strlen(chars) > MAXSIZE) {
        return ERROR; // 超过了最大容量
    } else {
        // 第一个位置存放字符串的长度
        S[0] = strlen(chars);
        for (i= 1; i < S[0]; i++) {
            S[i] = *(chars + i -1);
        }
 
        return OK;
    }
 
 
}
 
/* ******************************************************/
 
/* 构造空的的二叉树T */
Status InitBiTree(BiTree *T)
{
    *T = NULL;
    return OK;
}
 
/* 构造二叉树T， 使用的是递归创建的方法 */
void CreateBiTree(BiTree  *T)
{
 
 
    if (index$ == strlen(str)) // 所有的元素都分配完毕， 即结束
        return;
    TElemType ch = str[index$++];
 
 
    if (ch == '#') {
        // 碰到#号， 停止生成新的结点
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T){
            exit(OVERFLOW); // malloc失败
        }
 
        (*T)->data = ch; // 生成根节点
        CreateBiTree(&(*T)->lchild); // 构造左子树
        CreateBiTree(&(*T)->rchild); // 构造右子树
    }
 
 
}
 
/* 前序遍历*/
void PreOrderTraverse(BiTree *T)
{
    if (*T == NULL)
        return;
 
    printf("%c ",(*T)->data);
    PreOrderTraverse(&(*T)->lchild);
    PreOrderTraverse(&(*T)->rchild);
}
 
 
 
int main() {
 
    BiTree T;
    InitBiTree(&T);
 
    // 构造字符串
    StrAssign(str,"ABDH#K###E##CFI###G#J##");
 
 
    // 构造二叉树
    CreateBiTree(&T);
 
    PreOrderTraverse(&T);
 
 
    return 0;
}