二叉树的前中后序遍历的递归与迭代算法

一,递归算法
二叉树的前、中、后序遍历的思路和程序都非常简单。

前中后序遍历的算法结构相同,只需要调整打印的位置。

前序遍历:打印根-访问左子树-访问右子树
中序遍历:访问左子树-打印根-访问右子树
后序遍历:访问左子树-访问右子树-打印根

遍历二叉树的算法中的基本操作是访问结点,所以不论是按照哪一种依次进行遍历,对有n个结点的二叉树,其时间复杂度为O(n).

由于是该算法是递归调用,所需辅助空间是遍历过程中栈的最大容量,即树的深度;一般情况下为O(logn);最坏情况下树的深度为n,则此时空间复杂度为O(n)。

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

二、迭代算法(1)
虽然递归算法的思路和程序都非常清晰,但其对栈空间有比较大的需求,当调用次数(即树的深度)达到一定量,此时便会出现栈空间不足的问题。

所以,我们便想采用非递归的算法来实现树的遍历。

因为树本身便是递归定义的,好像没有递归的结构还不太可以,因此我们应该想到用栈这个数据结构来模拟递归调用的过程,进而实现迭代算法的二叉树的遍历。

对于迭代算法,前序遍历和后续遍历的算法的程序结构是一样的。

前序:打印根-右子结点进栈-左子结点进栈——此时,由于栈具有先进后出的特点,得到的结果便是,根节点-左子节点-右子节点
后序:打印根-右子结点进栈-左子结点进栈——同样因为栈的先进后出的特点,得到的结果为,根节点-右子节点-左子节点。这时,得到的结果刚好是后序遍历的逆序,所以只需要对结果进行逆转就行了。

▲程序逻辑:
根不为空时压入栈
循环判断栈不为空时
弹出栈顶元素输出
右子节点压栈(前)/左子节点压栈(后)
左子节点压栈(前)/右子节点压栈(后)
反转结果(后)

//前序遍历

vector<int> preorderTraversal(TreeNode* root) { 
        vector<int> v;
        stack<TreeNode*> s;
        if(root!=nullptr)
            s.push(root);
        TreeNode* temp=nullptr;
        while(!s.empty())
        { 
            temp=s.top();
            s.pop();
            v.push_back(temp->val);
            if(temp->right!=nullptr)
                s.push(temp->right);
            if(temp->left!=nullptr)
                s.push(temp->left);

        }
        return v;
    }

//后序遍历

 vector<int> postorderTraversal(TreeNode* root) { 
        //迭代算法
        vector<int> v;
        stack<TreeNode*> s;
        if(root!=nullptr)
            s.push(root);

        TreeNode* temp=nullptr;
        while(!s.empty())
        { 
            temp=s.top();
            s.pop();
            v.push_back(temp->val);
            if(temp->left!=nullptr)
                s.push(temp->left);
            if(temp->right!=nullptr)
                s.push(temp->right);
        }
        reverse(v.begin(),v.end());
        return v;
    }

中序遍历与前、后序遍历的程序结构就不同了

程序逻辑:
初始将根节点赋给中间变量temp
循环,当temp不为空或者栈不为空时,
如果temp不为空,将temp入栈并temp向左子树移动
否则,出栈打印并temp向右子树移动

//中序遍历

vector<int> inorderTraversal(TreeNode* root) { 
        //迭代算法
        vector<int> v;

        stack<TreeNode*> s;
        TreeNode* temp=root;
        while(temp!=nullptr || !s.empty())
        { 
            if(temp!=nullptr)
            { 
                s.push(temp);
                temp=temp->left;
            }
            else
            { 
                temp=s.top();
                v.push_back(temp->val);
                s.pop();
                temp=temp->right;
            }
        }
        return v;
    }

三、迭代算法(2)
由于以上的迭代算法中,对于二叉树的前、中、后序的遍历的算法结构一致。

因此,为了保持算法结构的一致方便学习和记忆。有一种算法通过将“压栈”和“输出”这些操作设计成结构体或类。压入栈的不是结点了,而变成了对结点的操作,听上去是挺有趣的算法。

此时,便可以像递归的遍历算法一样只需要改变打印、操作左子结点、操作右子结点三行代码的位置便可实现前、中、后序遍历。

(突然有点事情,代码下次再放,嘻嘻)

    原文作者:第—缕阳光
    原文地址: https://blog.csdn.net/qq_45043381/article/details/108435383
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞