摘要：本文描述和实现了二叉树的遍历方法，包括：层次遍历， 先序遍历（VRL），中序遍历（RVL），后序遍历（RLV）。

1. 遍历（Traversals）

（1）层次遍历

（2）V：root ； R： right child ；  L：left child

先序遍历（VRL）：A B DHIEJ CFG

中序遍历（RVL）：HDIBJE A FCG

后序遍历（RLV）：HIDJEB FGC A

2. 先序遍历（VRL）

 

template 
    
     static void CXBitTree
     
      ::PreOder( CXTreeNode
      
        *node ) const{    if( node == NULL )        return;    visit( root );    PreOder( node->GetLeft() );    PreOder( node->GetRight() );}
      
     
    

有些人把PreOrder这样“优化”：

 

 

template 
    
     static void CXBitTree
     
      ::PreOder2( CXTreeNode
      
        *node ) const{    visit( root );    if(  node->GetLeft() )        PreOder( node->GetLeft() );    if( node->GetRight() )        PreOder( node->GetRight() );}
      
     
    

但是这样真的优化了吗？

 

PreOrder2比PreOrder有2点劣势：

（1）对于每一个node的访问需要调用2次（检查非空1次，访问1次），对于复杂的Node结构来说，这显然是很费时。

（2）如果最初传递给PreOrder2的node == NULL， 会产生问题，为了解决这个问题需要额外的监测。

3.  中序遍历（RVL）

 

template 
    
     static void CXBitTree
     
      ::InOder( CXTreeNode
      
        *node ) const{    if( node == NULL )        return;        PreOder( node->GetLeft() );    visit( root );    PreOder( node->GetRight() );}
      
     
    

 

 

4. 后序遍历（RLV）

 

template 
    
     static void CXBitTree
     
      ::PostOder( CXTreeNode
      
        *node ) const{    if( node == NULL )        return;    PreOder( node->GetLeft() );    PreOder( node->GetRight() );    visit( root );}
      
     
    

 

 

5. 层次遍历

 

template 
    
     static void CXBitTree
     
      ::LevelOder( CXTreeNode
      
        *node ) const{    if( node == NULL )        return;    std::queue
       
        
          *> queue_nodes;    CXTreeNode
         
           * pnode; queue_nodes.push( node ); while ( !queue_nodes.empty() ) { pnode = queue_nodes.front(); queue_nodes.pop(); visit( pnode ); if ( pnode->GetLeft() ) { queue_nodes.push( pnode->GetLeft() ); } if( pnode->GetRight() ) { queue_nodes.push( pnode->GetRight() ); } }//while}
         
        
       
      
     
    

 

 

6. 算法分析

设：每个节点的访问时间复杂度为O( 1 ),

那么：这4中算法的时间复杂度为O(n).