对于一种数据结构而言，遍历是常见操作。二叉树是一种基本的数据结构，是一种每个节点的儿子数目都不多于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. 后序遍历

　　后序遍历与中序遍历，先序遍历的路径也完全一样。主要的不同点是后序遍历访问节点的顺序是先访问左儿子和右儿子，最后访问节点，即左儿子-右儿子-根节点。

　　递归实现思路与中序遍历和先序遍历相似，代码如下:

void PostOrderTraversal(BinTree BT)
{
? ? if (BT)
? ? {
? ? ? ? PostOrderTraversal(BT->Left);
? ? ? ? PostOrderTraversal(BT->Right);
? ? ? ? printf("%d\n", BT->Data);
? ? }
}

?　　后序遍历的非递归实现

　　思路一：

　　　　对于一个节点而言，要实现访问顺序为左儿子-右儿子-根节点，可以利用后进先出的栈，在节点不为空的前提下，依次将根节点，右儿子，左儿子压栈。故我们需要按照根节点-右儿子-左儿子的顺序遍历树，而我们已经知道先序遍历的顺序是根节点-左儿子-右儿子，故只需将先序遍历的左右调换并把访问方式打印改为压入另一个栈即可。最后一起打印栈中的元素。代码如下：

?

void PostOrderTraversal(BinTree BT)
{
? ? BinTree T = BT;
? ? Stack S1 = CreatStack(MAX_SIZE);? ? //创建并初始化堆栈S1
? ? Stack S2 = CreatStack(MAX_SIZE);? ? //创建并初始化堆栈S2?
? ? while(T || !IsEmpty(S1))
? ? {
? ? ? ? while(T)? ? ? ? //一直向右并将沿途节点访问（压入S2）后压入堆栈S1
? ? ? ? {
? ? ? ? ? ? Push(S2, T);
? ? ? ? ? ? Push(S1, T);
? ? ? ? ? ? T = T->Right;
? ? ? ? }
? ? ? ? if (!IsEmpty(S1))
? ? ? ? {
? ? ? ? ? ? T = Pop(S1);? ? //节点弹出堆栈
? ? ? ? ? ? T = T->Left;? //转向左子树
? ? ? ? }
? ? }
? ? while(!IsEmpty(S2))? ? //访问（打印）S2中元素
? ? {
? ? ? ? T = Pop(S2);
? ? ? ? printf("%d\n", T->Data);
? ? }? ? ? ? ?
}

　　　　思路一的优点是由于利用了先序遍历的思想，代码较简洁，思路较清晰。缺点是需要用一个栈来存储树的所有节点，空间占用较大。　　

　　思路二：

　　　　要访问一个节点的条件上一个访问的节点是右儿子。我们可以增加一个变量Prev来判断当前节点Curr的上一个节点与它的关系来执行相应的操作。
?　　　　若Prev为空(Curr节点是根节点)或者Prev是Curr的父节点，将Curr节点的左孩子和右孩子分别压入栈；
?　　　　若Prev是Curr的左儿子，则将Curr的右儿子压入栈；
?　　　　否则Prev是Curr的右儿子，访问Curr;

　　　　代码如下: