这篇“C++二叉树的前序中序后序非递归怎么实现”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C++二叉树的前序中序后序非递归怎么实现”文章吧。
前序遍历的顺序是根、左、右。任何一颗树都可以认为分为左路节点，左路节点的右子树。先访问左路节点，再来访问左路节点的右子树。把访问左路节点的右子树看成一个子问题，就可以完整递归访问了。
先定义栈st存放节点、v存放值，TreeNode* cur，cur初始化为root。
当cur不为空或者栈不为空的时候(一开始栈是空的，cur不为空)，循环继续：先把左路节点存放进栈中，同时把值存入v中，一直循环，直到此时的左路节点为空，访问结束。在弹出栈顶元素top，把top->right赋值给我们的cur，就可以转化成子问题去访问左路节点的右子树了。
栈st不为空说明此时还有左路节点的右子树还没访问，cur不为空说明此时还有树要去访问。当两个同时为空时，循环结束，最终得到前序遍历。
一个节点出栈说明这个节点及其左子树已经访问完了，因为我们是先把左路节点存入栈中，此时还剩右子树没有访问。
计算
安全
数据库
网络和加速
企业服务
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> st;
TreeNode*cur = root;
while(!st.empty()||cur)
{
//左路节点
while(cur)
{
st.push(cur);
v.push_back(cur->val);
cur = cur->left;
}
//左路节点右子树
TreeNode* top = st.top();
st.pop();
cur = top->right;//转化成子问题访问右子树
}
return v;
}
};
中序遍历是左、根、右。左子树访问完之后才能去访问根。左路节点一直走直到左子树访问完，入栈的过程中不去进行访问（存放数值到v中），当左路节点出栈之后，也就是从栈中弹出进行访问。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> st;
TreeNode*cur = root;
while(cur||!st.empty())
{
while(cur)
{
//不访问
st.push(cur);
cur = cur->left;
}
TreeNode*top = st.top();
//进行访问
v.push_back(top->val);
st.pop();
cur = top->right;
}
return v;
}
};
后序的遍历顺序是左、右、根。与前面的相比，比较麻烦，我们需要把左子树和右子树访问完再去访问根。我们定义一个栈，在栈里面取到一个节点时：右子树是否访问过，如果没有访问，迭代子问题访问，如果访问过了，则访问这个根节点，pop出栈
如果top的右子树为空或者右子树已经访问过了（上一个访问节点是右子树的根），那么说明右子树不用访问或者访问过了，可以访问根top;当右子树不为空，且没有访问过，则迭代子问题访问。
通过prev来判断上一次访问的节点：如果prev等于top->right时，表示栈顶节点的右子树已经访问过了，可以弹出栈顶节点并访问它。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> st;
TreeNode*cur = root;
TreeNode*prev = nullptr;
while(cur||!st.empty())
{
while(cur)
{
st.push(cur);
cur = cur->left;
}
TreeNode*top = st.top();
//top的右子树为空，或者右子树已经访问过了（上一个访问节点时右子树的根）那么说明右子树不用访问或者访问过了，可以访问根top
//右子树不为空，且没有访问， 则迭代子问题访问
if(top->right==nullptr||top->right==prev)
{
st.pop();
v.push_back(top->val);
prev = top;
}
else
{
cur = top->right;
}
}
return v;
}
};
以上就是关于“C++二叉树的前序中序后序非递归怎么实现”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注亿速云行业资讯频道。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://blog.csdn.net/weixin_60478154/article/details/128945483
