二叉树的构建使用的是链表的形式，每个节点中既包含了根节点的元素，也包含了指向左右孩子的指针，实际可以看成一个二维的线性结构。
二叉树的遍历实质就是就二维变为一维的过程。
前序遍历的递归思想是：
首先访问根节点
然后以左子树为根节点递归调用遍历函数，（这样就沿着树的最左边的分支遍历到最左边的叶子节点）
接着以右子树为根节点递归调用遍历函数，（这样就逐层回到调用的根节点，然后递归根节点的右节点）
中序与后序的递归遍历思想一样，只是访问根节点的先后顺序不一样
以中序遍历为例实现递归遍历
templte <class T>
void preOrder(binarytTreeNode<T> *t)
{
if(t!=NULL)
{
visit(t); //访问根节点
preOrder(t->leftChild); //前序遍历左子树
preOrder(t->rightChild); //前序遍历右子树
}
}
非递归实现二叉树的思想是使用堆栈来实现的
实际上，无论是前序、中序还是后序遍历，其在树中所走的路劲的顺序都是一样的。都是先指到根节点，然后指到左子树最后指到右子树，只是不同的遍历，在访问左右子树和根节点的顺序不同而已。
那么就可以使用堆栈来实现非递归的遍历
首先当指到根节点时，将其压入堆栈，然后指向其左子树，如果左子树非空，也将其入栈，这样就到达最左边的叶子节点
然后从栈中依次取出每个“根节点”
最后再指向这些“根节点”的右子树
以上根节点打双引号是因为实际上是将左右节点在某个位子看成了根节点，实际上在遍历构成中，不同的根节点也正是这些左右节点，利用堆栈就是使各左右节点在合适的位置成为根节点。
对于不同的遍历，只是访问访问“根节点”的顺序不同，便可得到不同遍历的非递归遍历方法如下：
前序遍历：
当遇到一个节点就访问它并将其压入栈中，然后遍历其左子树
当左子树遍历结束后，从栈顶弹出这个节点
然后指向其右子树再按前序遍历
其实现如下：
void preOrder(binaryTreeNode<T> t)
{
binaryTreeNode tmp=t;
Stack S=CreatStack(size); //伪代码，创建一个长度为size的栈
while(!T.empty || !empty(S)) //只要树和栈非空
{
while(!T.empty) //一直向左并将沿途的节点压入栈中
{
visit(T); //访问T
push(S,T); //将T压入栈
T=T->leftchild;
}
if(empty(S))
{
T=pop(S); //将节点弹出堆栈
T=T->rightchild; //转向右子树
}
}
}
中序遍历：
当遇到一个节点就将其压入栈中，然后遍历其左子树
当左子树遍历结束后，从栈顶弹出这个节点并访问它
然后指向其右子树再按中序遍历
void inOrder(binaryTreeNode<T> t)
{
binaryTreeNode tmp=t;
Stack S=CreatStack(size); //伪代码，创建一个长度为size的栈
while(!T.empty || !empty(S)) //只要树和栈非空
{
while(!T.empty) //一直向左并将沿途的节点压入栈中
{
push(S,T); //将T压入栈
T=T->leftchild;
}
if(empty(S))
{
T=pop(S); //将节点弹出堆栈
visit(T); //访问T
T=T->rightchild; //转向右子树
}
}
}
后序遍历：
后序遍历的非递归实现是三种遍历方式中最难的一种。在前两种遍历中，左子树都是在根节点之前可以遍历到，而右子树都是在根节点后才遍历。而在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。
一种思路如下：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了（通过设置被访问标记来判断），则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
void inOrder(binaryTreeNode<T> t)
{
binaryTreeNode tmp=t;
Stack S=CreatStack(size); //伪代码，创建一个长度为size的栈
while(!T.empty || !empty(S)) //只要树和栈非空
{
while(!T ) //T不是空节点
{ //一直向左并将沿途的节点压入栈中
push(S,T); //将T压入栈
if(!T->rightchild.isvisited()&& T->rightchild) //T存在未被访问过的右节点
{
T=T->rightchild;
push(S,T); //将T的右节点压入栈
T.isvisited(); //将T的右节点压设为被访问过
}
if(!T->leftchild.isvisited()&& T->lefttchild) //T存在未被访问过的左节点
{
T=T->rightchild;
}
else
T=NULL;
}
if(empty(S))
{
T=pop(S); //将节点弹出堆栈
visit(T); //访问T
//T=T->rightchild; //转向右子树
}
}
}
层次遍历：
层次遍历是逐层访问，每一层从左自右逐个访问，这种实现方法可以使用队列来实现。
从根节点开始入队
然后从队首取出元素，并访问该元素所指节点
然后判断该节点的左右孩子是否为空，并按先后顺序将非空节点入队
void levelOrder( binaryTreeNode<T> *t)
{
Queue Q; //创建队列
binaryTreeNode<T> tree;
if(!t)
return; //如果树为空，则直接返回
Q=Createqueue(size); //伪代码，创建长度为size的队列
AddQ(Q,t); //将tree入队
while(!Q.empty) //队列非空时
{
tree=Q.top; //队首元素出队
Q.pop(); //删除队首
/*将非空子树入队*/
if(tree.leftchild) AddQ(Q,tree.leftchild);
if(tree.leftchild) AddQ(Q,tree.leftchild);
}
}