#include<stdio.h>

#include<stdlib.h>

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define OVERFLOW -1

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef int Status;

typedef char ElemType;

typedef struct BTNode{//定义树节点结构体

    ElemType data;

    struct BTNode *l;

    struct BTNode *r;

}BTNode,*BinTree;

typedef BinTree SElemType;

typedef struct{//非递归遍历要使用的栈操作定义

    SElemType *base;

    SElemType *top;

    int stacksize;//当前的栈空间容量

}SqStack;

//定义二叉树的基本操作

BinTree CreateBinTree(BinTree T);//创建二叉树并且返回一个指针

Status Visit(ElemType e);

Status Depth(BinTree T);

Status PreOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e));

Status LevelOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e));

//定义栈的基本操作

Status InitStack(SqStack *S);

Status Destroy(SqStack *S);

Status StackEmpty(SqStack S);

Status GetTop(SqStack *s,SElemType *e);

Status Pop(SqStack *S,SElemType *e);

Status Push(SqStack *S,SElemType e);

Status StackTraverse(const SqStack *S);//常量？

Status PreOrderNoneRecursionTraverse(BinTree T,Status(*Visit)(ElemType e));//非递归先序遍历

int main(){

    //int depth;

    BinTree Tree=NULL;

    Status(*Visit)(ElemType e)=Visit;//使用函数指针，用指针调用函数

    printf("请按先序遍历输入二叉树元素（空节点为=）:\n");

    Tree=CreateBinTree(Tree);

    printf("\n先序遍历：\n");

    PreOrderRecursionTraverse(Tree,Visit);

    printf("\n层序遍历：\n");

    LevelOrderRecursionTraverse(Tree,Visit);

}

BinTree CreateBinTree(BinTree T){

    char ch;

    scanf("%c",&ch);

    if(ch=='='){

        T=NULL;

    }else{

        if(!(T=(BTNode *)malloc(sizeof(BTNode)))){

            exit(OVERFLOW);

        }

        T->data=ch;

        T->l=CreateBinTree(T->l);

        T->r=CreateBinTree(T->r);

    }

    return T;//返回的T为最后一个结点

}

Status Visit(ElemType e){

    if(e=='\0'){

        return ERROR;

    }else{

        printf("%c",e);

    }

    return OK;

}

Status PreOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e))

{

    if(T){//判空

        if(!Visit(T->data)){//访问不成功，visit返回的是error

            return ERROR;

        }

        PreOrderRecursionTraverse(T->l,Visit);

        PreOrderRecursionTraverse(T->r,Visit);

    }

    return OK;

}

//层遍历

Status LevelOrderRecursionTraverse(BinTree T,Status(*Visit)(ElemType e))

{

    if(T){

        int front=-;//每一次循环中表示从左到右的父节点的增加

        int rear=-;//每一次循环当中用来表示front下一层该父节点左右子节点的变化增加

        BTNode *Q[];//用来存储呢每一层从左到右的每一个树节点

        Q[++rear]=T;

        printf("根节点的数据：%d ",T->data);

        while(front!=rear){

            BTNode *p;

            if(!(p=(BTNode *)malloc(sizeof(BTNode)))){

                exit(OVERFLOW);

            }

            p=Q[++front];

            if(p->l){

                Q[++rear]=p->l;

                printf("节点%d 的数据：%d",rear,p->l->data);

            }

            if(p->r){

                Q[++rear]=p->r;

                printf("节点%d 的数据：%d",rear,p->r->data);

            }

        }

    }

}

/*

Status Depth(BinTree T){

    int a,b;

    if(!T){

        return ERROR;

    }else{

        a=Depth(T->l)+1;

        b=Depth(T->r)+1;

        return a>b?a:b;

    }

}

Status PreOrderNoneRecursionTraverse(BinTree T,Status(*Visit)(ElemType e)){

        SqStack S;

        SElemType p;

        InitStack(&S);

        Push(&S,T);//将T入栈作为第一个操作结点

        while(S.base!=S.top){//栈不为空就一直循环，从上到下从左到右的取出

            Pop(&S,&p);

            if(!Visit(p->data)){//判断是否访问成功

                return ERROR;

            }

            if(p->l){

                Push(&S,p->r);//右结点先入栈为了后出栈

            }

            if(p->r){

                Push(&S,p->l);

            }

        }

        DestroyStack(&S);//释放栈

        return OK;

}*/