对于一种数据结构而言，遍历是常见操作。二叉树是一种基本的数据结构，是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下：
typedef struct TreeNode *PtrToNode;
typedef struct TreeNode *BinTree;
struct TreeNode
{
int Data; //为简单起见，不妨假设树节点的元素为int型
BinTree Left;
BinTree Right;
};
二叉树的遍历主要有先序遍历，中序遍历，后序遍历，层序遍历四种方式，下面一一介绍。
1. 先序遍历
在先序遍历中，对节点的访问工作是在它的左右儿子被访问之前进行的。换言之，先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义，所以树的常见操作用递归实现常常是方便清晰的。递归实现的代码如下：
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT->Data); //对节点做些访问比如打印
PreOrderTraversal(BT->Left); //访问左儿子
PreOrderTraversal(BT->Right); //访问右儿子
}
}
由递归代码可以看出，该递归为尾递归（尾递归即递归形式在函数末尾或者说在函数即将返回前）。尾递归的递归调用需要用栈存储调用的信息，当数据规模较大时容易越出栈空间。虽然现在大部分的编译器能够自动去除尾递归，但是即使如此，我们不妨自己去除。非递归先序遍历算法基本思路：使用堆栈
a. 遇到一个节点，访问它，然后把它压栈，并去遍历它的左子树；
b. 当左子树遍历结束后，从栈顶弹出该节点并将其指向右儿子，继续a步骤；
c. 当所有节点访问完即最后访问的树节点为空且栈空时，停止。
实现代码如下：
void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MAX_SIZE); //创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) //一直向左并将沿途节点访问（打印）后压入堆栈
{
printf("%d\n", T->Data);
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S); //节点弹出堆栈
T = T->Right; //转向右子树
}
}
}
2. 中序遍历
中序遍历的遍历路径与先序遍历完全一样。其实现的思路也与先序遍历非常相似。其主要的不同点是访问节点顺序不同：中序遍历是访问完所有左儿子后再访问根节点，最后访问右儿子，即为左儿子-根节点-右儿子。
递归实现的代码如下:
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d\n", BT->Data);
InOrderTraversal(BT->Right);
}
}
非递归实现代码如下:
void InOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MaxSize); //创建并初始化堆栈S
while(T || !IsEmpty(S))
{
while(T) //一直向左并将沿途节点压入堆栈
{
Push(S,T);
T = T->Left;
}
if(!IsEmpty(S))
{
T = Pop(S); //节点弹出堆栈
printf("%d\n", T->Data); //（访问） 打印结点
T = T->Right; //转向右子树
}
}
}
3. 后序遍历
后序遍历与中序遍历，先序遍历的路径也完全一样。主要的不同点是后序遍历访问节点的顺序是先访问左儿子和右儿子，最后访问节点，即左儿子-右儿子-根节点。
递归实现思路与中序遍历和先序遍历相似，代码如下: