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

//树结构 
typedef struct kl
{
    int data;
    struct kl *lchild;
    struct kl *rchild;
}bittree;

//栈结构 
typedef struct ji
{
    int top;
    bittree **data;
    int size;
}stack;

//初始化栈
void init(stack *stack,int size)
{
    stack->size = size;
    stack->top = -1;
    stack->data = (bittree**)malloc(size * sizeof(bittree*));
    for(int i = 0 ; i < size  ;i++)
    {
        stack->data[i] = NULL;    
    }    
}

//创建树
bittree *createtree()
{
    bittree *root = NULL;
    int num;
    printf("Please input number:");
    scanf("%d",&num);
    if(num > 0)
    {
        root = (bittree*)malloc(sizeof(bittree));
        root->data = num;
        root->lchild = createtree();
        root->rchild = createtree();
    }
}

//栈的操作 判满
int isfull(stack *stack)
{
    return stack->top == stack->size-1;
} 

//栈的操作 判空
int isempty(stack *stack)
{
    return stack->top == -1; 
}

//栈的操作 入栈 
void input(stack *stack,bittree *root)  
{
    if(isfull(stack)) return; 
    stack->top++;
    stack->data[stack->top] = root;
}

//栈的操作 出栈
bittree *out(stack *stack) 
{
    return stack->data[stack->top--];
}

//栈的操作 返回栈顶元素
bittree *top(stack * stack)
{
   int index;
   if(stack->top==-1) return NULL;
    index=stack->top;
    return stack->data[index];
} 

void midvisitbystack1(bittree *root)//已做演示  
{
    if(root == NULL)
        return ;
    
    stack stack;
    init(&stack,50); //一直到这一步差不多都是一样的 
      
    while(root != NULL)
    {
        input(&stack,root);
        root = root->lchild;     //把最左边的一列树的数据全部存入  
    }    
    
    while(!isempty(&stack))
    {
        root = out(&stack);     //一一读出 当读出的这个树有有孩子时 就可以让它等于它的右孩子  
        printf("%5d",root->data);    //然后再把这个右孩子最左边的一列树的数据全部存入 这样循环就解决了   
        if(root->rchild != NULL)
        {
            root = root->rchild;
            while(root != NULL)
            {
                input(&stack,root);
                root = root->lchild;    
            }
        }
    }
}

 

void midvisitbystack2(bittree *root)//已做演示 
{
    stack stack;
    init(&stack,50);
    
    if(root == NULL)
        return ;
    //中序是左右中 那么再栈中就是 右中左  
    input(&stack,root); //注意的地方1 
    while(!isempty(&stack))
    {
        root = out(&stack);
        if (root == NULL)     return;
        //变的地方就是 先存入根 到了后面读出了根  然后存入右孩子 最后又存入了根   
        //还有一个关键条件是 如果这个数据是叶子 或者是 栈顶元素 那么就可以打印 
        if(root->lchild == NULL&&root->rchild == NULL || !isempty(&stack)&&root->rchild == top(&stack))
        {
            printf("%5d",root->data);
            continue;
        } 
            
        input(&stack,root->rchild);  //右 
        input(&stack,root);//注意的地方2   中 
        if(root->lchild != NULL)    
            input(&stack,root->lchild); //左        
    }
} 

 

 
 
int main()
{
    bittree *root = createtree();
    midvisitbystack2(root);
    return 0;
}