之前一直觉得二叉树使用递归来实现就感觉有点绕，今天才发现二叉树使用非递归来实现更加的绕，但是考虑到我们得使用非递归来提高二叉树的遍历效率，使用非递归是一种比较好的方法。
成都创新互联公司专注于达日企业网站建设,成都响应式网站建设,成都商城网站开发。达日网站建设公司,为达日等地区提供建站服务。全流程按需求定制设计，专业设计，全程项目跟踪，成都创新互联公司专业和态度为您提供的服务三种递归遍历对遍历的描述，思路非常简洁，最重要的是三种方法完全统一，大大减轻了我们理解的负担。现在非递归使用栈来实现，利用了栈的先进后出的特点，可以解决。
二叉树的递归实现之前已经实现过了，我们直接实现非递归。并且都使用栈实现
（一）前序遍历
对于前序遍历，我们要解决的问题是何时压入左右子树？先压左子树还是右子树？
答案是显而易见的，因为是前序遍历，所以在压栈根节点，出栈后再压入左右子树。并且是先压右子树。然后出栈左子树，最后出栈右子树。直到栈为空。
void PrevOrder_Nrec()//前序非递归实现
{
stack s;
if (_root)
s.push(_root);
while (!s.empty())
{
Node* top = s.top();
cout << top->_data << " ";
s.pop();
if (top->_right)
{
s.push(top->_right);
}
if (top->_left)
{
s.push(top->_left);
}
}
} （二）中序遍历
中序遍历是一直压栈，把最左节点都压入栈内，出栈最左子树的左节点，然后出栈根节点，然后才出栈右节点。当栈为空时结束。
void MideOrder_Nrec()//中序遍历非递归实现
{
stack s;
Node* cur = _root;
while (!s.empty()||cur)
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
if (!s.empty())
{
Node* tmp = s.top();
s.pop();
cout << tmp->_data << " ";
cur = tmp->_right;
}
}
} （三）后序遍历
后序遍历比较难办，因为我们要找到一棵树，首先遍历到的都是树的根节点，在后序遍历中，得先把左右子树都遍历以后才能输出根节点。左子树比较好办，我们可以把左节点看作是一颗子树的根节点，所以我们必须要创建一个指针来标识是否我们已经访问过右子树。我们把这个指针名为prev，表示上一个访问的节点，让他与根节点的右节点比如果相等说明已经访问过了，可以出栈根。否则访问右节点。
void RearOrder_Nrec()//后序遍历非递归实现
{
stack s;
Node* cur = _root;
Node* prev = NULL;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
if (!s.empty())
{
Node* top = s.top();
if (top->_right == prev)//判断是否已经访问了根节点的右子树
{
s.pop();
cout << top->_data << " ";
prev = top;
}
else
{
cur = top->_right;//如果没有就去访问右子树
prev = top->_right;
}
}
}
} 如果一棵树深度很大，那么非递归比递归的效率高很多，但是递归比非递归好理解，怎样取舍看情况吧。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
