目录
- 二叉树的前序遍历
- 二叉树的中序遍历
- 二叉树的后序遍历
二叉树的前序遍历
在不使用递归的方式遍历二叉树时，我们可以使用一个栈模拟递归的机制。二叉树的前序遍历顺序是：根 → 左子树 → 右子树，我们可以先将二叉树的左路结点入栈，在入栈的同时便对其进行访问，此时就相当于完成了根和左子树的访问，当左路结点入栈完毕后再从栈顶依次取出结点，并用同样的方式访问其右子树即可。
具体步骤如下：
- 将左路结点入栈，入栈的同时访问左路结点。
- 取出栈顶结点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); //更新上一次访问的结点为top prev = top; } else //4、若取出结点的右子树还未被访问，则准备访问其右子树 { cur = top->right; } } return ret; //返回后序遍历结果 } };
注意： 看动图演示时请结合所给代码，动图是严格按照代码的逻辑制作的。
到此这篇关于c++ 非递归实现二叉树的前中后序遍历的文章就介绍到这了,更多相关二叉树前中后序遍历内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>！
需要了解更多c/c++开发分享C++ 非递归实现二叉树的前中后序遍历，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/992972.html