c++ - （二叉树的非递归后续遍历）运行后，直接崩溃

Question

#include <iostream>
using namespace std;
#define MAXSIZE 50



typedef struct node
{
    char data;
    struct node *lchild;
    struct node *rchild;
}BiNode, *BiTree;


// 先序建立二叉树 （输入时，按先序次序输入二叉树中结点的值,以 # 字符表示空树）
BiTree createBiTree()
{
    BiTree T;
    
    char c;
    scanf("%c", &c);
    
    if (c == '#')
        T = NULL;
    else
    {
        T = new BiNode;  // 或 T = (BiTree)malloc(sizeof(BiNode));
        T->data = c;
        
        T->lchild = createBiTree();
        T->rchild = createBiTree();
    }
    
    return T;
    
}

typedef struct stackNode
{
    BiTree ptr;
    int flag;
} *pSTree;

// 二叉树的后序遍历（非递归）
void postOrder(BiTree T)
{
    pSTree s[MAXSIZE]; // 栈s初始化
    int top = -1; // 采用顺序栈，并假定不会发生溢出


    while ((T != NULL) || (top != -1)) // 循环直到T为空且栈s为空
    {
        while (T != NULL) // 当T不为空时循环
        {
            top++;
            s[top]->ptr = T; ***// ???????运行后正确，输入“ab##c##”创建二叉树后，直接崩溃；***
            s[top]->flag = 1; // 将 T 连同 标志flag=1 入栈
            T = T->lchild; // 继续遍历T的左子树
        }

        while (top != -1 && s[top]->flag == 2) // 当栈s非空且栈顶元素的标志为2时，出栈并输出栈顶节点
        {
            T = s[top--]->ptr;
            cout << T->data << endl;
            if (top == -1)
                return;
        }
        if (top != -1) // 若栈非空，将栈顶元素的标志改为2，准备遍历栈顶节点的右子树
        {
            s[top]->flag = 2;
            T = s[top]->ptr->rchild;
        }

    }
}

Answer 1

typedef struct stackNode
{

BiTree ptr;
int flag;

}NODET, *pSTree;

while (T != NULL)

    {
        top++;
        **s[top] = new NODET();** // 只需添加该行代码即可解决
        s[top]->ptr = T; 
        s[top]->flag = 1;
        T = T->lchild;
    }

Answer 2

The main question is the difference between pointer array and array pointer.
void postOrder(BiTree T)
{

pSTree s[MAXSIZE]; // 栈s初始化
int top = -1; // 采用顺序栈，并假定不会发生溢出

The s here is actually an array of pointers, and when s[0]->ptr = T, an error will occur because the pointer s[0] does not point to any stackNode.

Change pSTree s[MAXSIZE]; to stackNode s[MAXSIZE]; also change the corresponding s below, and there should be no error

Answer 3

https://github.com/bloomsource/rbtree