遍历一个数据结构，也即逐一地处理（可读可写）其中所有元素。

• 二叉树的遍历：一棵二叉树可以看作一个状态空间：根节点（入口）对应状态空间的初始状态，父子结点连接对应状态的邻接关系。以这种观点，一次二叉树的遍历就是一次覆盖整个状态空间的搜索。

1. 深度优先与广度优先

按深度优先的方式遍历一棵二叉树，需要做三件事（可能需要处理其中的数据）：

• 遍历左子树（L）；
• 遍历根节点（D）；
• 遍历右子树（R）；

全排列的话，A33=6，但这里一般假定先处理左子树，后处理右子树，这样，根据根节点遍历的先后顺序，仅可得到三种遍历方式（先中后说的都是根节点的遍历相对顺序）。

由于二叉树的子树也是二叉树，将一种具体的遍历顺序（先中后）方式继续运用到子树的遍历中，就形成了一种二叉树的统一方法。

宽度优先（层次遍历）是按路径长度（自己到自己，路径长度为 0）由近到远地访问节点。对二叉树做这种遍历，也就是按二叉树的层次逐层访问树中各结点。与状态空间搜索的情况一样，这种遍历不能写成一个递归的过程。

在宽度优先遍历中规定了逐层访问，并未规定同一层结点的访问顺序。但从算法的角度，必须规定一个顺序，常见的是在每一层里都从左到右逐个访问（从右到左，也是需要使用一个队列，只不过进队的顺序是从右子节点，左子节点）。实现这一算法需要一个队列作为缓存。

2. 二叉树的遍历：递归实现

• 先序：
  template<typename T, typename VST>
  void travPreorder_R(BinNode<T>* x, VST& visit){
  if (!x) return;
  visit(x->data);
  if (HasLChild(x))
  travPreorder_R(x->lChid, visit);
  if (HasRChild(x))
  travPreorder_R(x->rChild, visit);
  }

• 中序：

  template
        
         void travInorder_R(BinNode
         
          * x, VST& visit){    if (!x) return;    if (HasLChild(x))        travPreorder_R(x->lChid, visit);    visit(x->data);    if (HasRChild(x))        travPreorder_R(x->rChild, visit);}
         
        

• 后序：

  template
        
         void travInorder_R(BinNode
         
          * x, VST& visit){    if (!x) return;    if (HasLChild(x))        travPreorder_R(x->lChid, visit);    if (HasRChild(x))        travPreorder_R(x->rChild, visit);    visit(x->data);}
         
        

3. 二叉树的遍历 —— 迭代实现

• 先序，思路，先一路向左（同时把右子树保存在栈里），再把栈中的右子树出栈，

  // 辅助函数template 
        
         void visitAlongLeftBranch(BinNode
         
          * x, VST& visit, Stack
          
           
            *> S){        while (x){            visit(x->data);            S.push(x->rChild);            x = x->lChild;        }}template 
            
             void travPreorder_I1(BinNode
             
              * x, VST& visit){ Stack
              
               
                *> S; while (true){ visitAlongLeftBranch(x, visit, S); if (S.empty()) break; x = S.pop(); }}
               
              
             
            
           
          
         
        

• 后序，思考的起点依然是，首先访问的结点是哪一个？（HLVFL，Highest Leaf Visual From Left）

  template 
        
         void gotoHLVFL(Stack
         
          
           *> S){    while (BinNode
           
            * x = S.top()){     // 循环退出时，一定是 x 为 NULL 了，也即 S.top() 栈顶元素为空        if (HasLChild(x)){            if (HasRChild(x)){                S.push(x->rChild);            }            S.push(x->lChild);        } else {            S.push(x->rChild);        }    }    S.pop();         // 弹出栈顶的空元素；}template 
            
             void travPostorder_I(BinNode
             
              * x, VST& visit){ Stack
              
               
                *> S; if (x) S.push(x); while (!S.empty()){ if (S.top() != x.parent){ gotoHLVFL(S); } x = S.pop(); visit(x->data); }}