이 진 트 리 의 비 재 귀적 후 순차 반복 알고리즘

  、  、         ，        ，               ，     ，               。     ，      ，           
typedef struct
{
   Node * p; 
   int rvisited;
}SNode 
//Node          ，rvisited==1  p               。

LastOrderTraverse(BiTree bt)
{
　　//  ，      ，     ，     ，            。
　　p = bt;
　　while(bt)
    {
　　　　//push       ，      ，            
            push(bt, 0); 
　　　　bt = bt.lchild;
　　}

　　//       
　　while(!Stack.empty())//     
    { 
　　　　sn = Stack.getTop(); // sn     

　　　　//  ，      N，       ，  N    ，N            (            )，              ，               ，            ，                ，         。
　　　　
　　　　if(!sn.p.rchild || sn.rvisited)//           ，          ，         ，    visit     。
        {
　　　　　　p = pop();
　　　　　　visit(p);
　　　　}
　　　　else //         rvisited 0，              ，            。
　　　　{ 
　　　　　　//                     ，      ，              。

　　　　　　//  ，           rvisited  1，                         (     ，                visit)。    ，            ，        visit  ，       rvisited   1。
　　　　　　sn.rvisited = 1;

　　　　　　//        ，          
　　　　　　p = sn.p.rchild;
　　　　　　while(p != 0)
            {
　　　　　　　　push(p, 0);
　　　　　　　　p = p.lchild;
　　　　　　}
　　　　}//        ，                ，                。
　　}