二叉树的遍历可以使用递归的方式实现，并且代码非常简单。而递归实际就是函数反复的调用本身，在栈上反复压栈。所以我们可以用栈来模拟实现递归。

1.前序遍历

（1）栈是后进先出的特点，所以无条件的把栈的根节点入栈，在把栈顶元素输出之后依次把右孩子，左孩子压入栈中。


代码如下：

void_PrevOrder(Node*root){stack<Node*>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<Node*>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<Node*>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;}}}