首页 / 操作系统 / Linux / 二叉树的遍历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 A2. 先序遍历（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相关阅读：二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm