二叉树的几种遍历方式浅析：递归遍历/堆栈遍历/层序遍历/Morris遍历

淩亂°似流年 2022-06-06 09:54 234阅读 0赞

在和树相关的算法中，二叉树的遍历起着举足轻重的作用，很多算法都能够以二叉树的遍历衍生出来，那么我们就从二叉树的建立开始，讲述二叉树的各种遍历方式。  
一、二叉树的建立  
二、二叉树递归遍历  
三、二叉树非递归遍历  
四、二叉树层序遍历  
五、二叉树Morris遍历

## 一、二叉树的建立 ##

首先，如何在内存中生成一颗二叉树呢？我们要在内存中创建一个如下图所示的二叉树。

A
        /   \    B     C
     /  \     \ D    E     F
     \   G

![这里写图片描述][SouthEast]

如上图所示，为了能让每个节点确认是否有左右孩子，我们对它进行扩展，也就是讲二叉树中每个节点的空指针引出一个虚结点，其值为一特定值，比如“\#“。我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一颗二叉树了。比如上图的前序遍历的前序遍历序列为：”ABD\#G\#\#E\#\#C\#F\#\#”。在内存中重建二叉树有两种方式：1.像上述所述的用扩展二叉树，根据前序遍历序列就能确定。2.根据前序遍历序列和中序遍历序列重建二叉树。本文采取第一种方式重建。  
建立二叉树的代码如下：

结果  
ABD\#G\#\#E\#\#C\#F\#\#  
ABDGECF

## 二、二叉树的递归遍历 ##

对于上图的二叉树，用递归的方法就行前序中序后序遍历。

using namespace std;
    
    typedef char TElemType;
    
    typedef struct BiTNode
    {
        TElemType val;
        BiTNode *lchild , *rchild;
        BiTNode(TElemType x):val(x),lchild(NULL),rchild(NULL) {}
    }tBiTNode;
    
    /*input : ABD#G##E##C#F##*/
    void createTree(tBiTNode *&T)
    {
         TElemType x;
         cin>>x;
         if(x=='#')
         {
             T = NULL;          
         }
         else
         {
             T = new BiTNode(x);
             createTree(T->lchild);
             createTree(T->rchild);
         }
    }
    
    /*Pre Order Traverse*/
    void PreOrderTraverse(BiTNode *T)
    {
        if(T==NULL)   return;
        cout<<T->val;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    
    /*In Order Traverse*/
    void InOrderTraverse(BiTNode *T)
    {
        if(T==NULL)     return ;
        InOrderTraverse(T->lchild);
        cout<<T->val;
        InOrderTraverse(T->rchild);
    } 
    
    /*Post Order Traverse*/
    void PostOrderTraverse(BiTNode *T)
    {
        if(T==NULL)     return ;
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<<T->val;
    }
    
    int main()
    {
        tBiTNode *p;
        createTree(p)    ;
        cout<<"Pre Order Traverse:"<<endl;
        PreOrderTraverse(p);
        cout<<"\nIn Order Traverse:"<<endl;
        InOrderTraverse(p);
        cout<<"\nPost Order Traverse:"<<endl;
        PostOrderTraverse(p); 
        cout<<endl;
        system("pause");
        return 0;
    }

![这里写图片描述][SouthEast 1]

## 三、二叉树的非递归遍历（堆栈遍历） ##

非递归前序遍历代码：

/*Pre Order Traverse with non-recursion algorithm*/
    void PreOrderTraverse(BiTNode *T)
    {
        if( T==NULL ) return ;
        vector<TElemType> vec; //contain the result sequence 
        stack<BiTNode *> stk;
        stk.push(T); //push the root into the stack 
        while( !stk.empty() )
        {
             BiTNode *cur = stk.top();
             stk.pop();
             vec.push_back(cur->val);
             if(cur->rchild!=NULL)
             {
                 stk.push(cur->rchild);
             }
             if(cur->lchild!=NULL)
             {
                 stk.push(cur->lchild);
             }
        }   
        print(vec);  //print the result 
    }

分析：前序遍历的顺序为“中–左–右”，那么指针从根节点开始，就是中间的节点，也是结果的第一个节点，然后依次是左子树和右子树的压栈和弹栈。值得注意的是，在压栈的时候首先压入的是右子树的根节点，然后才是左子树的根节点，是因为栈是先进后出的数据结构，后压入左子树才能先弹出，相信代码写的足够清楚，稍微揣测一下就能够理解，重点是非递归后序遍历。

非递归中序遍历代码：

/*In Order Traverse with non-recursion algorithm*/
    void InOrderTraverse(BiTNode *T)
    {
        if( T==NULL ) return ;
        stack<BiTNode *> stk;
        vector<TElemType> vec;
        BiTNode *cur = T->lchild;
        stk.push(T);
        while( cur!=NULL || !stk.empty() )
        {
            /*search the most left pointer by cur*/   
            while( cur!=NULL )
            {
                stk.push(cur);
                cur = cur->lchild;  
            }
            cur = stk.top();
            stk.pop();
            vec.push_back(cur->val);
            cur = cur->rchild; //traverse the right subtree 
        }
        print(vec);
    }

分析：首先根据当前的指针cur找到最左面的节点，并把路径上的结点的指针依次压栈，弹栈，之后去用相同的方法遍历右子树，最终完成中序遍历。

非递归后序遍历代码：

/*Post Order Traverse with non-recursion algorithm*/<strong>
    </strong>void PostOrderTraverse(BiTNode *T)
    {
        if(T==NULL) return ;
        vector<TElemType> vec;
        stack<BiTNode *> stk;
        stk.push(T);
        while( !stk.empty() )
        {
            BiTNode *cur = stk.top();
            stk.pop();
            vec.push_back(cur->val);
            if( cur->lchild!=NULL )
            {
                stk.push(cur->lchild);
            }
            if( cur->rchild!=NULL )
            {
                stk.push(cur->rchild);
            }
        }
        reverse( vec.begin(),vec.end() ); //reverse the result sequence 
        print(vec);
    }

重点分析：后序遍历的代码基本上和前序遍历的代码一致，唯一不同的就是左右子树的压栈顺序以及最终的将序列逆序两个地方。解释一下原因，前序遍历的过程为：中-左-右；后序遍历的过程为：左-右-中。做个变换：“中-左-右”==>”中-右-左”==>”左-右-中”。也就是说，后序遍历的结果序列分为两步：1.前序遍历的一个改版：先访问根节点，遍历右子树，再遍历左子树。2.将(1)的结果逆序即可。

完整代码：

#include<iostream>
    #include<stack>
    #include<cstdlib>
    #include<algorithm>
    #include<vector>
    
    using namespace std;
    
    typedef char TElemType;
    
    typedef struct BiTNode
    {
        TElemType val;
        BiTNode *lchild , *rchild;
        BiTNode(TElemType x):val(x),lchild(NULL),rchild(NULL) {}
    }tBiTNode;
    
    /*print the result*/
    void print( vector<TElemType> &vec )
    {
        int len = vec.size();
        for( int i=0;i<len;i++ )         
        {
            cout<<vec[i];     
        }
        cout<<endl;
    }
    
    /*input : ABD#G##E##C#F##*/
    void createTree(tBiTNode *&T)
    {
         TElemType x;
         cin>>x;
         if(x=='#')
         {
             T = NULL;          
         }
         else
         {
             T = new BiTNode(x);
             createTree(T->lchild);
             createTree(T->rchild);
         }
    }
    
    /*Pre Order Traverse with non-recursion algorithm*/
    void PreOrderTraverse(BiTNode *T)
    {
        if( T==NULL ) return ;
        vector<TElemType> vec; //contain the result sequence 
        stack<BiTNode *> stk;
        stk.push(T); //push the root into the stack 
        while( !stk.empty() )
        {
             BiTNode *cur = stk.top();
             stk.pop();
             vec.push_back(cur->val);
             if(cur->rchild!=NULL)
             {
                 stk.push(cur->rchild);
             }
             if(cur->lchild!=NULL)
             {
                 stk.push(cur->lchild);
             }
        }   
        print(vec);  //print the result 
    }
    
    /*In Order Traverse with non-recursion algorithm*/
    void InOrderTraverse(BiTNode *T)
    {
        if( T==NULL ) return ;
        stack<BiTNode *> stk;
        vector<TElemType> vec;
        BiTNode *cur = T->lchild;
        stk.push(T);
        while( cur!=NULL || !stk.empty() )
        {
            /*search the most left pointer by cur*/   
            while( cur!=NULL )
            {
                stk.push(cur);
                cur = cur->lchild;  
            }
            cur = stk.top();
            stk.pop();
            vec.push_back(cur->val);
            cur = cur->rchild; //traverse the right subtree 
        }
        print(vec);
    } 
    
    /*Post Order Traverse with non-recursion algorithm*/
    void PostOrderTraverse(BiTNode *T)
    {
        if(T==NULL) return ;
        vector<TElemType> vec;
        stack<BiTNode *> stk;
        stk.push(T);
        while( !stk.empty() )
        {
            BiTNode *cur = stk.top();
            stk.pop();
            vec.push_back(cur->val);
            if( cur->lchild!=NULL )
            {
                stk.push(cur->lchild);
            }
            if( cur->rchild!=NULL )
            {
                stk.push(cur->rchild);
            }
        }
        reverse( vec.begin(),vec.end() ); //reverse the result sequence 
        print(vec);
    }
    
    int main()
    {
        tBiTNode *p;
        createTree(p)    ;
        cout<<"Pre Order Traverse:"<<endl;
        PreOrderTraverse(p);
        cout<<"\nIn Order Traverse:"<<endl;
        InOrderTraverse(p);
        cout<<"\nPost Order Traverse:"<<endl;
        PostOrderTraverse(p); 
        cout<<endl;
        system("pause");
        return 0;
    }

结果和递归一致。

## 四、二叉树的层序遍历 ##

层序遍历代码：

/*Level Traverse*/
    void LevelTraverse(BiTNode *T)
    {
        queue<BiTNode *> que;
        if( T==NULL )  return ;
        vector<TElemType> vec;
        que.push(T);
        while( !que.empty() )
        {
            BiTNode *cur = que.front();
            que.pop();
            vec.push_back(cur->val);
            if( cur->lchild!=NULL )
            {
                que.push(cur->lchild);
            } 
            if( cur->rchild!=NULL )
            {
                que.push(cur->rchild);
            }
        }
        print(vec);
    }

分析：层序遍历就是相当于一个从根节点开始的BFS，那么可以想到用到队列，首先将根节点入队列，然后出队列，将其左右两个孩子的节点指针入队列，依次出队列，保持值，入左右孩子节点的指针，重复直到队列为空。

结果：  
![这里写图片描述][SouthEast 2]

## 五、二叉树的Morris遍历 ##

参考：[http://daiziguizhong.qiniudn.com/article22.html][http_daiziguizhong.qiniudn.com_article22.html]

转载请注明出处：[http://blog.csdn.net/lavorange/article/details/20641041][http_blog.csdn.net_lavorange_article_details_20641041]

[SouthEast]: /images/20220606/0b12ff3c23b44778a39bfcdf54a6b7a6.png
[SouthEast 1]: /images/20220606/3c7fb4a638404918915ae78c28e24546.png
[SouthEast 2]: /images/20220606/b14c39bfae9f48efbef117725e06b7c9.png
[http_daiziguizhong.qiniudn.com_article22.html]: http://daiziguizhong.qiniudn.com/article22.html
[http_blog.csdn.net_lavorange_article_details_20641041]: http://blog.csdn.net/lavorange/article/details/20641041