“树”是一种重要的数据结构，本文浅谈二叉树的遍历问题，采用C语言描述。
一、二叉树基础
1）定义：有且仅有一个根结点，除根节点外，每个结点只有一个父结点，最多含有两个子节点，子节点有左右之分。2）存储结构
二叉树的存储结构可以采用顺序存储，也可以采用链式存储，其中链式存储更加灵活。
在链式存储结构中，与线性链表类似，二叉树的每个结点采用结构体表示，结构体包含三个域：数据域、左指针、右指针。
二叉树在C语言中的定义如下：
struct BiTreeNode{ int c; struct BiTreeNode *left; struct BiTreeNode *right;};
二、二叉树的遍历
“遍历”是二叉树各种操作的基础。二叉树是一种非线性结构，其遍历不像线性链表那样容易，无法通过简单的循环实现。
二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。
二叉树遍历通常借用“栈”这种数据结构实现，有两种方式：递归方式及非递归方式。
在递归方式中，栈是由操作系统维护的，用户不必关心栈的细节操作，用户只需关心“访问顺序”即可。因而，采用递归方式实现二叉树的遍历比较容易理解，算法简单，容易实现。
递归方式实现二叉树遍历的C语言代码如下：
//先序遍历–递归int traverseBiTreePreOrder(BiTreeNode *ptree,int (*visit)(int)){if(ptree){if(visit(ptree->c))if(traverseBiTreePreOrder(ptree->left,visit))if(traverseBiTreePreOrder(ptree->right,visit))return 1; //正常返回return 0; //错误返回}else return 1; //正常返回}//中序遍历–递归int traverseBiTreeInOrder(BiTreeNode *ptree,int (*visit)(int)){if(ptree){if(traverseBiTreeInOrder(ptree->left,visit))if(visit(ptree->c))if(traverseBiTreeInOrder(ptree->right,visit))return 1;return 0;}else return 1;}//后序遍历–递归int traverseBiTreePostOrder(BiTreeNode *ptree,int (*visit)(int)){if(ptree){if(traverseBiTreePostOrder(ptree->left,visit))if(traverseBiTreePostOrder(ptree->right,visit))if(visit(ptree->c))return 1;return 0;}else return 1;}
以上代码中，visit为一函数指针，用于传递二叉树中对结点的操作方式，其原型为：int (*visit)(char)。
大家知道，函数在调用时，会自动进行栈的push，调用返回时，则会自动进行栈的pop。函数递归调用无非是对一个栈进行返回的push与pop，既然递归方式可以实现二叉树的遍历，那么借用“栈”采用非递归方式，也能实现遍历。但是，这时的栈操作（push、pop等）是由用户进行的，因而实现起来会复杂一些，而且也不容易理解，但有助于我们对树结构的遍历有一个深刻、清晰的理解。
在讨论非递归遍历之前，我们先定义栈及各种需要用到的栈操作：
//栈的定义，栈的数据是“树结点的指针”struct Stack{BiTreeNode **top;BiTreeNode **base;int size;};#define STACK_INIT_SIZE 100#define STACK_INC_SIZE 10//初始化空栈，预分配存储空间Stack* initStack(){Stack *qs=NULL;qs=(Stack *)malloc(sizeof(Stack));qs->base=(BiTreeNode **)calloc(STACK_INIT_SIZE,sizeof(BiTreeNode *));qs->top=qs->base;qs->size=STACK_INIT_SIZE;return qs;}//取栈顶数据BiTreeNode* getTop(Stack *qs){BiTreeNode *ptree=NULL;if(qs->top==qs->base)return NULL;ptree=*(qs->top-1);return ptree;}//入栈操作int push(Stack *qs,BiTreeNode *ptree){if(qs->top-qs->base>=qs->size){qs->base=(BiTreeNode **)realloc(qs->base,(qs->size+STACK_INC_SIZE)*sizeof(BiTreeNode *));qs->top=qs->base+qs->size;qs->size+=STACK_INC_SIZE;}*qs->top++=ptree;return 1;}//出栈操作BiTreeNode* pop(Stack *qs){if(qs->top==qs->base)return NULL;return *–qs->top;}//判断栈是否为空int isEmpty(Stack *qs){return qs->top==qs->base;}
首先考虑非递归先序遍历（NLR）。在遍历某一个二叉（子）树时，以一当前指针记录当前要处理的二叉（左子）树，以一个栈保存当前树之后处理的右子树。首先访问当前树的根结点数据，接下来应该依次遍历其左子树和右子树，然而程序的控制流只能处理其一，所以考虑将右子树的根保存在栈里面，，当前指针则指向需先处理的左子树，为下次循环做准备；若当前指针指向的树为空，说明当前树为空树，不需要做任何处理，直接弹出栈顶的子树，为下次循环做准备。相应的C语言代码如下：
//先序遍历–非递归int traverseBiTreePreOrder2(BiTreeNode *ptree,int (*visit)(int)){Stack *qs=NULL;BiTreeNode *pt=NULL;qs=initStack();pt=ptree;while(pt || !isEmpty(qs)){if(pt){if(!visit(pt->c)) return 0; //错误返回push(qs,pt->right);pt=pt->left;}else pt=pop(qs);}return 1; //正常返回}
相对于非递归先序遍历，非递归的中序/后序遍历稍复杂一点。
最大的成功在于最大的付出。
