摘 要：二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，掌握二叉树的遍历对于二叉树的学习有重要作用。
关键词：二叉树；遍历
数据结构是指同一数据元素类中各数据元素之间存在的关系。它有四类基本结构：集合、线性结构、树形结构、图状结构。在计算机科学中，树是一种重要的非线性数据结构。树形结构是一种非线性的结构，能清晰的表达元素之间的分支和层次关系。客观世界中有许多事物的个体之间呈树形结构，如家族关系，部门机构设置等。所以树形结构是一种实用且常用的数据结构。
二叉树是一种特殊的树，特别适合于计算机处理。二叉树是个有限元素的集合，该集合或者为空，或者由一个称为根的元素及两个不相交、被分别称为左子树和右子树的二叉树组。在这里我们不讨论空树。
所谓遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是对树的一种最基本的运算也是一种重要操作，许多对树的操作都要基于遍历的。根据二叉树的结构特征，可以有三类搜索路径：先上后下的按层次遍历、先左（子树）后右（子树）的遍历、先右（子树）后左（子树）的遍历。设访问根结点记做D,遍历根的左子树记做L，遍历根的右子树记做R，则遍历二叉树有6种规则：DLR、DRL、LDR、LRD、RDL及层次遍历。若规定二叉树中必须先左后右(左右顺序不能颠倒)，则只有DLR、LDR、LRD及层次遍历四种遍历规则。所以二叉树的遍历分为：前序遍历、中序遍历、后序遍历和层次遍历。
（1）前序遍历（DLR）：按照“根（D）—左子树（L）—右子树（R）”的次序遍历二叉树。首先访问根，按前序遍历左子树，按前序遍历右子树。这是由上至下的推算过程。首先访问根，如左图所示，A作为根首先被访问，接着访问左结点B，而B是DE的根，根据DLR遍历要求，D作为B的左结点被接着访问，而D是HI的根，再访问过D后，H作为D的左结点被访问，接下去访问D的右结点I。因为HI之下没有结点了，回到被访问过的D处，E作为B的右结点被访问，J是E的左结点被访问。此时，A的左子树全部被访问，接下去访问右子树，C是A的右结点被访问，FG作为C的左右结点被访问。所以左图的前序遍历结果序列：ABDHIEJCFG.
前序遍历递归算法如下：
Template<class ElemType>
Void BinaryTree<ElemType>::PreOrder(BinTreeNode<ElemType>*r,void(*Visit)(ElemType &))
{ if(r!=NULL)
{
(*Visit)(r->data); //访问根结点
PreOrder(r->leftChild,Visit); //遍历左子树
PreOrder(r->rightChild,Visit); //遍历右子树
}
}
(2)中序遍历（LDR）：按照“左子树（L）—根（D）—右子树（R）”的次序。首先遍历左子树，访问根，按中序遍历右子树。我们首先都考虑ABC这个二叉树，B作为A的左结点应该先被访问，但是B又是DE的根，所以不能先被访问，那就看B的左结点D，但是D是HI的根，所以也不能被先访问。再看D的左右结点，H和I之下没有结点了，所以访问从这里开始了。这是由上至下的推算过程，但是遍历却是由下至上的。先考虑左子树，H作为D的左结点被最先访问，D为根，I是D的右结点被访问，推进一层，B作为D的根被访问，接下去应该访问B的右子树了，但是B的右结点E有个左结点J，根据规则左子树先根被访问，所以J先与E被访问。这时候根A的左子树被全部访问，根据规则A先于右子树被访问。接下去考虑A的右结点C，但是C是FG的根节点，所以F作为左结点先于C被访问，接下去才是C和C的右结点G。所以上图的中序遍历结果序列为：HDIBJEAFCG
中序遍历递归算法如下：
Template<class ElemType>
Void BinaryTree<ElemType>::InOrder(BinTreeNode<ElemType>*r,void(*Visit)(ElemType &))
{ if(r!=NULL)
{
PreOrder(r->leftChild,Visit); //遍历左子树
(*Visit)(r->data); //访问根结点
PreOrder(r->rightChild,Visit); //遍历右子树
}
}
（3）后序遍历（LRD）：按照“左子树（L）—右子树（R）—根（D）”的次序。考虑方法和中序遍历一样，首先考虑ABC这个树，按照规则B将先被访问，但是B是DE的根，同理可以知道D也不能先访问。考虑D的左右结点，HI之下没有结点了，所以HI被先访问，D作为根被访问。D被访问后应该访问B的右结点E，但是E还有个左结点J，所以J被先访问，然后是E和B。至此A的左子树被遍历，现在考虑右子树，C作为A的右结点应被最先考虑，但是C又是FG的根结点。根据规则先访问F和G，然后是根C。A作为BC的根结点被最后访问。得到后序遍历结果序列为：HIDJEBFGCA
后序遍历递归算法如下：
Template<class ElemType>
Void BinaryTree<ElemType>::PostOrder(BinTreeNode<ElemType>*r,void(*Visit)(ElemType &))
{ if(r!=NULL)
{
PreOrder(r->leftChild,Visit); //遍历左子树
PreOrder(r->rightChild,Visit); //遍历右子树
(*Visit)(r->data); //访问根结点
}
}
(4)层次遍历：这是二叉树遍历中最简单的遍历。按照层次访问，即按照从上层到下层，同层内从左到右的次序访问结点。上图的层次遍历结果序列：ABCDEFGHIJ
二叉树遍历看似简单，但是也容易出错。最主要一点是，在遍历过程中，不要把结点简单的单做子结点或者根结点，有些结点分饰几角，有不同的身份。有些子结点也是其他结点的根结点，要仔细考虑。当然，只要你细心，多方面考虑，牢记各种遍历规则，就能准确把握二叉树的遍历。
参考文献：
[1]主编 唐宁九 数据结构与算法分析 四川大学出版社
