二叉树的遍历VRL，RVL，RLV

二叉树的遍历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 <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， 会产生问题，为了解决这个问题需要额外的监测。

更多详情见请继续阅读下一页的精彩内容：

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针