C++非递归如何实现二叉树的前中后序遍历
C++非递归如何实现二叉树的前中后序遍历
小编给大家分享一下C++非递归如何实现二叉树的前中后序遍历，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
二叉树的前序遍历
在不使用递归的方式遍历二叉树时，我们可以使用一个栈模拟递归的机制。二叉树的前序遍历顺序是：根 → 左子树 → 右子树，我们可以先将二叉树的左路结点入栈，在入栈的同时便对其进行访问，此时就相当于完成了根和左子树的访问，当左路结点入栈完毕后再从栈顶依次取出结点，并用同样的方式访问其右子树即可。
具体步骤如下：
将左路结点入栈，入栈的同时访问左路结点。
取出栈顶结点top。
准备访问top结点的右子树。
structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode():val(0),left(nullptr),right(nullptr){}TreeNode(intx):val(x),left(nullptr),right(nullptr){}TreeNode(intx,TreeNode*left,TreeNode*right):val(x),left(left),right(right){}};classSolution{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;}returnret;//返回前序遍历结果}};
二叉树的中序遍历
二叉树的中序遍历顺序是：左子树 → 根 → 右子树，我们可以先将二叉树的左路结点入栈，当左路结点入栈完毕后，再从栈顶依次取出结点，在取出结点的同时便对其进行访问，此时就相当于先访问了左子树再访问了根，之后再用同样的方式访问取出结点的右子树即可。
具体步骤如下：
将左路结点入栈。
取出栈顶结点top并访问。
准备访问top结点的右子树。
structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode():val(0),left(nullptr),right(nullptr){}TreeNode(intx):val(x),left(nullptr),right(nullptr){}TreeNode(intx,TreeNode*left,TreeNode*right):val(x),left(left),right(right){}};classSolution{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;}returnret;//返回中序遍历结果}};
二叉树的后序遍历
二叉树的后序遍历顺序是：左子树 → 右子树 → 根，我们可以先将二叉树的左路结点入栈，当左路结点入栈完毕后，再观察栈顶结点，若栈顶结点的右子树为空，或栈顶结点的右子树已经被访问过了，则栈顶结点可以出栈并访问，若栈顶结点的右子树还未被访问，则用同样的方式访问栈顶结点的右子树，直到其右子树被访问后再访问该结点，这时的访问顺序遵循了二叉树的后序遍历所要求的顺序。
具体步骤如下：
将左路结点入栈。
观察栈顶结点top。
若top结点的右子树为空，或top结点的右子树已经访问过了，则访问top结点。访问top结点后将其从栈中弹出，并更新上一次访问的结点为top。
若top结点的右子树还未被访问，则准备访问其右子树。
structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode():val(0),left(nullptr),right(nullptr){}TreeNode(intx):val(x),left(nullptr),right(nullptr){}TreeNode(intx,TreeNode*left,TreeNode*right):val(x),left(left),right(right){}};classSolution{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;}}returnret;//返回后序遍历结果}};
注意： 看动图演示时请结合所给代码，动图是严格按照代码的逻辑制作的。
以上是“C++非递归如何实现二叉树的前中后序遍历”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注恰卡编程网行业资讯频道！
