首先要搞清楚先序、中序、后序的非递归算法共同之处：用栈来保存先前走过的路径，以便可以在访问完子树后,可以利用栈中的信息,回退到当前节点的双亲节点,进行下一步操作。
后序遍历的非递归算法是三种顺序中最复杂的，原因在于，后序遍历是先访问左、右子树,再访问根节点，而在非递归算法中，利用栈回退到时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点，如果从左子树回退到根节点，此时就应该去访问右子树，而如果从右子树回退到根节点，此时就应该访问根节点。所以相比前序和后序，必须得在压栈时添加信息，以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作。 voidpostrav1(structbtnode*bt){structbtnode*p;struct{structbtnode*pt;inttag;}st[MaxSize];inttop=-1;top++;st[top].pt=bt;st[top].tag=1;while(top>-1)/*栈不为空*/{if(st[top].tag==1)/*不能直接访问的情况*/{p=st[top].pt;top--;if(p!=NULL){top++;/*根结点*/st[top].pt=p;st[top].tag=0;top++;/*右孩子结点*/st[top].pt=p->p->rchild;st[top].tag=1;top++;/*左孩子结点*/st[top].pt=p->lchild;st[top].tag=1;}}}if(st[top].tag==0)/*直接访问的情况*/{printf("%d",st[top].pt->d);top--;}}算法2 voidpostrav2(structbtnode*bt){structbtnode*st[MaxSize],*p;intflag,top=-1;if(bt!=NULL){do{while(bt!=NULL){top++;st[top]=bt;bt=bt->lchild;}p=NULL;flag=1;while(top!=-1&&flag){bt=st[top];if(bt->rchild==p){printf("%d",bt->d);top--;p=bt;}else{bt=bt->rchild;flag=0;}}}while(top!=-1)printf("\n");}}
