原文链接:https://blog.csdn.net/Monster_ii/article/details/82115772

二叉树的前中后和层序遍历详细图解(递归和非递归写法)_C/C++_Monster_ii的博客-CSDN博客

二叉树的递归/非递归遍历

前序遍历

递归版本:

//前序遍历
void preorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        path.push_back(root->val);
        preorder(root->left, path);
        preorder(root->right, path);
    }
}

非递归版本:

 //非递归前序遍历
 void preorderTraversal(TreeNode *root, vector<int> &path)
 {
     stack<TreeNode *> s;
     TreeNode *p = root;
     while(p != NULL || !s.empty())
     {
         while(p != NULL)
         {
             path.push_back(p->val);
             s.push(p);
             p = p->left;
         }
         if(!s.empty())
         {
             p = s.top();
             s.pop();
             p = p->right;
         }
     }
 }

非递归的写法比递归写法要麻烦一点,要用到栈来存储树的结点,在理解非递归方法的时候要重点理解栈中保存的元素的共同点是什么,在前序访问中,栈中元素都是自己和自己的左孩子都访问过了,而右孩子还没有访问到的节点,如果不太懂可以看下面的详细步骤图解。

1、首先我们要用一个指针(cur)来指向当前访问的结点

https://tva1.sinaimg.cn/large/00831rSTly1gcj2901j9ej30fb0ant93.jpg

发现这个节点不为空,就将它的数据输出,然后将这个节点的地址(图上的栈中写了节点的值是为了便于理解,实际上栈中保存的是节点地址)压栈。

https://tva1.sinaimg.cn/large/00831rSTly1gcj292pvtyj30h50a9jra.jpg

再去访问它的左子树,发现左孩子结点依旧不为空,继续输出并压栈。

https://tva1.sinaimg.cn/large/00831rSTly1gcj29ggmfcj30hy0am74s.jpg

同理压栈D节点

https://tva1.sinaimg.cn/large/00831rSTly1gcj29o9omtj30kc0awaal.jpg

然后访问D的左孩子,发现为空,便从栈中拿出栈顶结点top,让cur = top->right,便访问到了D的右孩子。

https://tva1.sinaimg.cn/large/00831rSTly1gcj29ty8bnj30mm0e8gmf.jpg

发现D的右孩子还是为空,这个看一下栈,发现栈不为空,说明还存在右孩子没被访问过的节点,就继续从栈中拿出栈顶结点top,让cur = top->right,便访问到了B的右孩子。

https://tva1.sinaimg.cn/large/00831rSTly1gcj2a2w0ftj30lb0dnjs6.jpg

B的右孩子处理方法和D一样,然后再从栈中拿出A节点,去访问A的右孩子C,在访问到G节点的右孩子之后,发现当前节点cur为空,栈中也没有元素可以取出来了,这时候就代表整棵树都被访问过了,便结束循环。

https://tva1.sinaimg.cn/large/00831rSTly1gcj2afv4h8j30hz0e23z9.jpg

最后输出的前序访问序列便是:ABDECFG


中序遍历

递归版本:

//中序遍历
void inorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        inorder(root->left, path);
        path.push_back(root->val);
        inorder(root->right, path);
    }
}

非递归版本:

//非递归中序遍历
void inorderTraversal(TreeNode *root, vector<int> &path)
{
    stack<TreeNode *> s;
    TreeNode *p = root;
    while(p != NULL || !s.empty())
    {
        while(p != NULL)
        {
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            path.push_back(p->val);
            s.pop();
            p = p->right;
        }
    }
}

后序遍历

递归版本:

//后续遍历
void postorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        postorder(root->left, path);
        postorder(root->right, path);
        path.push_back(root->val);
    }
}

非递归版本:

//非递归后序遍历-迭代
class Solution {
public:
    vector<int> res;
    stack<TreeNode* > s;

    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return res;
        }
        TreeNode *prev = nullptr;
        while (root != nullptr || !s.empty()) {
            while (root != NULL){
                s.emplace(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            if(root->right == nullptr || root->right == prev) {
                res.emplace_back(root->val);
                prev = root;
                root = nullptr;
            } else {
                s.emplace(root);
                root = root->right;
            }
        }
        return res;
    }
};

还是沿着左子树一路往下走,将路过的节点都压栈,直到走到空节点。

这里写图片描述

然后从栈中看一下栈顶元素(只看一眼,用top指针记下,先不出栈),如果top节点没有右子树,或者last等于top的右孩子,说明top的右子树不存在或者遍历过了,就输出top节点的值,并将栈顶元素pop掉(出栈),反之则是从左子树回到根节点的,接下来要去右子树。

这里写图片描述

如图,top的右孩子为空,说明右子树不存在,就可以输出top的值并pop掉栈顶了,这时候用last指针记下top指向的节点,代表上一次处理的节点。(这一过程cur始终没有动,一直指向空)

这里写图片描述

继续从栈顶看一个元素记为top,然后发现top的右孩子不为空,而且last也不等于top->right,就使cur = top->right,回到第一步,用同样的方法来处理top的右子树,下一次回来的时候,last指针指向的是E节点。

这里写图片描述

这时候发现top的右孩子不为空,但是last等于top->right,说明top的右子树遍历完成,下一步就要输出top的值并且将这个节点出栈,下一次再从栈中看一个栈顶元素A即为top。

这里写图片描述

这时候再比较,发现top的right不为空,而且last也不等于top->right,说明top有右子树并且还没有遍历过,就让cur = top->right,回到第一步用同样的方法来遍历A的右子树。到最后,cur访问到了G的左孩子,而top也一路出栈到了A节点,发现cur为空,并且栈中也为空,这时候便代表整个树已经遍历完成,结束循环。

这里写图片描述

最后输出的中序访问序列为:DEBFGCA


更简单的非递归遍历二叉树的方法

这里我给出统一的实现思路和代码风格的方法,完成对二叉树的三种非递归遍历。

更简单的非递归前序遍历

//更简单的非递归前序遍历
void preorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
            s.push(make_pair(root, true));
        }
    }
}

更简单的非递归中序遍历

//更简单的非递归中序遍历
void inorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root->right, false));
            s.push(make_pair(root, true));
            s.push(make_pair(root->left, false));
        }
    }
}

更简单的非递归后序遍历

//更简单的非递归后序遍历
void postorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root, true));
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
        }
    }
}

层序遍历

层序遍历是比较接近人的思维方式的一种遍历方法,将二叉树的每一层分别遍历,直到最后的叶子节点被全部遍历完,这里要用到的辅助数据结构是队列,队列具有先进先出的性质。

void LevelOrder(TreeNode *root, vector<int> &path) {
        stack<TreeNode * > q;
        TreeNode * front;

        if (root == NULL) return;

        q.push(root);

        while (!q.empty()) {
            front = q.top();
            q.pop();

            if (front -> left)
                q.push(front -> left);

            if (front -> right)
                q.push(front -> right);
            path.push_back(front->val);
        }
    }
Last modification:September 29th, 2020 at 12:16 pm
如果觉得我的文章对你有用,请随意赞赏