数据结构与算法系列之二叉树的遍历

﹏ヽ暗。殇╰゛Y 2022-05-29 08:45 202阅读 0赞

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

*  **转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net_u011475210]**
 *  **个人博客：[https://wordzzzz.github.io/][https_wordzzzz.github.io] [https://wordzzzz.gitee.io/][https_wordzzzz.gitee.io]**
 *  **代码地址：[https://github.com/WordZzzz/DS-A/blob/master/BinaryTreeNode.cpp][https_github.com_WordZzzz_DS-A_blob_master_BinaryTreeNode.cpp]**
 *  **开发平台：Win10 + visual studio 2015**
 *  **编  者：WordZzzz**

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

*   *  前言
     *  构造二叉树
     *  前序遍历
        
         *  1.递归实现
         *  2.非递归实现
     *  中序遍历
        
         *  1.递归实现
         *  2.非递归实现
     *  后序遍历
        
         *  1.递归实现
         *  2.非递归实现
     *  题目汇总

## 前言 ##

最近在准备春招实习，正好复习到二叉树，干脆就把二叉树的遍历整理一下，同时把之前刷《剑指offer》中所有关于数的题目都贴在文章尾部，方便自己，也方便大家复习。本文全部代码已经贴在wordzzzz的[github][https_github.com_WordZzzz_DS-A_blob_master_BinaryTreeNode.cpp]上。

在计算机科学里，树的遍历（也称为树的搜索）是图的遍历的一种，指的是按照某种规则，不重复地访问某种树的所有节点的过程。具体的访问操作可能是检查节点的值、更新节点的值等。不同的遍历方式，其访问节点的顺序是不一样的。以下虽然描述的是二叉树的遍历算法，但它们也适用于其他树形结构。

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度优先遍历和广度优先遍历两大类。其中，深度优先遍历又包括前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而面试中往往要求我们掌握二叉树的非递归遍历。对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。

## 构造二叉树 ##

之前在牛客网上刷题只需要写功能函数就可以了，但是为了准备春招，有些代码还是要从头到尾写一遍。本文中，我根据《剑指offer》中的[序列化二叉树][Link 1]中的方法来构造二叉树。

#include <iostream>
    #include <stack>
    #include <queue>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    struct BinaryTreeNode {
        int val;
        BinaryTreeNode* left;
        BinaryTreeNode* right;
        BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    /*  
     *  反序列化二叉树辅助函数
     *  参数：
     *      str：前序遍历的字符串
     *  返回值：
     *      ret：当前根节点
     */
    BinaryTreeNode *deserializeHelper(string &s)
    {
        if (s.empty())
            return NULL;
        if (s[0] == '$')
        {
            s = s.substr(2);
            return NULL;
        }
        BinaryTreeNode *ret = new BinaryTreeNode(stoi(s));
        s = s.substr(s.find_first_of(',') + 1);
        ret->left = deserializeHelper(s);
        ret->right = deserializeHelper(s);
        return ret;
    }
    
    
    /*  
     *  反序列化二叉树：string --》 BinaryTreeNode
     *  参数：
     *      str：前序遍历的字符串，e.g:"1, 2, $, $, 3, $, $,"
     *  返回值：
     *      deserializeHelper(str)：生成树的根节点
     */
    BinaryTreeNode* Deserialize(string str)
    {
        if (str == "")
            return NULL;
        return deserializeHelper(str);
    }
    
    /*  
     *  序列化二叉树辅助函数
     *  参数：
     *      node：树的根节点
     *      str：前序遍历后字符串
     *  返回值：
     *      
     */
    void serializeHelper(BinaryTreeNode *node, string& str)
    {
        if (node == NULL)
        {
            str.push_back('$');
            str.push_back(',');
            return;
        }
        str += to_string(node->val);
        str.push_back(',');
        serializeHelper(node->left, str);
        serializeHelper(node->right, str);
    }
    
    /*  
     *  序列化二叉树：BinaryTreeNode --》 string
     *  参数：
     *      pRoot：树的根节点
     *  返回值：
     *      ret：前序遍历后的字符串
     */
    char* Serialize(BinaryTreeNode *pRoot)
    {
        if (pRoot == NULL)
            return NULL;
        string s = "";
        serializeHelper(pRoot, s);
    
        char *ret = new char[s.length() + 1];
        strcpy_s(ret, strlen(s.c_str()) + 1, s.c_str());
        return ret;
    }
    
    /*  
     *  打印二叉树辅助函数
     */
    void PrintTreeNode(BinaryTreeNode* pNode)
    {
        if (pNode != nullptr)
        {
            printf("value of this node is: %d\n", pNode->val);
    
            if (pNode->left != nullptr)
                printf("value of its left child is: %d.\n", pNode->left->val);
            else
                printf("left child is null.\n");
    
            if (pNode->right != nullptr)
                printf("value of its right child is: %d.\n", pNode->right->val);
            else
                printf("right child is null.\n");
        }
        else
        {
            printf("this node is null.\n");
        }
    
        printf("\n");
    }
    
    /*  
     *  打印二叉树函数
     */
    void PrintTree(BinaryTreeNode* pRoot)
    {
        PrintTreeNode(pRoot);
    
        if (pRoot != nullptr)
        {
            if (pRoot->left != nullptr)
                PrintTree(pRoot->left);
    
            if (pRoot->right != nullptr)
                PrintTree(pRoot->right);
        }
    }
    
    /*  
     *  销毁二叉树函数
     */
    void DestroyTree(BinaryTreeNode* pRoot)
    {
        if (pRoot != nullptr)
        {
            BinaryTreeNode* pLeft = pRoot->left;
            BinaryTreeNode* pRight = pRoot->right;
    
            delete pRoot;
            pRoot = nullptr;
    
            DestroyTree(pLeft);
            DestroyTree(pRight);
        }
    }
    
    int main(int argc, char *argv[])
    {
        string str;
        cin >> str;
        BinaryTreeNode *pRoot = Deserialize(str);
        PrintTree(pRoot);
        DestroyTree(pRoot);
        return 0;
    }

测试

1,2,$,$,3,$,$,
    value of this node is: 1
    value of its left child is: 2.
    value of its right child is: 3.
    
    value of this node is: 2
    left child is null.
    right child is null.
    
    value of this node is: 3
    left child is null.
    right child is null.

## 前序遍历 ##

前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。

### 1.递归实现 ###

/*  
     *  递归前序遍历
     */
    void preOrder1(BinaryTreeNode *pRoot) 
    {
        if (pRoot != NULL)
        {
            cout << pRoot->val << " ";
            preOrder1(pRoot->left);
            preOrder1(pRoot->right);
        }
    }

### 2.非递归实现 ###

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：

对于任一结点P：

*  访问结点P，并将结点P入栈;
 *  判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
 *  直到P为NULL并且栈为空，则遍历结束。

/*  非递归前序遍历
    */
    /*  
     *  非递归前序遍历
     */
    void preOrder2(BinaryTreeNode *pRoot)
    {
        stack<BinaryTreeNode *> s;
        BinaryTreeNode *p = pRoot;
        while (p != NULL || !s.empty())
        {
            while (p != NULL)
            {
                cout << p->val << " ";
                s.push(p);
                p = p->left;
            }
            if (!s.empty())
            {
                p = s.top();
                s.pop();
                p = p->right;
            }
        }
    }

## 中序遍历 ##

中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。

### 1.递归实现 ###

/*  
     *  递归中序遍历
     */
    void inOrder1(BinaryTreeNode *pRoot)
    {
        if (pRoot != NULL)
        {
            inOrder1(pRoot->left);
            cout << pRoot->val << " ";
            inOrder1(pRoot->right);
        }
    }

### 2.非递归实现 ###

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：

对于任一结点P，

*  若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
 *  若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
 *  直到P为NULL并且栈为空则遍历结束

/*  
     *  非递归中序遍历
     */
    void inOrder2(BinaryTreeNode *pRoot)
    {
        stack<BinaryTreeNode *> s;
        BinaryTreeNode *p = pRoot;
        while (p != NULL || !s.empty())
        {
            while (p != NULL)
            {
                s.push(p);
                p = p->left;
            }
            if (!s.empty())
            {
                p = s.top();
                cout << p->val << " ";
                s.pop();
                p = p->right;
            }
        }
    }

## 后序遍历 ##

后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。

### 1.递归实现 ###

/*  
     *  递归后序遍历
     */
    void postOrder1(BinaryTreeNode *pRoot)
    {
        if (pRoot != NULL)
        {
            postOrder1(pRoot->left);
            postOrder1(pRoot->right);
            cout << pRoot->val << " ";
        }
    }

### 2.非递归实现 ###

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。

要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

/*  
     *  非递归后序遍历
     */
    void postOrder2(BinaryTreeNode *pRoot)
    {
        stack<BinaryTreeNode *> s;
        BinaryTreeNode *cur;                    //当前结点 
        BinaryTreeNode *pre = NULL;             //前一次访问的结点 
        s.push(pRoot);
        while (!s.empty())
        {
            cur = s.top();
            if ((cur->left == NULL && cur->right == NULL) ||
                (pre != NULL && (pre == cur->left || pre == cur->right)))
            {
                cout << cur->val << " ";  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
                s.pop();
                pre = cur;
            }
            else
            {
                if (cur->right != NULL)
                    s.push(cur->right);
                if (cur->left != NULL)
                    s.push(cur->left);
            }
        }
    }

## 题目汇总 ##

*  [《剑指offer》刷题笔记（树）：重建二叉树][offer]
 *  [《剑指offer》刷题笔记（代码的鲁棒性）：树的子结构][offer 1]
 *  [《剑指offer》刷题笔记（面试思路）：二叉树的镜像][offer 2]
 *  [《剑指offer》刷题笔记（举例让抽象具体化）：从上往下打印二叉树][offer 3]
 *  [《剑指offer》刷题笔记（举例让抽象具体化）：二叉树中和为某一值的路径][offer 4]
 *  [《剑指offer》刷题笔记（分解让复杂问题简单）：二叉搜索树与双向链表][offer 5]
 *  [《剑指offer》刷题笔记（知识迁移能力）：二叉树的深度][offer 6]
 *  [《剑指offer》刷题笔记（知识迁移能力）：平衡二叉树][offer 7]
 *  [《剑指offer》刷题笔记（综合）：树中两个结点的最低公共祖先][offer 8]
 *  [《剑指offer》刷题笔记（树）：二叉树的下一个结点][offer 9]
 *  [《剑指offer》刷题笔记（树）：对称的二叉树][offer 10]
 *  [《剑指offer》刷题笔记（树）：把二叉树打印成多行][offer 11]
 *  [《剑指offer》刷题笔记（树）：按之字形顺序打印二叉树][offer 12]
 *  [《剑指offer》刷题笔记（树）：序列化二叉树][Link 1]
 *  [《剑指offer》刷题笔记（树）：二叉搜索树的第k个结点][offer_k]

参考链接：  
\- [二叉树的非递归遍历][Link 2]  
\- [数据结构（六）——二叉树 前序、中序、后序、层次遍历及非递归实现 查找、统计个数、比较、求深度的递归实现][Link 3]

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

**系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～**

**完的汪(∪｡∪)｡｡｡zzz**

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

[http_blog.csdn.net_u011475210]: http://blog.csdn.net/u011475210
[https_wordzzzz.github.io]: https://wordzzzz.github.io/
[https_wordzzzz.gitee.io]: https://wordzzzz.gitee.io/
[https_github.com_WordZzzz_DS-A_blob_master_BinaryTreeNode.cpp]: https://github.com/WordZzzz/DS-A/blob/master/BinaryTreeNode.cpp
[Link 1]: http://blog.csdn.net/u011475210/article/details/78889876
[offer]: http://blog.csdn.net/u011475210/article/details/78109978
[offer 1]: http://blog.csdn.net/u011475210/article/details/78259143
[offer 2]: http://blog.csdn.net/u011475210/article/details/77865056
[offer 3]: http://blog.csdn.net/u011475210/article/details/78443771
[offer 4]: http://blog.csdn.net/u011475210/article/details/78465662
[offer 5]: http://blog.csdn.net/u011475210/article/details/78580852
[offer 6]: http://blog.csdn.net/u011475210/article/details/77833260
[offer 7]: http://blog.csdn.net/u011475210/article/details/78787462
[offer 8]: http://blog.csdn.net/u011475210/article/details/78849323
[offer 9]: http://blog.csdn.net/u011475210/article/details/78875485
[offer 10]: http://blog.csdn.net/u011475210/article/details/78876309
[offer 11]: http://blog.csdn.net/u011475210/article/details/78880059
[offer 12]: http://blog.csdn.net/u011475210/article/details/78880066
[offer_k]: http://blog.csdn.net/u011475210/article/details/78893566
[Link 2]: http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html
[Link 3]: http://blog.csdn.net/fansongy/article/details/6798278