#include <assert.h>
#include <stdio.h>


struct tree{
    int n;
    struct tree *left;
    struct tree *right;
};

static const void *stack[128];
static char stack_flag[128];
static int stack_i;
#define visit(t) printf("%d\t", t->n)
#define push(x) do{if(x) stack[stack_i++] = x;}while(0)
#define pop() (stack_i == 0 ? NULL : stack[--stack_i])
#define push2(x, flag) do{if(x) {stack[stack_i] = x; stack_flag[stack_i++] = flag;}}while(0)
#define pop2(flag) (stack_i == 0 ? NULL : ((flag=stack_flag[--stack_i]), (stack_flag[stack_i] = 0), stack[stack_i]))

// 二叉树的先序遍历
//
// 递归版本
void preorder(const struct tree *t){
    if(t == NULL)
        return;
    visit(t);
    preorder(t->left);
    preorder(t->right);
}

// 循环版本
// 如何变成循环呢，方法就是递归怎么来，我们就怎么来，
// 1. 调用visit，但是调用之后要恢复两个函数调用，为了恢复现场，需要在栈空间中保存后续要做的事，我们这里显然不需要保存cpu寄存器等，只需要保存t->left和t->right就可以了，由于是先调用t->left，后调用t->right，所以入栈就要反过来。
//push(t->right);
//push(t->left);
//能不能直接push(t)呢，答案是不能，除非标记t已经访问过了，否则就循环访问t了，但是标记t访问过了还是要把t->right和t->left入栈，不如就直接来，更直接。
// 2. t访问完了，递归程序就恢复现场，返回到visit的下一个地址执行，恢复现场就对应我们的出栈，继续执行同样的preorder逻辑就相当于我们重复一次循环，
// 3. 递归程序继续这个过程，直到函数栈上的最底层，也就是最后一个函数调用返回，对应我们的继续这个过程，直到栈里面没有数据了为止。
// 代码如下
void preorder_loop0(const struct tree *in)
{
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        visit(t);
        push(t->right);
        push(t->left);
    }while((t = pop()) != NULL);
}
//这个程序是最原始的贴近递归的版本，还可以继续优化，visit(t)之后pop出来的一定是t->left，那么下次一定是visit(t->left)，往下递推，每一次都是visit(t->left)，也就是说按照一直向左的方向遍历就可以了，需要入栈的只是右子树，但是右子树谁先谁后呢，从递归程序可以看出，所有的左子树成员都在右子树的前面遍历，也就是说最接近树根的大叉是优先级最低的，远离树根的在左子树上的右子树更优先，也就是说，入栈的顺序和访问的顺序相同，即
//

void preorder_loop1(const struct tree *in)
{
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        while(t)
        {
            visit(t);
            push(t->right);
            t = t->left;
        }
    }while((t = pop()) != NULL);
}
// 将上面两种版本对比，想象一下preorder_loop0的执行过程，也可以直接优化为preorder_loop1

//中序遍历
// 递归版本
void inorder(const struct tree *t){
    if(t == NULL)
        return;
    inorder(t->left);
    visit(t);
    inorder(t->right);
}

// 第一步还是按照和递归一一对应的方式来转换成循环，这个地方有点复杂，因为第一个函数不是visit，本身就是个递归的，这时候的处理方式不唯一，可以直接把递归版本函数中最上面的那个inorder展开，也可以按照通用的循环中的逻辑来处理那个inorder，前者直接就是优化之后的了。另外由于inorder和visit是两种操作，为了区分是哪一种操作，还需要在入栈的时候加标记等。
void inorder_loop0(const struct tree *in)
{
    int is_visit = 0;
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        if(is_visit)
            visit(t);
        else
        {
            push2(t->right, 0);
            push2(t, 1);
            push2(t->left, 0);
        }
    }while((t = pop2(is_visit)) != NULL);
}
// 简化push(t->left); 同preorder的方法
void inorder_loop1(const struct tree *in)
{
    int is_visit = 0;
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        if(is_visit)
            visit(t);
        else
        {
            while(t)
            {
                push2(t->right, 0);
                push2(t, 1);
                t = t->left;
            }
        }
    }while((t = pop2(is_visit)) != NULL);
}
// 继续优化，每次pop出来的一定是先visit的，然后接着就是它的right，那么两者可以合成一个整体，这样也不用标记是否是is_visit了
void inorder_loop2(const struct tree *in)
{
    const struct tree *t = in;
    if(t == NULL)
        return;

    while(t)
    {
        push(t);
        t = t->left;
    }
    while((t = pop()) != NULL)
    {
        visit(t); // pop -> t
        if(t->right) // pop -> t->right
        {
            t = t->right;
            while(t)
            {
                push(t);
                t = t->left;
            }
        }
    }
}

// 后续遍历
// 递归版本
void postorder(const struct tree *t){
    if(t == NULL)
        return;
    postorder(t->left);
    postorder(t->right);
    visit(t);
}
// 和中序遍历相同的方式，唯一一个区别就是 visit(t) 和postorder(t->right)的顺序换了一下，也就是入栈的顺序换了一下。代码如下：
void postorder_loop0(const struct tree *in)
{
    int is_visit = 0;
    const struct tree *t = in;
    if(t == NULL)
        return;
    do{
        if(is_visit)
            visit(t);
        else
        {
            push2(t,