数据结构-二叉树的前序、中序、后序遍历的递归和非递归实现

迈不过友情╰ 2022-06-15 05:37 107阅读 0赞

在leetcode刷题，很多地方会考察到二叉树的遍历。  
深度优先遍历DFS和广度优先遍历BFS看这里[**【链接】**][Link 1]  
这篇总结一下前序、中序、后序遍历的实现，备忘。

# 1.基础知识 #

二叉树的定义如下：

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

序–指的是根结点被遍历的顺序。  
前序遍历： 根结点，左子树，右子树  
中序遍历：左子树，根结点，右子树  
后序遍历：左子树，右子树，根结点  
这里拿百度百科的图片作为示例，这个不是二叉树。  
![这里写图片描述][SouthEast]

# 2.递归实现 #

递归非常好理解，代码简明跟上面的文字说明一模一样。  
可以看到，只是三行代码的位置顺序调换了而已。

//前序遍历
    void preOrder(TreeNode* root,vector<int>& values) {
        if (root) {
            values.push_back(root->val);//先访问根结点
            preOrder(root->left,values);        
            preOrder(root->right,values);
        }
    }
    //中序遍历
    void inOrder(TreeNode* root,vector<int>& values) {
        if (root) {
            inOrder(root->left,values);
            values.push_back(root->val);
            inOrder(root->right,values);
        }
    }
    //后序遍历
    void postOrder(TreeNode* root,vector<int>& values) {
        if (root) {     
            postOrder(root->left,values);       
            postOrder(root->right,values);
            values.push_back(root->val);//最后访问根结点
        }
    }

# 3.非递归实现 #

这里需要使用数据结构栈stack用来保存节点。  
1）先序遍历  
对于一个节点，先将根结点入栈，遍历左子树，后面再出栈遍历右子树。

void preOrder(TreeNode* root,vector<int>& values) {
        stack<TreeNode*> nodes;
        while (!nodes.empty() || root) {
            if (root) {
                values.push_back(root->val);//先访问根结点
                nodes.push(root);
                root = root->left;//再转到左子树
            }
            else {
       //左边已经遍历到底部，回到根结点，然后转到右子树
                root = nodes.top();
                nodes.pop();
                root = root->right;
            }
        }
    }

2）中序遍历

void inOrder(TreeNode* root, vector<int>& values) {
        stack<TreeNode*> nodes;
        while (!nodes.empty() || root) {
            if (root) {
       //一直遍历到左子树的最底部
                nodes.push(root);
                root = root->left;
            }
            else {
       //左子树遍历完，返回并访问根结点，转到右子树
                root = nodes.top();
                nodes.pop();
                values.push_back(root->val);//访问根结点
                root = root->right;//转到右子树
            }
        }
    }

3）后序遍历  
根结点被访问的条件是其左右子节点均已被访问或者不存在左右子节点。  
所以可以用一个变量来记录上一次访问的节点。通过判断上一次访问的节点是否其右节点来决定能否访问根结点。

void postOrder(TreeNode* root, vector<int>& values) {
        stack<TreeNode*> nodes;
        TreeNode* pLast = NULL;
        TreeNode* pCur;
        nodes.push(root);
        while (!nodes.empty()) {
            pCur = nodes.top();
            //节点被访问的条件：没有左右子节点或只有左子节点且子节点已被访问或右子节点已被访问
            if ((pCur->left == NULL&&pCur->right == NULL) || (pCur->right == NULL&&pLast == pCur->left) || pLast == pCur->right)
            {
                values.push_back(pCur->val);
                pLast = pCur;
                nodes.pop();
            }
            else {
       //右节点先入栈，因为先进后出
                if (pCur->right)
                    nodes.push(pCur->right);
                if (pCur->left)
                    nodes.push(pCur->left);
            }
        }
    }

[Link 1]: http://blog.csdn.net/my_lovely_lemon_tree/article/details/72722726
[SouthEast]: /images/20220615/cdf0577145794894833323b9168de284.png