//二叉树的非递归遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSIZE 1024

//非递归需要辅助栈
//栈的结构体
struct SStack
{   
    //将数组头作为栈顶，因为如果作为栈顶的话来回出入元素时间开销比较大
    void *data[MAXSIZE]; //数组
    int size;
};

typedef void * sstack;

//初始化栈
sstack init_stack(){
    struct SStack * myStack = malloc(sizeof(struct SStack));
    if (myStack==NULL)
    {
        return NULL;
    }
    memset(myStack->data,0,sizeof(void *)*MAXSIZE); //给数组赋初值0
    myStack->size=0; //初试化栈的大小
    return myStack;
}

//入栈
void push_stack(sstack stack,void *data ){
    if (stack==NULL)
    {
        return;
    }
    if (data==NULL)
    {
        return;
    }
    struct SStack *myStack=stack; //把用户传过来的指针转换成栈结构体指针

    //判断栈满
    if (myStack->size==MAXSIZE)
    {
        return;
    }
    
    //入栈就是尾插数组
    myStack->data[myStack->size]=data;
    myStack->size++;
}

//出栈
void pop_stack(sstack stack){
    if (stack==NULL)
    {
        return;
    }
    struct SStack *myStack=stack;

    //判断栈空
    if (myStack->size==0)
    {
        return;
    }
    
    //出栈其实就是尾删
    myStack->data[myStack->size-1]=NULL;
    myStack->size--;
}
//返回栈顶
void * top_stack(sstack stack)
{
	if (stack == NULL)
	{
		return NULL;
	}

	struct SStack * mystack = stack;

	if (mystack->size == 0)
	{
		return NULL;
	}
	return mystack->data[mystack->size - 1];
}
//判断栈是否为空
int isempty_stack(sstack stack){
    if (stack==NULL)
    {
        return -1; //返回-1代表栈空
    }
    struct SStack *myStack=stack;
    if (myStack->size==0)
    {
        return -1;
    }
    return 0;
}
//返回栈大小
int size_stack(sstack stack){
    if (stack==NULL)
    {
        return -1;
    }
    struct SStack *myStack=stack;
    return myStack->size;
}
//销毁栈
void destroy_stack(sstack stack){
    if (stack==NULL)
    {
        return;
    }    
    free(stack);
    stack=NULL;
}




//二叉树结点结构体
typedef struct BTNode{
    char data;
    struct BTNode *lchild,*rchild;
    int flag; //标志位
}BTNode,*BTree;

//创建二叉树
BTree CreateBitree(BTree T)//先序创建一颗二叉树
{
  char  e;
  printf("请输入结点数据:");
  scanf("%c", &e);
  fflush(stdin); //用于清空缓冲区
  if (e != '#')     //判断当前输入的字符
 {
 
   T = (BTree)malloc(sizeof(BTNode)); //分配存贮空间
   T->data = e;
   T->flag=0;
   T->lchild = NULL;
   T->rchild = NULL;
   T->lchild = CreateBitree(T->lchild); //递归创建左孩子节点值
   T->rchild = CreateBitree(T->rchild);   //递归创建右孩子节点值
 }
 return T;
}

//非递归遍历
/* 
1.将根节点入栈
2.只要栈中元素个数大于0，就执行循环(循环过程如下)
*/
void nonRecursion(BTree T){
    sstack myStack=init_stack(); 
    push_stack(myStack,T); //根节点入栈

    while (size_stack(myStack)>0)
    {
        //获取栈顶元素
        BTree pTop=top_stack(myStack);

        //出栈
        pop_stack(myStack);

        //如果标志位是真，直接输出 并且执行下一次循环
        if (pTop->flag==1)
        {
            printf("%c ",pTop->data);
        }
        //如果标志位为假，将其置为真，并且将其右子树，左子树，根节点（自身）入栈
        //由于入栈顺序是上述顺序，那么遍历的结果其实就是先序遍历
        else
        {
            pTop->flag=1;
            if (pTop->rchild!=NULL)
            {
                push_stack(myStack,pTop->rchild);
            }
            if (pTop->lchild!=NULL)
            {
                push_stack(myStack,pTop->lchild);
            }
            if (pTop!=NULL)
            {
                push_stack(myStack,pTop);
            }                
        }
    }
    //销毁栈
    destroy_stack(myStack);
}
int main()
{   
    BTree myTree=CreateBitree(myTree);
    printf("非递归遍历的结果为：");
    nonRecursion(myTree);
    return 0;
}