PreOrder(BiTree T)  //先序非递归遍历二叉树  {           InitStack(S);  //创建工作栈           Push(S,T);           while(!StackEmpty(S))           {                     Pop(S,p);  //出栈                     Visit(p);   //访问                     if(p->rchild)                               Push(S,p->rchild);  //右子树入栈                     if(p->lchild)                          Push(S,p->lchild);   //左子树入栈           } }   InOrder(BiTree T)  //中序非递归遍历二叉树  {           InitStack(S);  //创建工作栈           Push(S,<T,0>);   //根入栈，且置0标志此时不能访问           while(!StackEmpty(S))           {                     Pop(S,<p,flag>);  //出栈                     if(flag==1)                                Visit(p);  //访问标志为1可以访问                      else                      {                            if(p->rchild)                                Push(S,<p->rchild,0>);   //右子树入栈且置访问标志0                             Push(S,<p,1>);   //根入栈且置访问标志1                              if(p->lchild)                                   Push(S,<p->lchild,0>);    //左子树入栈且置访问标志0                       }           } }   PostOrder(BiTree T)  //后序非递归遍历二叉树  {           InitStack(S);  //创建工作栈           Push(S,<T,0>);  //根入栈，且置i0标志此时不能访问           while(!StackEmpty(S))           {                 Pop(S,<p,flag>);  //出栈                  if(flag==1)                             Visit(p);  //访问标志为1可以访问                   else                   {                          Push(S,<p,1>);  //根入栈且置访问标志1                            if(p->rchild)                                   Push(S,<p->rchild,0>);  //右子树入栈且置访问标志0                             if(p->lchild)                                     Push(S,<p->lchild,0>);  //左子树入栈且置访问标志0                    }          } }   LayerOrder(BiTree T)  //层次遍历二叉树  {           InitQueue(Q);  //创建工作队列           EnQueue(Q,T);  //根入队           while(!QueueEmpty(Q))           {                     DeQueue(Q,p);  //出队                     Visit(p);  //访问                     if(p->lchild)                                EnQueue(Q,p->lchild);  //左子树入队                     if(p->rchild)                               EnQueue(Q,p->rchild);    //右子树入队           } }

评论