二叉树遍历练习 - 递归/非递归

参考：https://blog.csdn.net/winter2121/article/details/99560253
样例：

样例输入：ABD##E##C#FG##H##

#include 
#include 
struct Node
{
    char data;
    struct Node *lchild, *rchild;
};

Node *createTree()
{
    char ch = getchar();
    if (ch != '#')
    {
        Node *p = (Node *)malloc(sizeof(Node));
        p->data = ch;
        p->lchild = createTree();
        p->rchild = createTree();
        return p;
    }
    return NULL;
}

void display_pre(Node *rt) //递归先序
{
    if (rt == NULL)
        return;
    putchar(rt->data);
    display_pre(rt->lchild);
    display_pre(rt->rchild);
}
void display_mid(Node *rt) //递归中序
{
    if (rt == NULL)
        return;
    display_mid(rt->lchild);
    putchar(rt->data);
    display_mid(rt->rchild);
}
void display_back(Node *rt) //递归后序
{
    if (rt == NULL)
        return;
    display_back(rt->lchild);
    display_back(rt->rchild);
    putchar(rt->data);
}

void display_pre_stack(Node *rt) //非递归先序
{
    Node *p = rt, *st[100]; // st栈
    int top = 0;            //栈实时大小
    while (p || top > 0)
    {
        if (p)
        {
            printf("%c", p->data);
            st[top++] = p;
            p = p->lchild;
        }
        else
        {
            p = st[--top];
            p = p->rchild;
        }
    }
}

void display_mid_stack(Node *rt) //非递归中序
{
    Node *p = rt, *st[100]; // st栈
    int top = 0;            //栈实时大小
    while (p || top > 0)
    {
        if (p)
        {
            st[top++] = p;
            p = p->lchild;
        }
        else
        {
            p = st[--top];
            printf("%c", p->data);
            p = p->rchild;
        }
    }
}

void display_back_stack(Node *rt) //非递归后序遍历
{
    Node *last = NULL, *p, *st[100];
    int top = 0; //栈元素数量
    st[top++] = rt;
    while (top > 0)
    {
        p = st[top - 1];                                         //取栈顶为p
        if (p->lchild && p->lchild != last && p->rchild != last) // p左子树存在&&未访问
        {
            p = p->lchild;
            st[top++] = p;
        }
        else if (p->rchild && p->rchild != last) // p右子树存在&&未访问
        {
            p = p->rchild;
            st[top++] = p;
        }
        else //左右均已访问，输出当前p，并从栈中弹出
        {
            printf("%c", p->data);
            top--; // p出栈
            last = p;
        }
    }
}

int main()
{
    Node *root = createTree(); // ABD##E##C#FG##H##
    printf("递归先序遍历:");
    display_pre(root);
    printf("n递归中序遍历:");
    display_mid(root);
    printf("n递归后序遍历:");
    display_back(root);

    printf("n非递归先序遍历:");
    display_pre_stack(root);
    printf("n非递归中序遍历:");
    display_mid_stack(root);
    printf("n非递归后序遍历:");
    display_back_stack(root);
}