资讯专栏INFORMATION COLUMN

二叉树的前中后序遍历(非递归实现)

tuantuan / 3428人阅读

摘要:文章目录二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树的前序遍历在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制。

二叉树的前序遍历


在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制。二叉树的前序遍历顺序是:根 → 左子树 → 右子树,我们可以先将二叉树的左路结点入栈,在入栈的同时便对其进行访问,此时就相当于完成了根和左子树的访问,当左路结点入栈完毕后再从栈顶依次取出结点,并用同样的方式访问其右子树即可。

具体步骤如下:

  1. 将左路结点入栈,入栈的同时访问左路结点。
  2. 取出栈顶结点top。
  3. 准备访问top结点的右子树。
struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode() : val(0), left(nullptr), right(nullptr) {}    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};class Solution {public:	//前序遍历	vector<int> preorderTraversal(TreeNode* root) {		stack<TreeNode*> st; //辅助栈		vector<int> ret; //用于存放前序遍历的结果		TreeNode* cur = root;		while (cur || !st.empty())		{			//1、将左路结点入栈,入栈的同时访问左路结点			while (cur)			{				st.push(cur);				ret.push_back(cur->val);				cur = cur->left;			}			//2、取出栈顶结点			TreeNode* top = st.top();			st.pop();			//3、准备访问其右子树			cur = top->right;		}		return ret; //返回前序遍历结果	}};

二叉树的中序遍历


二叉树的中序遍历顺序是:左子树 → 根 → 右子树,我们可以先将二叉树的左路结点入栈,当左路结点入栈完毕后,再从栈顶依次取出结点,在取出结点的同时便对其进行访问,此时就相当于先访问了左子树再访问了根,之后再用同样的方式访问取出结点的右子树即可。

具体步骤如下:

  1. 将左路结点入栈。
  2. 取出栈顶结点top并访问。
  3. 准备访问top结点的右子树。
struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode() : val(0), left(nullptr), right(nullptr) {}    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};class Solution {public:	//中序遍历	vector<int> inorderTraversal(TreeNode* root) {		stack<TreeNode*> st; //辅助栈		vector<int> ret; //用于存放中序遍历的结果		TreeNode* cur = root;		while (cur || !st.empty())		{			//1、将左路结点入栈			while (cur)			{				st.push(cur);				cur = cur->left;			}			//2、取出栈顶结点并访问			TreeNode* top = st.top();			st.pop();			ret.push_back(top->val);			//3、准备访问其右子树			cur = top->right;		}		return ret; //返回中序遍历结果	}};

二叉树的后序遍历


二叉树的后序遍历顺序是:左子树 → 右子树 → 根,我们可以先将二叉树的左路结点入栈,当左路结点入栈完毕后,再观察栈顶结点,若栈顶结点的右子树为空,或栈顶结点的右子树已经被访问过了,则栈顶结点可以出栈并访问,若栈顶结点的右子树还未被访问,则用同样的方式访问栈顶结点的右子树,直到其右子树被访问后再访问该结点,这时的访问顺序遵循了二叉树的后序遍历所要求的顺序。

具体步骤如下:

  1. 将左路结点入栈。
  2. 观察栈顶结点top。
  3. 若top结点的右子树为空,或top结点的右子树已经访问过了,则访问top结点。访问top结点后将其从栈中弹出,并更新上一次访问的结点为top。
  4. 若top结点的右子树还未被访问,则准备访问其右子树。
struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;    TreeNode() : val(0), left(nullptr), right(nullptr) {}    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};class Solution {public:	//后序遍历	vector<int> postorderTraversal(TreeNode* root) {		stack<TreeNode*> st; //辅助栈		vector<int> ret; //用于存放后序遍历的结果		TreeNode* cur = root;		TreeNode* prev = nullptr; //记录上一次访问的结点		while (cur || !st.empty())		{			//1、将左路结点入栈			while (cur)			{				st.push(cur);				cur = cur->left;			}			//2、取出栈顶结点			TreeNode* top = st.top();			//3、若取出结点的右子树为空,或右子树已经访问过了,则访问该结点			if (top->right == nullptr || top->right == prev)			{				//访问top结点后将其从栈中弹出				st.pop();				ret.push_back(top->val);				//更新上一次访问的结点为top				prev = top;			}			else //4、若取出结点的右子树还未被访问,则准备访问其右子树			{				cur = top->right;			}		}		return ret; //返回后序遍历结果	}};

注意: 看动图演示时请结合所给代码,动图是严格按照代码的逻辑制作的。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/124503.html

相关文章

  • 【数据结构初阶之叉树】:叉树相关的性质和经典的习题(用C语言实现,附图详解)

    摘要:当集合为空时,称该二叉树为空二叉树。也就是说,如果一个二叉树的层数为,且结点总数是,则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。 ...

    Martin91 评论0 收藏0
  • 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

    摘要:在数据结构领域对应树结构来说二叉树是最常用的一种树结构,二叉树具有一个唯一的根节点,也就是最上面的节点。二叉树每个节点最多有两个孩子,一个孩子都没有的节点通常称之为叶子节点,二叉树每个节点最多有一个父亲,根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

    ghnor 评论0 收藏0
  • 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

    摘要:在数据结构领域对应树结构来说二叉树是最常用的一种树结构,二叉树具有一个唯一的根节点,也就是最上面的节点。二叉树每个节点最多有两个孩子,一个孩子都没有的节点通常称之为叶子节点,二叉树每个节点最多有一个父亲,根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

    FuisonDesign 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<