摘要：本文描述和實現了二叉樹的遍歷方法，包括：層次遍歷， 先序遍歷（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 <typename T>
static void CXBitTree<typename T>::PreOder( CXTreeNode<T> *node ) const
{
if( node == NULL )
return;
visit( root );
PreOder( node->GetLeft() );
PreOder( node->GetRight() );
}
有些人把PreOrder這樣“優化”：
template <typename T>
static void CXBitTree<typename T>::PreOder2( CXTreeNode<T> *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， 會產生問題，為了解決這個問題需要額外的監測。
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2013-10/91625p2.htm