二叉树非递归后序遍历

Question

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50

//定义二叉树的结构体
typedef struct BiTNode
{
    char data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

//定义栈的结构体
typedef struct SqStack
{
    BiTNode val[MaxSize];
    int top;
}SqStack;

SqStack S;

//初始化栈
void InitStack(SqStack& S)
{
    S.top = -1;
}

//判断栈是否为空
bool IsEmpty(SqStack& S)
{
    if (S.top == -1)
        return true;
    else
        return false;
}

//进栈
bool Push(SqStack& S, BiTNode& T)
{
    if (S.top == MaxSize - 1)
        return false;
    else
        S.val[++S.top] = T;
    return true;
}

void visit(BiTNode W) {
    printf("%c", W.data);
}

//出栈
BiTNode Pop(SqStack S)
{
    return S.val[S.top];
}

//非递归中序遍历
void PostOrder2(BiTree T)
{
    InitStack(S);    //初始化栈
    BiTNode* p = T;
    BiTNode* Y = NULL;
    BiTNode* q = T;
    while (p || !IsEmpty(S))   //S不空，p存在
    {
        if (p != NULL) {
            Push(S, *p);
            p = p->lchild;
        }
        else {
            *q = Pop(S); //返回栈顶元素
            if (q->rchild && (q->rchild) !=Y) { //这里Y的值一直指向栈顶元素，为什么？
                p = q->rchild;
            }

            else {
                visit(S.val[S.top--]);   //输出栈顶元素
                Y = q;
                p = NULL;
            }

        }
    }
}



//先序创建二叉树
void CreateBiTree(BiTree& T)
{
    char ch;
    ch = getchar();
    if (ch == '#')    //#代表空指针
        T = NULL;
    else
    {
        T = (BiTNode*)malloc(sizeof(BiTNode));
        if (T) {
            T->data = ch;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }
    }
}

int main() {
    BiTree T;     //创建了一指针
    printf("创建先序构建的二叉树：\n");
    CreateBiTree(T);
    printf("\n后序遍历的结果为：");
    PostOrder2(T);
    return 0;
}

我的代码运行情况顺畅，但是在关键代码那里，Y值一直等于栈顶元素值，始终找不到原因。

我想要达到的结果：DEBCA

Answer 1

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7772915
• 你也可以参考下这篇文章：二叉树遍历递归实现