13518219792
二叉树的遍历可以使用递归的方式实现，并且代码非常简单。而递归实际就是函数反复的调用本身，在栈上反复压栈。所以我们可以用栈来模拟实现递归。
1.前序遍历
（1）栈是后进先出的特点，所以无条件的把栈的根节点入栈，在把栈顶元素输出之后依次把右孩子，左孩子压入栈中。
代码如下：
void _PrevOrder(Node * root)
{
stack s;
if (root == NULL)
{
return;
}
s.push(root);//将第一个元素入栈
while (!s.empty())//当栈不为空时
{
root = s.top();
cout << root->_data << "->";//打印节点
s.pop();
//栈的特点，后进先出，所以，先压右子树
if (root->_right)//遍历右子树
{
s.push(root->_right);
}
if (root->_left)//遍历左子树
{
s.push(root->_left);
}
}
} 2.中序遍历
（1）一直入栈，一直到二叉树的最左边最下边的节点。
（2）按照中序遍历的特点：左子树->根节点->右子树，输出栈顶的元素，并且弹出，必须保留该节点的指针。
（3）此时，该判断此节点的右子树：
a.右子树为NULL，返回到栈顶；
b.右子树不为NULL，把该节点当根节点，重复（1）（2）（3）......
代码如下：
void _InOrder(Node * root)
{
if (root == NULL)
{
return;
}
Node * cur = root;
stack s;
while (cur || !s.empty())
{
while (cur)//当没有左子树时，停止入栈
{
s.push(cur);
cur = cur->_left;
}
Node * top = s.top();//保留栈顶指针，判断是否有右子树
cout << top->_data << "->";
s.pop();
if (top->_right == NULL)//没有右子树时，不需要压栈
{
cur = NULL;
}
else//当存在右子树时，把右子树的根节点压入栈中，循环去判断该节点的左子树是否存在
{
cur = top->_right;
}
}
} 3.后序遍历
（1）一直入栈，一直到二叉树的最左边最下边的节点。
（2）按照后序遍历的特点：左子树->右子树->根节点，输出栈顶的元素，并且弹出，必须保留该节点的指针。
（3）此时，该判断此节点的右子树，如果存在右子树，把该节点当作根节点，重复（1）（2）（3）
代码如下：
void _PostOrder(Node * root)
{
if (root == NULL)
{
return;
}
Node * cur = root;
Node * prev = NULL;
stack s;
while (cur || !s.empty())
{
while (cur)//当没有左子树时，停止入栈
{
s.push(cur);
cur = cur->_left;
}
Node * top = s.top();//保留栈顶指针，判断它的右子树是否为空或者已经出栈
if (top->_right == NULL || top->_right == prev)
{
cout << top->_data << "->";
s.pop();
prev = top;//保留出栈元素的指针
cur = NULL;
}
else//当存在右子树时，把右子树的根节点压入栈中，循环去判断该节点的左子树是否存在
{
cur = top->_right;
}
}
} 另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
