当前位置：首页 > news >正文

二叉树非递归遍历（C++）

news 来源：原创 2024/9/30 2:21:58

文章目录

前言
一、前序遍历
二、中序遍历
三、后序遍历
总结

前言

我们之前学习过用递归解决二叉树的前序，中序，后序。
下面我们将用非递归，也就是遍历的方法对二叉树进行遍历

一、前序遍历

我们要解决这个问题最重要的就是用另一个角度看待这颗树

以下面这棵树为例子

在这里插入图片描述

我们把看成为：左路节点和左路节点的右子树

借助栈来实现

我们进行遍历，前序：根右子树左子树

🌟8,3,1入栈一直到nullptr，同时我们可以进行访问，这就是根

在这里插入图片描述

🌟取栈顶1元素，访问这个元素的右子树。由于右子树为nullptr,没有节点，继续遍历

在这里插入图片描述

🌟取栈顶元素3，遍历3的右子树

在这里插入图片描述

🌟3的右子树，根6入栈。访问左子树，4入栈.

在这里插入图片描述

🌟取栈顶元素4，访问4的右子树，右子树没有节点，继续遍历。

在这里插入图片描述

🌟下面也是同样的逻辑，遍历右子树，进行入栈。取栈顶元素进行，在遍历它的右子树

代码

    vector<int> preorderTraversal(TreeNode* root) {vector<int>v;stack<TreeNode*>st;TreeNode*cur=root;while(cur||st.size()!=0){//访问左路节点while(cur){v.push_back(cur->val);st.push(cur);cur=cur->left;}//取栈顶TreeNode*stop=st.top();st.pop();//左路节点的右子树cur=stop->right;}return v;}

注意：
结束条件：cur遍历到空节点，但是栈里面仍然有元素，我们继续进行遍历。
当cur为空，并且栈里面也为空，说明元素已经访问完了，结束

cur=stop->right;神之一手

二、中序遍历

中序遍历：左子树根右子树

中序遍历和前序遍历十分相似，唯一不同的就是访问根的时机不同。
上面讲的前序遍历，上来遇到跟我们就进行遍历。
我们在中序遍历的时候，需要先把左子树访问完了，再访问根。
我们在进行出栈的时候进行访问

vector<int> inorderTraversal(TreeNode* root) {vector<int>v;stack<TreeNode*>st;TreeNode*cur=root;while(cur||st.size()!=0){//左路节点while(cur){st.push(cur);cur=cur->left;}//取栈顶TreeNode*stop=st.top();//栈里面取到一个节点时，一定是它的左子树访问完了v.push_back(stop->val);st.pop();//左路节点1的右子树cur=stop->right;}return v;}

三、后序遍历

后序遍历和前序中序类似，也需要借助栈来实现，解决本题的关键就是什么时候可以对根节点进行访问
只有右子树访问完了，我们才可以访问这个节点，那我们怎末知道右子树是否已经访问过了呢？？

新增一个节点prev，记录前一个访问的节点

我们画图来看下

🌟遍历左路节点，左路节点入栈

在这里插入图片描述

🌟取栈顶元素1，这时不能pop,因为我们不能确定右子树是否已经被访问过了。

访问它的右子树，我们发现右子树为空，我们就可以对这个节点进行访问。这个节点访问完了，出栈。
prev=1

在这里插入图片描述

🌟继续取栈顶元素3，由于3的右子树不为nullptr,需要判断3这个节点的右子树的根节点是否等于prev.
如果等于prev,说明已经访问过了。如果不等于，我们就访问3这个节点的右子树。
我么判断而得，3->right!=prev.说明3的右子树还没有被访问。
访问3的右子树。

在这里插入图片描述

🌟继续取栈顶元素6，访问它的右子树。右子树为空，可以访问6这个节点,同时出栈。同时prev更新为6
在这里插入图片描述

🌟取栈顶元素3，由于3的右子树不为nullptr,需要判断3这个节点的右子树的根节点是否等于prev.
如果等于prev,说明已经访问过了。如果不等于，我们就访问3这个节点的右子树。
经过判断，3->right==prev.说明右子树已经访问完了。我们可以访问3这个节点了。

在这里插入图片描述

🌟后面也是同样的道理。

在这里插入图片描述

总结：🌟如果这个节点右子树为空，可以访问这个节点。
🌟或者这个节点的右子树等于prev(最近访问节点)，就说明这个节点的右子树已经访问过了，可以访问这个节点。
🌟否则，访问它的右子树

代码

    vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*>st;vector<int>v;TreeNode*cur=root;TreeNode*prev=nullptr;while(cur||!st.empty()){//左路节点入栈while(cur){st.push(cur);cur=cur->left;}//取栈顶元素TreeNode*stop=st.top();//这里不能pop//栈里面取到top说明top左子树已经访问完了//如果右子树为nullptr可以访问这个节点//右子树不为nullptr,且上一个访问节点就是这个节点的右子树的根，可以访问这个节点if(stop->right==nullptr||stop->right==prev){v.push_back(stop->val);st.pop();//更新上一个访问的最新节点prev=stop;}//否则子问题访问右子树else{cur=stop->right;}}return v;}