小编给大家分享一下c++非递归如何实现二叉树的前中后序遍历,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!二叉树的前序遍历在不使用递归的方式遍历二叉树时,我们可以使
小编给大家分享一下c++非递归如何实现二叉树的前中后序遍历,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制。二叉树的前序遍历顺序是:根 → 左子树 → 右子树,我们可以先将二叉树的左路结点入栈,在入栈的同时便对其进行访问,此时就相当于完成了根和左子树的访问,当左路结点入栈完毕后再从栈顶依次取出结点,并用同样的方式访问其右子树即可。
具体步骤如下:
将左路结点入栈,入栈的同时访问左路结点。
取出栈顶结点top。
准备访问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; //返回前序遍历结果}};
二叉树的中序遍历顺序是:左子树 → 根 → 右子树,我们可以先将二叉树的左路结点入栈,当左路结点入栈完毕后,再从栈顶依次取出结点,在取出结点的同时便对其进行访问,此时就相当于先访问了左子树再访问了根,之后再用同样的方式访问取出结点的右子树即可。
具体步骤如下:
将左路结点入栈。
取出栈顶结点top并访问。
准备访问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; //返回中序遍历结果}};
二叉树的后序遍历顺序是:左子树 → 右子树 → 根,我们可以先将二叉树的左路结点入栈,当左路结点入栈完毕后,再观察栈顶结点,若栈顶结点的右子树为空,或栈顶结点的右子树已经被访问过了,则栈顶结点可以出栈并访问,若栈顶结点的右子树还未被访问,则用同样的方式访问栈顶结点的右子树,直到其右子树被访问后再访问该结点,这时的访问顺序遵循了二叉树的后序遍历所要求的顺序。
具体步骤如下:
将左路结点入栈。
观察栈顶结点top。
若top结点的右子树为空,或top结点的右子树已经访问过了,则访问top结点。访问top结点后将其从栈中弹出,并更新上一次访问的结点为top。
若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);//更新上一次访问的结点为topprev = top;}else //4、若取出结点的右子树还未被访问,则准备访问其右子树{cur = top->right;}}return ret; //返回后序遍历结果}};
注意: 看动图演示时请结合所给代码,动图是严格按照代码的逻辑制作的。
以上是“C++非递归如何实现二叉树的前中后序遍历”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注编程网其他教程频道!
--结束END--
本文标题: C++非递归如何实现二叉树的前中后序遍历
本文链接: https://www.lsjlt.com/news/300359.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0