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

我会带着你远行 2022-03-28 10:55 237阅读 0赞

\*非递归算法思想：

（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”); 
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70]: /images/20220328/6d620d9d0e3141bbafef438bdeacb882.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 1]: /images/20220328/88a91f30966b441da69d22dc02f26d5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 2]: /images/20220328/ef0f3529aa904780b9e9d4c89213f469.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 3]: /images/20220328/e4813ebd74754db69ba98205e5d58fa6.png