/* 二叉树对称根周游的递归算法*/

#include<malloc.h>
#include<stdio.h>

struct BinTreeNode;                         /* 二叉树中结点 */
typedef struct BinTreeNode *PBinTreeNode;   /* 结点的指针类型 */

struct BinTreeNode {
    char  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_BTree1()  /* 递归创建从根开始的二叉树 */
{
   PBinTreeNode  pbnode;

    char ch;

    scanf("%c",&ch);

    if (ch == '#')
        
    { pbnode = NULL;}

   else {
        pbnode = (PBinTreeNode )malloc(sizeof(struct BinTreeNode));

        pbnode->info = ch;

        pbnode->llink = createRest_BTree1();    /* 构造左子树 */

        pbnode->rlink = createRest_BTree1();    /* 构造右子树 */
   }
    return pbnode;
}
PBinTree  create_BTree( void ) {
    /* 创建完整的二叉树 */
    PBinTree pbtree = (PBinTree)malloc(sizeof(BinTree));
    if (pbtree != NULL)
        *pbtree = createRest_BTree1() ; /* 递归创建从根开始的二叉树 */
    return pbtree;
}

void visit(BNode p)

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

void inOrderzhong(BNode p) //中根次序周游的递归算法
{
    if (p == NULL) return;
    inOrderzhong(leftChild_btree(p));
    visit(p);
    inOrderzhong(rightChild_btree(p));
}

void inOrderxian(BNode p)

{ if(p==NULL) return;

   visit(p);

   inOrderxian(leftChild_btree(p));

   inOrderxian(rightChild_btree(p));
}

void inOrderhou(BNode p)

{if(p==NULL) return;

  inOrderhou(leftChild_btree(p));
 
   inOrderhou(rightChild_btree(p));

   visit(p);
}



int main()
{   printf("请创建树：\n");
    PBinTree tree = create_BTree();
    printf("请选择周游的方式\n 1为先根 2为中根 3为后根\n");

    int a;
    scanf("%d",&a);
   switch(a)
   {case 1:inOrderxian(*tree);break;
    case 2:inOrderzhong(*tree);break;
    case 3:inOrderhou(*tree);
   }
   
    putchar('\n');
    return 0;
}