二叉树的前中后序遍历非递归实现

╰半橙微兮° 2022-12-02 04:23 138阅读 0赞

转载请注明出处：[https://blog.csdn.net/Benja\_K/article/details/88389039][https_blog.csdn.net_Benja_K_article_details_88389039]

**二叉树的非递归前、中、后序遍历算法详解及代码实现（C语言）**

1. 前序遍历和中序遍历非递归算法思路

前序和中序非递归遍历的C代码

2. 后序遍历非递归算法思路

后序非递归遍历的C代码

--------------------

# 1. 前序遍历和中序遍历非递归算法思路 #

遍历过程：（如图所示）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JlbmphX0s_size_16_color_FFFFFF_t_70][] 图1 前序遍历和中序遍历流程图

从当前节点开始遍历：（当入栈时访问节点内容，则为前序遍历；出栈时访问，则为中序遍历）

1. 若当前节点存在，就存入栈中，并访问左子树；

2. 直到当前节点不存在，就出栈，并通过栈顶节点访问右子树；

3. 不断重复12，直到当前节点不存在且栈空。

**Tips：我们很容易发现，在理解并写好该非递归遍历代码后，只需要在入栈、出栈的时候，分别进行节点访问输出，即可分别得到前序、中序的非递归遍历代码！！！**

便于理解的伪代码：

void preOrder(TreeNode *T){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             p = T
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             
         
          while(p不空||栈不空){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                 
         
          if(p不空){      
         
          //两种情况：1.栈不空；2.栈空
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     p入栈;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     (前序遍历，访问)
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     入p左子节点;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                 }
         
          else{            
         
          //一种情况：当前节点为空，但栈不空
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     p=出栈;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     (中序遍历，访问)
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     入p右子节点;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                 }
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             }
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
         }

### 前序和中序非递归遍历的C代码 ###

二叉树节点结构体：

typedef 
         
          struct TreeNode{
           
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          int data;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          struct TreeNode *lChild;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          struct TreeNode *rChild;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
         }TreeNode;

前序遍历非递归：

void preOrder(TreeNode *T){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             TreeNode *
         
          stack[
         
          15];
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          int top = 
         
          -1;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             TreeNode *p = T;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          while(p!=
         
          NULL||top!=
         
          -1){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                 
         
          if(p!=
         
          NULL){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                     
         
          stack[++ top] = p;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                     
         
          printf(
         
          "%d\t",p->data); 
         
          //入栈时，访问输出
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     p = p->lChild;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                 }
         
          else{
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     p = 
         
          stack[top --];
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     p = p->rChild;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                 }
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             }
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
         }

中序遍历非递归：

void inOrder(TreeNode *T){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             TreeNode *
         
          stack[
         
          15];
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          int top = 
         
          -1;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             TreeNode *p = T;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          while(p!=
         
          NULL||top!=
         
          -1){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                 
         
          if(p!=
         
          NULL){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                     
         
          stack[++ top] = p;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     p = p->lChild;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                 }
         
          else{
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     p = 
         
          stack[top --];
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                     
         
          printf(
         
          "%d\t",p->data);  
         
          //出栈时，访问输出
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     p = p->rChild;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                 }
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             }
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
         }

# 2. 后序遍历非递归算法思路 #

后序遍历整体与前中序遍历过程相似。但要注意，这时对于父节点的访问输出，需要在其右子树遍历完成的前提下进行。所以不能像前中序遍历一样，在遍历完左子树后，就直接出栈。我们需要利用这个未出栈的栈顶元素去获取右子树，在遍历完右子树后，就可以出栈，并对此节点进行访问输出。

这里我们需要使用一个标记，以区分是从左子树取栈还是从右子树出栈：（如图所示）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JlbmphX0s_size_16_color_FFFFFF_t_70 1][] 图2 后序遍历流程图

从当前节点开始遍历：

1. 若当前节点存在，就存入栈中，并且置节点flag为1（第一次访问），然后访问其左子树；

2. 直到当前节点不存在，需要回退，这里有两种情况：

1）当栈顶节点flag为1时，则表明是从左子树回退，这时需置栈顶节点flag为2（第二次访问），然后通过栈顶节点访问其右子树（取栈顶节点用，但不出栈）

2）当栈顶节点flag为2时，则表明是从右子树回退，这时需出栈，并取出栈节点做访问输出。（需要注意的是，输出完毕需要置当前节点为空，以便继续回退。具体可参考代码中的p = NULL）

3. 不断重复12，直到当前节点不存在且栈空。

**Tips：我们很容易发现，当理解并写好后序遍历非递归代码后，只需要在入栈、取栈、出栈的时候，分别进行节点访问输出，即可分别得到前序、中序、后序的非递归遍历代码，是不是非常简单！！！**

###  ###

### 后序非递归遍历的C代码 ###

节点结构体：

后序遍历非递归：

void postOrder(TreeNode *T){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             TreeNode *
         
          stack[
         
          15];
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          int top = 
         
          -1;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          int flagStack[
         
          15];   
         
          //记录每个节点访问次数栈
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             TreeNode *p = T;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
             
         
          while(p!=
         
          NULL||top!=
         
          -1){
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                 
         
          if(p!=
         
          NULL){     
         
          //第一次访问，flag置1，入栈
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                     
         
          stack[++ top] = p;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     flagStack[top] = 
         
          1;   
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     p = p->lChild;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                 }
         
          else{
         
          //（p == NULL）
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                     
         
          if(flagStack[top] == 
         
          1){  
         
          //第二次访问，flag置2，取栈顶元素但不出栈
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                         p = 
         
          stack[top];
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                         flagStack[top] = 
         
          2;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                         p = p->rChild;
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     }
         
          else{         
         
          //第三次访问，出栈
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                         p = 
         
          stack[top --];
        
         
       
        
       
       
        
        
         
       
        
       
        
        
                         
         
          printf(
         
          "%d\t",p->data);    
         
          //出栈时，访问输出
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                         p = 
         
          NULL;      
         
          //p置空，以便继续退栈
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                     }
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
                 }
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
             }
        
         
       
        
       
       
        
        
         
       
        
       
        
        
         
          
         }

[https_blog.csdn.net_Benja_K_article_details_88389039]: https://blog.csdn.net/Benja_K/article/details/88389039
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JlbmphX0s_size_16_color_FFFFFF_t_70]: /images/20221123/d7d355e2ce044820b6dcd4bf11b6fed1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JlbmphX0s_size_16_color_FFFFFF_t_70 1]: /images/20221123/22d319a9a66d41c296fd5a381a17344c.png