二叉树遍历算法包含： 前序， 中序， 后序， 层次遍历 共四种算法。
先序遍历 DLR： 先访问根节点，然后访问左子树， 最后访问右子树
中序遍历LDR： 先访问左子树，然后根节点，最后访问右子树
后序遍历LRD： 先访问左子树，然后访问右子树，最后根节点
层次遍历： 从每层开始，至左向右逐层访问
先序、中序，后序都可以使用递归方式进行访问，非递归方式使用栈辅助， 层次遍历使用队列作为辅助结构
先序非递归遍历算法：
每次递归深入的时候，就是将左右孩子节点压栈的过程，在压栈之前，访问该节点；
每个节点只有在访问完右子树，或者右子树为空时，出栈，为了标志每个节点的右孩子节点是否压栈，可以使用一个标志位flag，将节点的右孩子节点压入栈中，需要改变flag，这样每次访问栈顶元素时，如果判断右子树已访问，直接出栈；
详细算法如下：
最开始根节点入栈
while(栈非空){
1. 获取栈顶元素cur；
2. 判断该节点的flag， 如果flag为true，说明该节点右子树已经访问，出栈， 否则 访问该节点cur；
3. 如果cur有左孩子节点，压入栈中，进入step 1；
否则，如果有右孩子节点（只有右子树），压入栈中，同时修改cur的标志位flag为true；如果cur为叶子节点，直接出栈，进入step1
}
void preOrder(BitNode *t){
Stack<BitNode*> s;
s.push(t);
BitNode *cur=NULL;
while( !s.empty() ){
cur= s.top();
if(cur.flag){
//右子树已经访问，出栈
s.pop();
}else{
visit(cur); //访问该节点
if(cur->lchild){
s.push(cur->lchild);//访问左子树
}else{
if(cur->rchild){//访问右子树
s.push(cur->rchild);
cur->flag= true;
}else{
//叶子节点
s.pop();
}
}
}
}
}
原文：https://www.cnblogs.com/energy1010/p/10627827.html