【数据结构和算法】全面剖析树的各类遍历方法

悠悠 2022-04-03 06:10 140阅读 0赞

# 【数据结构和算法】全面剖析树的各类遍历方法 #

2016年08月11日 15:10:52 [ZeeCoder][] 阅读数：11693 标签： [数据结构][Link 1][遍历][Link 2][算法][Link 3][class][] 更多

个人分类： [数据结构和算法][Link 4]

面试中常考到树的前序，中序，后序和层序遍历，这篇博文就带你深度剖析一下二叉树的各类遍历算法的实现

二叉树的遍历主要有四种，前序、中序、后序和层序

遍历的实现方式主要是：递归和非递归

递归遍历的实现非常容易，非递归的实现需要用到栈，难度系数要高一点。

# 一、二叉树节点的定义 #

二叉树的每个节点由节点值、左子树和右子树组成。

class TreeNode{
    public:
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7

# 二、二叉树的遍历方式 #

前序遍历：先访问根节点，再访问左子树，最后访问右子树

中序遍历：先访问左子树，再访问根节点，最后访问右子树

后序遍历：先访问左子树，再访问右子树，最后访问根节点

层序遍历：每一层从左到右访问每一个节点。

举例说明:(以下面的二叉树来说明这四种遍历)

![2018122019220140][]

前序遍历：ABDFGHIEC   
中序遍历：FDHGIBEAC   
后序遍历：FHIGDEBCA   
层序遍历：ABCDEFGHI

> 大家可以根据这个例子先熟悉一下这四种遍历，如有不懂的，建议先去google一下，再接着阅读本文

# 三、前序遍历 #

## 递归版本 ##

按照遍历的顺序很容易就能写出下列代码：

以下代码均在leetcode测试通过，二叉树前序遍历的原题链接：[戳我！leetcode直通车！上车啦！][leetcode]

vector<int> preorderTraversal(TreeNode* root){
        vector<int> ret;
        dfsPreOrder(root,ret);
        return ret;
    }
    void dfsPreOrder(TreeNode* root,vector<int> &ret){
        if(root==NULL) return;
        ret.push_back(root->val);//存储根节点
        if(root->left!=NULL) dfsPreOrder(root->left,ret);//访问左子树
        if(root->right!=NULL) dfsPreOrder(root->right,ret);//访问右子树
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11

## 非递归版本 ##

非递归版本需要利用辅助栈来实现

*  1.首先把根节点压入栈中
 *  2.此时栈顶元素即为当前根节点，弹出并访问即可
 *  3.把当前根节点的右子树和左子树分别入栈，考虑到栈是先进后出，所以必须右子树先入栈，左子树后入栈
 *  4.重复2,3步骤，直到栈为空为止

vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root==NULL) return ret;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* tp = st.top();//取出栈顶元素
            st.pop();
            ret.push_back(tp->val);//先访问根节点
            if(tp->right!=NULL) st.push(tp->right);//由于栈时先进后出，考虑到访问顺序，先将右子树压栈
            if(tp->left!=NULL) st.push(tp->left);//将左子树压栈
        }
        return ret;
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15

# 四、中序遍历 #

## 递归版本 ##

中序遍历的访问顺序依次是左子树->根节点->右子树，按照递归的思想依次访问即可

以下代码均在leetcode测试通过，二叉树中序遍历的原题链接：[戳我！leetcode直通车！上车啦！][leetcode 1]

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        inorder(root,ret);
        return ret;
    }
    void inorder(TreeNode* p,vector<int>& ret)
    {
        if(p==NULL) return;
        inorder(p->left,ret);//访问左子树
        ret.push_back(p->val);//访问根节点
        inorder(p->right,ret);//访问右子树
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12

## 非递归版本 ##

中序遍历的非递归版本比前序稍微复杂一点，除了用到辅助栈之外，还需要一个指针p指向下一个待访问的节点

*  如果p非空，则将p入栈，p指向p的左子树
 *  如果p为空，说明此时左子树已经访问到尽头了，弹出当前栈顶元素，进行访问，并把p设置成p的右子树的左子树，即下一个待访问的节点

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        TreeNode* p = root;
        stack<TreeNode*> st;
        while(!st.empty()||p!=NULL){
            if(p){//p非空，代表还有左子树，继续
                st.push(p);
                p=p->left;
            }
            else{//如果为空，代表左子树已经走到尽头了
                p = st.top();
                st.pop();
                ret.push_back(p->val);//访问栈顶元素
                if(p->right) {
                    st.push(p->right);//如果存在右子树，将右子树入栈
                    p = p->right->left;//p始终为下一个待访问的节点
                }
                else p=NULL;
            }
        }
        return ret;
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20
 *  21
 *  22

# 五、后序遍历 #

## 递归版本 ##

递归版本还是一样，按照访问顺序来写代码即可。

以下代码均在leetcode测试通过，二叉树后序遍历的原题链接：[戳我！leetcode直通车！上车啦！][leetcode 2]

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        inorder(root,ret);
        return ret;
     }
    void inorder(TreeNode* p,vector<int>& ret)
    {
        if(p==NULL) return;
        inorder(p->left,ret);//访问左子树
        inorder(p->right,ret);//访问右子树
        ret.push_back(p->val);//访问根节点
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12

## 非递归版本 ##

采用一个辅助栈和两个指针p和r，p代表下一个需要访问的节点，r代表上一次需要访问的节点

1、如果p非空，则将p入栈，p指向p的左子树

2、如果p为空，代表左子树到了尽头，此时判断栈顶元素

*  如果栈顶元素存在右子树且没有被访问过(等于r代表被访问过)，则右子树入栈，p指向右子树的左子树
 *  如果栈顶元素不存在或者已经被访问过，则弹出栈顶元素，访问，然后p置为null，r记录上一次访问的节点p

vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        TreeNode* p = root;
        stack<TreeNode*> st;
        TreeNode* r = NULL;
        while(p||!st.empty())
        {
            if(p)
            {
                st.push(p);
                p = p -> left;
            }
            else
            {
                p = st.top();
                if(p->right&&p->right!=r)
                {
                    p = p->right;
                    st.push(p);
                    p = p->left;
                }
                else 
                {
                    p = st.top();
                    st.pop();
                    ret.push_back(p->val);
                    r= p;
                    p = NULL;
                }
            }
        }
        return ret;
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20
 *  21
 *  22
 *  23
 *  24
 *  25
 *  26
 *  27
 *  28
 *  29
 *  30
 *  31
 *  32
 *  33

还有另一种解法，大家可以看看前序遍历的非递归版本，访问顺序依次是根节点->左子树->右子树，如果将压栈顺序改动一下，可以很容易得到根节点->右子树->左子树，观察这个顺序和后序遍历左子树->右子树->根节点正好反序。

vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root==NULL) return ret;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
           TreeNode* tmp = st.top();
           ret.push_back(tmp->val);//先访问根节点
           st.pop();
           if(tmp->left!=NULL) st.push(tmp->left);//再访问左子树
           if(tmp->right!=NULL) st.push(tmp->right);//最后访问右子树
        }
        reverse(ret.begin(),ret.end());//将结果反序输出
        return ret;
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16

# 六、层序遍历 #

层序遍历，即按层序从左到右输出二叉树的每个节点。如例子中的A(第一层)BC(第二层)DE(第三层)FG(第四层)HI(第五层)

层序遍历需要借助队列queue来完成，因为要满足先进先去的访问顺序。具体思路看代码：

以下代码均在leetcode测试通过，二叉树层序遍历的原题链接：[戳我！leetcode直通车！上车啦！][leetcode 3]

vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(root==NULL) return ret;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            vector<int> temp;
            queue<TreeNode*> tmpQue;//存储下一层需要访问的节点
            while(!que.empty())//从左到右依次访问本层
            {
                TreeNode* tempNode = que.front();
                que.pop();
                temp.push_back(tempNode->val);
                if(tempNode->left!=NULL) tmpQue.push(tempNode->left);//左子树压入队列
                if(tempNode->right!=NULL) tmpQue.push(tempNode->right);//右子树压入队列
            }
            ret.push_back(temp);
            que=tmpQue;//访问下一层
        }
        return ret;
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20
 *  21
 *  22

# 七、其他经典考题 #

## 根据前序和中序遍历来构造二叉树 ##

前序遍历的顺序是：根节点->左子树->右子树，中序遍历的顺序时：左子树->根节点->右子树。

在前序遍历中第一个节点为根节点，然后去中序遍历中找到根节点，则其左边为左子树，右边为右子树

例如前序遍历ABC，中序遍历BAC,在前序遍历中找到根节点A，在中序遍历中A的左边B为左子树，右边C为右子树。

然后一次递归下去，就可以把整棵数构造出来了。

以下代码均在leetcode测试通过，构造二叉树的原题链接：[戳我！leetcode直通车！上车啦！][leetcode 4]

typedef vector<int>::iterator vi;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()||inorder.empty()) return (TreeNode*)NULL;
        vi preStart = preorder.begin();
        vi preEnd = preorder.end()-1;
        vi inStart = inorder.begin();
        vi inEnd = inorder.end()-1;
        return constructTree(preStart,preEnd,inStart,inEnd);
    }
    TreeNode* constructTree(vi preStart,vi preEnd,vi inStart,vi inEnd)
    {
        if(preStart>preEnd||inStart>inEnd) return NULL;
        //前序遍历的第一个节点为根节点
        TreeNode* root = new TreeNode(*preStart);
        if(preStart==preEnd||inStart==inEnd) return root;
        vi rootIn = inStart;
        while(rootIn!=inEnd){//在中序遍历中找到根节点
            if(*rootIn==*preStart) break;
            else ++rootIn;
        }
        root->left = constructTree(preStart+1,preStart+(rootIn-inStart),inStart,rootIn-1);//递归构造左子树
        root->right = constructTree(preStart+(rootIn-inStart)+1,preEnd,rootIn+1,inEnd);//递归构造右子树
        return root;
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20
 *  21
 *  22
 *  23
 *  24

## 根据中序和后序遍历构造二叉树 ##

与上面的题目比较相似，后序遍历中最后一个节点为根节点，然后在中序遍历中找到根节点，左边为左子树，右边为右子树。

以下代码均在leetcode测试通过，构造二叉树的原题链接：[戳我！leetcode直通车！上车啦！][leetcode 4]

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.empty()||postorder.empty()) return NULL;
        return constructTree(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
    }
    TreeNode* constructTree(vector<int>& inorder, vector<int>& postorder, int inStart,int inEnd,int postStart,int postEnd)
    {
        if(postStart>postEnd||inStart>inEnd) return NULL;
        TreeNode* root = new TreeNode(postorder[postEnd]);
        if(postStart==postEnd||inStart==inEnd) return root;
        int i ;
        for(i = inStart ;i<inEnd;i++)//在中序遍历中找到根节点
        {
            if(inorder[i]==postorder[postEnd]) break;
        }
        root->left = constructTree(inorder,postorder,inStart,i-1,postStart,postStart+i-inStart-1);//递归构造左子树
        root->right = constructTree(inorder,postorder,i+1,inEnd,postStart+i-inStart,postEnd-1);//递归构造右子树
        return root;
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18

## 求二叉树的深度 ##

采用深度优先搜索，可以很容易计算出深度

以下代码均在leetcode测试通过，二叉树的深度的原题链接：[戳我！leetcode直通车！上车啦！][leetcode 5]

int maxDepth(TreeNode* root) {
        return DfsTree(root);
    }
    int DfsTree(TreeNode* root){
        if(root==NULL) return 0;
        int left = DfsTree(root->left);//左子树的深度
        int right = DfsTree(root->right);//右子树的深度
        return left>right?left+1:right+1;//比较左右子树的深度，取最大值
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10

## 判断是否为平衡二叉树 ##

利用上面求深度的思想，求出左右子树的深度，判断它们相差是否大于1，如果大于则返回false。

以下代码均在leetcode测试通过，判断平衡二叉树的原题链接：[戳我！leetcode直通车！上车啦！][leetcode 6]

bool isBalanced(TreeNode* root) {
        return dfsTree(root)!=-1;
    }
    int dfsTree(TreeNode* root)
    {
        if(root==NULL) return 0;
        int left = dfsTree(root->left);//求左子树的深度
        if(left == -1) return -1;//返回-1代表左子树不平衡
        int right = dfsTree(root->right);//求右子树的深度
        if(right== -1) return -1;//返回-1代表右子树不平衡
        if(abs(left-right)>1) return -1;//如果左右子树均平衡，则判断它们是否相差小于等于1
        return max(left,right)+1;//返回该根节点树的深度
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13

本篇博客到这里就结束了，当然二叉树的变种考题还有很多中，后序也会陆续收集进来，敬请关注[我的小站][Link 5]。

如有任何疑问，可以在下方留言去留言，也可以直接发邮件给我,详见[联系方式][Link 6]

[https://blog.csdn.net/terence1212/article/details/52182836][https_blog.csdn.net_terence1212_article_details_52182836]

[ZeeCoder]: https://me.csdn.net/terence1212
[Link 1]: http://so.csdn.net/so/search/s.do?q=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84&t=blog
[Link 2]: http://so.csdn.net/so/search/s.do?q=%E9%81%8D%E5%8E%86&t=blog
[Link 3]: http://so.csdn.net/so/search/s.do?q=%E7%AE%97%E6%B3%95&t=blog
[class]: http://so.csdn.net/so/search/s.do?q=class&t=blog
[Link 4]: https://blog.csdn.net/terence1212/article/category/5966503
[2018122019220140]: /images/20220403/5589699cdc3544bebdbf80e3dfbf8a60.png
[leetcode]: https://leetcode.com/problems/binary-tree-preorder-traversal/
[leetcode 1]: https://leetcode.com/problems/binary-tree-inorder-traversal/
[leetcode 2]: https://leetcode.com/problems/binary-tree-postorder-traversal/
[leetcode 3]: https://leetcode.com/problems/binary-tree-level-order-traversal/
[leetcode 4]: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[leetcode 5]: https://leetcode.com/problems/maximum-depth-of-binary-tree/
[leetcode 6]: https://leetcode.com/problems/balanced-binary-tree/
[Link 5]: http://zcheng.ren/
[Link 6]: http://zcheng.ren/about/
[https_blog.csdn.net_terence1212_article_details_52182836]: https://blog.csdn.net/terence1212/article/details/52182836