概念:就是从二叉树的根结点出发,按照一定得次序依次访问二叉树中的所有结点,是的每个结点被访问到的次数都为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;
}