#include <stdlib.h>
#include <stdio.h>
#define Maxsize 100
#define OK 1
#define OVERFLOW -2
typedef struct BinNode                        //定义二叉树结构
{
        char data;
        struct BinNode        *lchild,*rchild;
} BinNode, *BinTree;

int CreateBinTree(BinTree *Tree)
{
        char ch;
        scanf("%c",&ch);
        if(ch == '.')
                (*Tree) = NULL;
        else
        {
                if(!((*Tree) = (BinTree)malloc(sizeof(BinNode))))
                        exit(OVERFLOW);
                (*Tree)->data = ch;
                CreateBinTree(&((*Tree)->lchild));
                CreateBinTree(&((*Tree)->rchild));
        }
        return OK;
}//CreateBiTree

void Preorder (BinTree T)
{
        BinNode *stack[Maxsize],*p;
        int top;
        if(T)
        {
                top=1;             //根结点入栈
                stack[top]=T;
                while(top>0)
                {
                        p=stack[top]; //退栈并访问该结点
                        top--;
                        printf("%c",p->data);
                        if(p->rchild)   //右孩子入栈
                        {
                                top++;
                                stack[top]=p->rchild;
                        }
                        if(p->lchild)   //左孩子入栈
                        {
                                top++;
                                stack[top]=p->lchild;
                        }
                }
        }
}

void Inorder(BinTree T)
{
        BinNode *stack[Maxsize],*p;
        int top=0;
        p=T;
        do
        {
                while(p)             //扫描左结点
                {
                        top++;
                        stack[top]=p;
                        p=p->lchild;
                }
                if(top>0)
                {
                        p=stack[top];    //*p所指结点为无左子树的结点或其左子树已遍历过
                        top--;
                        printf("%c",p->data);
                        p=p->rchild;
                }
        }while(p || top!=0);
}
void Postorder(BinTree T)
{
        BinNode *stack[Maxsize],*p;
        int tag[Maxsize];
        int top=0;
        p=T;
        do
        {
                while(p)
                {
                        top++;
                        stack[top]=p;
                        tag[top]=0;
                        p=p->lchild;
                }
                if(top>0)
                {
                        if(tag[top]==1)
                        {
                                printf("%c",stack[top]->data);
                                top--;
                        }
                        else
                        {
                                p=stack[top];
                                if(top>0)
                                {
                                        p=p->rchild;
                                        tag[top]=1;
                                }
                        }
                }
        }while(p || top!=0);
}

void Translevel(BinTree T)
{
        struct Bin
        {
                BinTree R[Maxsize];
                int f,r;
        }q;
        q.f=0;
        q.r=0;
        if(T)
                printf("%c",T->data);
        q.R[q.r]=T;
        q.r=q.r+1;
        while(q.f<q.r)
        {
                T=q.R[q.f];
                q.f=q.f+1;
                if(T->lchild)
                {
                        printf("%c",T->lchild->data);
                        q.R[q.r]=T->lchild;
                        q.r=q.r+1;
                }
                if(T->rchild)
                {
                        printf("%c",T->rchild->data);
                        q.R[q.r]=T->rchild;
                        q.r=q.r+1;
                }
        }
}

void main()               
{
        BinTree T=NULL;
        printf("请输入您要建立的二叉树的先序扩展序列(用.表示空)\n");

        CreateBinTree(&T);
        printf("构造二叉树成功!\n");
    printf("先序遍历：");
    Preorder(T);
    printf("\n中序遍历：");
        Inorder(T);
        printf("\n后序遍历：");
        Postorder(T);
    printf("\n层次遍历：");
    Translevel(T);
    printf("\n");
}