概念:就是从二叉树的根结点出发,按照一定得次序依次访问二叉树中的所有结点,是的每个结点被访问到的次数都为1.

遍历法:前序遍历.中序遍历,后序遍历.

其实这里的前序,中序,后序是按照双亲被遍历的位置而定的.前序就是最先遍历双亲,中序就是在左孩子遍历后遍历双亲,后序就是最后遍历双亲.举个最简单的例子就是如下所示一个最简单的二叉树:

   A

 /   \

B    C

按照前序遍历法就是ABC,中序遍历就是BAC,后序遍历就是BCA.很简单吧.那么对于一个复杂的二叉树来说呢?其实依旧按照这个原则.举下面这个例子.

      A

    /   \

  B     C

/       / \

D      E    F

前序遍历就是ABDCEF,中序遍历则为DBAECF,后序遍历为DBEFCA.怎么来的呢?就是把一棵大树划分为一棵棵小树,然后按照上面前序,中序,后序的次序来遍历.如上的书就可以分为以下小树

  A            B             C

 /  \         /              /  \

B    C       D             E    F

这里拿前序遍历来详细说明.先从根结点开始,遇到了

   A

 /   \

B    C

这个二叉树,根据前序的定义,这是ABC,此时我们发现B还有左孩子,于是接着看

  B

/

D

这个二叉树,遍历应该是BD,于是这里的BD根前面的ABC合并后变成了ABDC,接着我们看到C也有孩子,于是

 C

/   \

E     F

遍历是CEF,再把刚才的ABDC合并就有了最后的结果ABDCEF.

那么代码如何表示呢?这里就显示出了递归的魅力了.这里就不说明了.分别是

前序遍历:

BOOL PreOrderTraverse(BiTree T)
{
    if(NULL==T)//如果是空树,则返回false
       return false;

    printf("%c",T->Data);//输出当前结点的数据
    PreOrderTraverse(T->lchild);//递归当前结点的左孩子
    PreOrderTraverse(T->rchild);//递归当前结点的右孩子

    return true;
}

中序遍历:

BOOL PreOrderTraverse(BiTree T)
{
    if(NULL==T)//如果是空树,则返回false
       return false;

    PreOrderTraverse(T->lchild);//递归当前结点的左孩子
    printf("%c",T->Data);//输出当前结点的数据
    PreOrderTraverse(T->rchild);//递归当前结点的右孩子

    return true;
}

后序遍历:

BOOL PreOrderTraverse(BiTree T)
{
    if(NULL==T)//如果是空树,则返回false
       return false;

    PreOrderTraverse(T->lchild);//递归当前结点的左孩子
    PreOrderTraverse(T->rchild);//递归当前结点的右孩子
    printf("%c",T->Data);//输出当前结点的数据

    return true;
}