算法 6.2.txt

《数据结构及应用算法教程》一书的源代码。作者：严蔚敏

算法 6.2
void InOrder_iter( BiTree BT，void(*visit)( BiTree ) ) {
  // 利用栈实现中序遍历二叉树，T为指向二叉树的根结点的头指针
      InitStack(S);
      e.ptr=BT;  e.task=Travel;           // e为栈元素
      if(BT)  Push(S, e);                  // 布置初始任务
      while(!StackEmpty(S)) {              // 每次处理一项任务
         Pop(S,e);
         if(e.task==Visit) visit(e.ptr);    // 处理访问任务
         else
           if(e.ptr){                                    // 处理非空树的遍历任务
             p=e.ptr;
             e.ptr=p->rchild;  Push(S,e);                // 最不迫切任务(遍历右子树)进栈
             e.ptr=p;  e.task=Visit;  Push(S,e);         //处理访问任务的工作状态进栈
             e.ptr=p->lchild;  e.task=Travel;  Push(S,e);// 迫切任务(遍历左子树)进栈
           }//if
       }//while
}//InOrder_iter