问题描述
#include <iostream>using namespace std;#define MAXSIZE 50typedef 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;} }}
问题解答
回答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; }回答2：
题主的问题在于，指针数组和数组指针的区别。void postOrder(BiTree T){
pSTree s[MAXSIZE]; // 栈s初始化int top = -1; // 采用顺序栈，并假定不会发生溢出
这里的s其实是一个指针数组，而当s[0]->ptr = T时，就会发生错误，因为s[0]这个指针并没有指向任何一个stackNode。
把pSTree s[MAXSIZE];改成stackNode s[MAXSIZE];下面s对应的也改一下，应该不会报错了
回答3：https://github.com/bloomsource/rbtree
