囧 后序遍历死循环。。
void BiTree::fPostorder(BiNode *root)
{
int top=-1;
element s[100];
while (root!=NULL || top!=-1)
{
while (root!=NULL)
{
top++;
s[top].ptr=root;
s[top].flag=1;
root=root->lchild;
}
while (top!=-1&&s[top].flag==2)
{
root=s[top--].ptr;
cout<<root->data;
}
if (top!=-1)
{
s[top].flag=2;
root=s[top].ptr->rchild;
}
}
}
二叉树后序遍历非递归算法的死循环。。
[解决办法]
数据结构:栈+结构体{flag:当前访问左还是右,Node *;}
实现：初始化压入{无,root}.
循环：取栈顶A.
情况1: 如果A->flag==无,那么：如果A->left!=Null,标记A->flag==左并且压入{无,A->left}，否则如果A->right!=NULL,标记A->flag==右,压入{无,A->right},否则(left,right都空)弹出A,打印A->data.
情况2:如果A->flag==左,那么:如果A->right!=Null,标记A->flag==右并且压入{无,A->right},否则弹出A,打印A->data;
情况3：如果A->flag==右,那么弹出A,打印A->data.
总之,在结点进入下一层递归之前,要记录它当前要去递归的是左子树还是右子树.
