/* 二叉樹中序遍歷的遞歸算法*/

#include<stdlib.h>
#include<stdio.h>

typedef char DataType;

struct BinTreeNode;                         /* 二叉樹中結點 */
typedef struct BinTreeNode *PBinTreeNode;   /* 結點的指針類型 */

struct BinTreeNode {
    DataType  info;                         /* 數據域 */
    PBinTreeNode  llink;                    /* 指向左子女 */
    PBinTreeNode  rlink;                    /* 指向右子女 */
};

typedef struct BinTreeNode *BinTree;
typedef BinTree *PBinTree;
typedef PBinTreeNode BNode;

PBinTreeNode root_btree(PBinTree t) {
    return *t;
}

PBinTreeNode leftChild_btree (PBinTreeNode p){
    return p->llink;
}

PBinTreeNode rightChild_btree (PBinTreeNode p){
    return p->rlink;
}

/*以下算法就是先將二叉樹擴充為擴充的二叉樹，
然后按先根次序周游的順序輸入結點的信息,
生成一個雙鏈存儲的二叉樹的過程*/
PBinTreeNode createRest_BTree() {
    /* 遞歸創建從根開始的二叉樹 */
    PBinTreeNode  pbnode;
    char ch;
    scanf("%c",&ch);
    if ( ch == '@') pbnode = NULL;
    else {
        pbnode = (PBinTreeNode )malloc(sizeof(struct BinTreeNode));
        if (pbnode == NULL) {
            printf("Out of space!\n");
            return pbnode;
        }
        pbnode->info = ch;
        pbnode->llink = createRest_BTree();	/* 構造左子樹 */
        pbnode->rlink = createRest_BTree();	/* 構造右子樹 */
    }
    return pbnode;
}


PBinTree  create_BTree( void ) {
    /* 創建完整的二叉樹 */
    PBinTree pbtree = (PBinTree)malloc(sizeof(BinTree));
    if (pbtree != NULL)
        *pbtree = createRest_BTree( );  /* 遞歸創建從根開始的二叉樹 */
    return pbtree; 
}

void visit(BNode p) { printf("%c ",p->info); }

void inOrder(BNode p) {
    if (p == NULL) return;
    inOrder(leftChild_btree(p));
    visit(p);
    inOrder(rightChild_btree(p));
}


int main(){
    PBinTree tree = create_BTree();
    inOrder(*tree);
    putchar('\n');
    return 0;
}