二叉树的遍历VRL，RVL，RLV

摘要：本文描述和实现了二叉树的遍历方法，包括：层次遍历， 先序遍历（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， 会产生问题，为了解决这个问题需要额外的监测。

相关阅读：