二叉树的中序遍历非递归算法-蒲公英云

二叉树的中序遍历非递归算法

*非递归算法思想：

（1）设置一个栈S存放所经过的根结点（指针）信息；初始化S；

（2）第一次访问到根结点并不访问，而是入栈；

（3）中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点；然后中序遍历它的右子树。

（4）当需要退栈时，如果栈为空则结束。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 1

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 2

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 3

代码实现：

void Midorder(struct BiTNode *t)      //t为根指针 
{ struct BiTNode *st[maxleng];//定义指针栈
  int top=0；                  //置空栈
  do{            
    while(t)               //根指针t表示的为非空二叉树 
    { if (top==maxleng) exit(OVERFLOW)；//栈已满,退出
      st[top++]=t；             //根指针进栈
      t=t->lchild；             //t移向左子树
     }   //循环结束表示以栈顶元素的指向为根结点的二叉树
         //的左子树遍历结束
    if (top)                    //为非空栈   
    { t=st[--top]；             //弹出根指针
      printf("%c",t->data)；    //访问根结点
      t=t->rchild；             //遍历右子树
     }
   } while(top||t)； //父结点未访问，或右子树未遍历
 }

依照同样的思维，写的先序遍历非递归模式

void Preorder(struct BiTNode * t){
  struct BiTNode * St[MaxSize], *p;
  int top = 0;             //置空栈
  if (t! = NULL){
      St[top++] = t;
    while(top){
       p = St[--top]; printf("%c ", p->data);
       if(p->rchild != NULL)
          St[top++] = p->rchild;
       if(p->lchild != NULL)
          St[top++] = p->lchild;
    }
    printf("\n");
  }
}

后序遍历

void Postorder(struct BiTNode * t){
  struct BiTNode * St[MaxSize], *pre;
  int flag, top = 0;
  if (t != NULL){
      do{
         while(t != NULL){
           St[top++] = t; t = t->lchild;
        }
         pre = NULL; flag = 1;
         while(top && flag){
          t = St[top-1];
           if(t->rchild == pre){
               printf(“%c ”, t->data); top--;  pre = t;
           }
           else{ t=t->rchild; flag = 0;}
         }
       }while(top);
      printf(“\n”); 
    }
}