递归 迭代
中序遍历 О（n） О（n）
Postorder О（n）  

中序遍历

递归 

if ( !x ) 
    return; //处理递归基
traverse( x->lChild, visit ); //遍历左子树
visit( x->data); //访问根节点
traverse( x->rChild, visit ); //遍历右子树

迭代 

  1. 控制权转交给左孩子；图中的被发现状态和visited状态 
  2. 访问左侧链节点，遍历右子树； 左式堆
  3. 逆序性：最先被访问的是最后被发现的，自下而上；采用后进先出的结构：栈。
  4. 分摊分析

后序遍历

递归

if ( !x )
    return;
traverse( x->lChild, visit );
traverse( x->rChild, visit );
visit( x->data );

 

层次遍历

迭代 

while ( ! Q.empty() ){
    BinNodePosi(T) x = Q.dequeue();
    visit( x->data );
    if ( HasLChild( * x ) )
        Q.enquene( x->lc );
    if ( HasLChild( * x ) )
        Q.enquene( x->rc );
}