二叉树非递归的后序遍历为什么不对呢

Question

已经看了好长时间了，还是不知道为什么，求指点输入abd..e..cf..g..输出如下所示，是循环的，知道大概是在判断p->right == pre处出的问题，但是就是想不通为什么此处条件不正确，求大神解答debfgca 进入1 b stack a 进入1 d stack ba 进入1 NULL stack dba getTop:d ino:1  p->right:NULL d进入2 pre:d stack ba getTop:b ino:0 进入3 e 进入1 NULL stack eba getTop:e ino:0  p->right:NULL e进入2 pre:e stack ba  getTop:b  ino:0  进入3 e  进入1 NULL stack eba  getTop:e  ino:0   p->right:NULL e进入2 pre:e stack ba#include <iostream>#include<stdlib.h>using namespace std;#define MAXSIZE 50typedef struct TNode{ char data; struct TNode *left, *right;}TNode, *bitTree;typedef TNode ElemType;typedef struct{    ElemType data[MAXSIZE];    int top;} Sqstack;void InitStack(Sqstack &S);bool isEmpty(Sqstack S);void getTop(Sqstack S, ElemType &e);void push(Sqstack &S, ElemType x);void pop(Sqstack &S, ElemType &x);void printStack(Sqstack S);void createTree(bitTree &T);void preOrder(bitTree T);void inOrder(bitTree T);void postOrder(bitTree T);void inOrderStack(bitTree T, Sqstack S);void preOrderStack(bitTree T, Sqstack S);void postOrderStack(bitTree T, Sqstack S);int main() {    bitTree T;    createTree(T); //输入 abd..e..cf..g..    postOrder(T);    cout << endl;    Sqstack S;    InitStack(S);    //后序遍历非递归算法    postOrderStack(T, S);    }//后序遍历非递归void postOrderStack(bitTree T, Sqstack S){    TNode *p = T, *pre = NULL;    ElemType x;    while(p || !isEmpty(S)){        if(p){            cout << "进入1 ";            push(S, *p);            p = p->left;            if(p) cout << p->data << " ";            else cout << "NULL" << " ";            cout << "stack ";            printStack(S);        }        else{            getTop(S, x);            p = &x;            cout << "getTop:" << x.data << endl;            cout << "ino:" << (x.right == pre) << endl;            if(!p->right || p->right == pre){//右边为空或右边已经遍历过                pop(S, *p);                cout << p->data;                pre = p;                p = NULL;                cout << "进入2 ";                cout << "pre:" << pre->data;                //if(p->right) cout << " p->right:" << p->right->data;                //else cout << " p->right:NULL ";                cout << " stack ";                printStack(S);            }            else{                cout << "进入3 ";                p = p->right;                if(p) cout << p->data << endl;                else cout << "NULL" << endl;            }        }    }    }void createTree(bitTree &T){    //cout << "init" << endl;    //以递归前序遍历方式创建，空用.表示    TNode s;    char data;    data = getchar();    if(data != '.'){        T = (TNode*)malloc(sizeof(TNode));        T->data = data;        T->left = NULL;        T->right = NULL;        createTree(T->left);        createTree(T->right);    }    else{        T = NULL;    }}void postOrder(bitTree T){    if(T){        postOrder(T->left);        postOrder(T->right);        cout << T->data;    }}void printStack(Sqstack S){ for(int i = S.top; i > -1; i--){ cout << S.data[i].data; } cout << endl;}void InitStack(Sqstack &S){    S.top = -1;}bool isEmpty(Sqstack S){    if(S.top == -1) return 1;    return 0;}void getTop(Sqstack S, ElemType &e){    e = S.data[S.top];}void push(Sqstack &S, ElemType x){    if(S.top != MAXSIZE-1){        S.data[++S.top] = x;    }}void pop(Sqstack &S, ElemType &x){    if(S.top != -1){        x = S.data[S.top--];    }}

Answer 1

      .......