#include <stdio.h>
#include <stdlib.h>

#define True 1
#define False 0
typedef char bool;

typedef struct TreeNode
{
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
    unsigned int flag;
} TreeNode;

typedef struct StackNode
{
    TreeNode *data;
    struct StackNode *next;
} StackNode;

// 创建二叉树
void createTree(TreeNode **T, char *data, int *index)
{
    char ch;
    ch = data[*index];
    *index += 1;
    if (ch == '#')
    {
        *T = NULL;
    }
    else
    {
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->data = ch;
        (*T)->flag = 0;
        createTree(&((*T)->left), data, index);
        createTree(&((*T)->right), data, index);
    }
}

// 初始化栈
StackNode *initStack()
{
    StackNode *S = (StackNode *)malloc(sizeof(StackNode));
    S->data = NULL;
    S->next = NULL;
    return S;
}

// 入栈
void push(StackNode *S, TreeNode *data)
{
    StackNode *node = (StackNode *)malloc(sizeof(StackNode));
    node->data = data;
    node->next = S->next;
    S->next = node;
}

// 判断是栈是否为空
bool isEmpty(StackNode *S)
{
    if (S->next == NULL)
    {
        return True;
    }
    else
    {
        return False;
    }
}

// 出栈
StackNode *pop(StackNode *S)
{
    if (isEmpty(S))
    {
        return NULL;
    }
    else
    {
        StackNode *node = S->next;
        S->next = node->next;
        return node;
    }
}

// 获取栈顶
StackNode *getTop(StackNode *S)
{
    if (isEmpty(S))
    {
        return NULL;
    }
    else
    {
        StackNode *node = S->next;
        return node;
    }
}

// 非递归前序遍历二叉树
void preOrder(TreeNode *T)
{
    TreeNode *node = T;
    StackNode *S = initStack();
    while (node || !isEmpty(S))
    {
        if (node)
        {
            printf("%c ", node->data);
            push(S, node);
            node = node->left;
        }
        else
        {
            node = pop(S)->data;
            node = node->right;
        }
    }
    printf("\n");
}

// 非递归中序遍历二叉树
void inOrder(TreeNode *T)
{
    TreeNode *node = T;
    StackNode *S = initStack();
    while (node || !isEmpty(S))
    {
        if (node)
        {
            push(S, node);
            node = node->left;
        }
        else
        {
            node = pop(S)->data;
            printf("%c ", node->data);
            node = node->right;
        }
    }
    printf("\n");
}

// 非递归后序遍历二叉树
void postOrder(TreeNode *T)
{
    TreeNode *node = T;
    StackNode *S = initStack();
    while (node || !isEmpty(S))
    {
        if (node)
        {
            push(S, node);
            node = node->left;
        }
        else
        {
            TreeNode *top = getTop(S)->data;
            if (top->right && top->right->flag == 0)
            {
                top = top->right;
                push(S, top);
                node = top->left;
            }
            else
            {
                top = pop(S)->data;
                printf("%c ", top->data);
                top->flag = 1;
            }
        }
    }
    printf("\n");
}

// 执行./main ABD##E##CF##G##
int main(int argc, char *argv[])
{
    TreeNode *T;
    int index = 0;
    createTree(&T, argv[1], &index);
    preOrder(T);
    inOrder(T);
    postOrder(T);
    return 0;
}