深入学习二叉树：二叉树基础4

问题导读

1.二叉树遍历分为哪四种？
2.层次遍历和其它遍历有什么不同？
3.如何实现层次遍历？


上一篇深入学习二叉树：二叉树基础3
https://www.aboutyun.com/forum.php?mod=viewthread&tid=30548


二叉树遍历
二叉树的遍历一个重点考查的知识点。


3.8.1 定义
二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
二叉树的访问次序可以分为四种：

前序遍历
中序遍历
后序遍历
层序遍历
复制代码

3.8.2 前序遍历
前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。




图3.13所示二叉树访问如下：

从根结点出发，则第一次到达结点A，故输出A;
继续向左访问，第一次访问结点B，故输出B；
按照同样规则，输出D，输出H；
当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；
I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；
向E左子树，故输出J；
按照同样的访问规则，继续输出C、F、G；

则3.13所示二叉树的前序遍历输出为：
ABDHIEJCFG


3.8.3 中序遍历
中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。

图3.13所示二叉树中序访问如下：

从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；
H右子树为空，则返回至D，此时第二次到达D，故输出D；
由D返回至B，第二次到达B，故输出B；
按照同样规则继续访问，输出J、E、A、F、C、G；

则3.13所示二叉树的中序遍历输出为：
HDIBJEAFCG


3.8.4 后序遍历
后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。

图3.13所示二叉树后序访问如下：

从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H；
H右子树为空，则返回至H，此时第三次到达H，故输出H；
由H返回至D，第二次到达D，不输出D；
继续访问至I，I左右子树均为空，故第三次访问I时，输出I；
返回至D，此时第三次到达D，故输出D；
按照同样规则继续访问，输出J、E、B、F、G、C，A；

则图3.13所示二叉树的后序遍历输出为：
HIDJEBFGCA
虽然二叉树的遍历过程看似繁琐，但是由于二叉树是一种递归定义的结构，故采用递归方式遍历二叉树的代码十分简单。
递归实现代码如下：

/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
    return;
    printf("%c", T->data);  /*显示结点数据，可以更改为其他对结点操作*/
    PreOrderTraverse(T->lchild);    /*再先序遍历左子树*/
    PreOrderTraverse(T->rchild);    /*最后先序遍历右子树*/
}


/*二叉树的中序遍历递归算法*/
void InOrderTraverse(BiTree T)
{
    if(T==NULL)
    return;
    InOrderTraverse(T->lchild); /*中序遍历左子树*/
    printf("%c", T->data);  /*显示结点数据，可以更改为其他对结点操作*/
    InOrderTraverse(T->rchild); /*最后中序遍历右子树*/
}


/*二叉树的后序遍历递归算法*/
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
    return;
    PostOrderTraverse(T->lchild);   /*先后序遍历左子树*/
    PostOrderTraverse(T->rchild);   /*再后续遍历右子树*/
    printf("%c", T->data);  /*显示结点数据，可以更改为其他对结点操作*/
}
复制代码

3.8.5 层次遍历
层次遍历就是按照树的层次自上而下的遍历二叉树。针对图3.13所示二叉树的层次遍历结果为：
ABCDEFGHIJ
层次遍历的详细方法可以参考二叉树的按层遍历法。

3.8.6 遍历常考考点
对于二叉树的遍历有一类典型题型。
1）已知前序遍历序列和中序遍历序列，确定一棵二叉树。
例题：若一棵二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，请画出这棵二叉树。
分析：前序遍历第一个输出结点为根结点，故A为根结点。早中序遍历中根结点处于左右子树结点中间，故结点A的左子树中结点有CB，右子树中结点有EDF。
如图3.14所示：




按照同样的分析方法，对A的左右子树进行划分，最后得出二叉树的形态如图3.15所示：





2）已知后序遍历序列和中序遍历序列，确定一棵二叉树。
后序遍历中最后访问的为根结点，因此可以按照上述同样的方法，找到根结点后分成两棵子树，进而继续找到子树的根结点，一步步确定二叉树的形态。
注：已知前序遍历序列和后序遍历序列，不可以唯一确定一棵二叉树。


4 结语
通过上述的介绍，已经对于二叉树有了初步的认识。本篇文章介绍的基础知识希望读者能够牢牢掌握，并且能够在脑海中建立一棵二叉树的模型，为后续学习打好基础。





大数据爱好者可加微信w3aboutyun



作者：MrHorse1992
链接：https://www.jianshu.com/p/bf73c8d50dc2