一、概念

 

二叉树：一个根节点，两个子节点(子节点可能没有)。

--整篇文章内容中，左侧的子节点简称左，右侧的子节点简称右，根节点简称根。--

前序(先序)遍历：按根左右的顺序输出。

中序遍历：按左根右的顺序输出。

后序遍历：按左右根的顺序输出。

二、入门练习

如上图这样一个简单的二叉树，我们分别输出三种遍历：

前序遍历：按ABC(根左右)的顺序输出。

中序遍历：按B|A|C(左根右)的顺序输出。

后序遍历：按BCA(左右根)的顺序输出。

比较特殊的是前序和后序。前序中，第一个输出是整棵树的根节点；后序中，最后一个输出是整棵树的根节点。记牢这两点，非常好用。

三、进阶练习

已知，前序遍历: GDAFEMHZ，中序遍历: ADEFGHMZ。画出二叉树图形，并输出后序遍历。

解题顺序：先画出二叉树图形，然后按照图形进行后序遍历。

1.根据前序遍历，我们可知G点是整棵树的根节点。那我们就可以这样分：

前: |G|  DAFEMHZ

中: ADEF  |G|  HMZ

从中序中可以直接的看出，G的左边都是它的左子树下的，G的右边都是它右子树下的。

2.接下来，只看G左边部分 

前: G  |D|  AFEMHZ

中: A  |D|  EF  G  HMZ

前序中D是第一个，也就是根节点，中序中D把剩下来的内容分出了左右。

 

 3.因为左侧的A只分出来一个，说明A下面没有子节点了，我们只需要继续分右侧的EF

前: G  D  A  |F| EMHZ

中: A   D  E  |F|  G  HMZ

同样的，我们从前序中发现，F是第一个，也就是说F是根节点；在中序中，E在F的左侧，说明E是F的左子树。

 

 4.这个时候G的整个左子树都确定好了，轮到右子树了。

 前: G   D  A  F  E  |M| HZ

中: A   D  E  F   G  H |M| Z

从前序中，我们可以确定M是右侧的根节点，中序被M分成了左右各一个，说明H和Z正好是M的左右子树。

  5.总结

 通过以上步骤，我们可以发现，先从先序中确定根节点，再通过根节点，看中序中被分割后的位置，判断出节点对应左右子树位置。

6.输出后序

后序是左右根，那我们就看图，找最左边(不一定是最底层)的那一个。

1.从GDM看，左边是D，从DAF看，左边是A，到A就没有然后了。输出结果：A

2.找完左，在以A为子节点的二叉树(DAF)中，找到同级(同一个根节点下)的右子树，存在F，这个时候回到1步骤，从FE找左，就是E，到E没有然后了。输出结果：AE

3.找完左，在以E为子节点的二叉树(FE)中，找到同级的右子树，不存在，没有输出项。

4.FE二叉树的左右都输出了，输出根F。输出结果：AEF

5.DAF二叉树的左右都输出了，输出根D。输出结果：AEFD

6.GDM的左找完了，找右子树，存在M，继续找MHZ的左，就是H，到H就没有然后了。输出结果：AEFDH

7.找完左，在以H为子节点的二叉树(MHZ)中，找到同级的右子树，存在Z，到Z就没有然后了。输出结果：AEFDHZ

8.MHZ二叉树的左右都找完了，输出根M。输出结果：AEFDHZM

9.GDM这层的左右都找完了，输出根G。输出结果：AEFDHZMG

整个逻辑，就是递归

后序：递归输出左，递归输出右，递归输出根。

前序：递归输出根，递归输出左，递归输出右。

中序：递归输出左，递归输出根，递归输出右。

JAVA代码实现二叉树的三种遍历