二叉树定义

每个节点的子节点数(度)不能大于2

先序遍历

• 定义：从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
  image
  以上先序遍历输出的即如果为：ABDHIEJCFG
  访问顺序为：

从根结点出发，则第一次到达结点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；

中序遍历

• 定义：从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
  中序遍历上图的输出结果是：HDIBJEAFCG
  访问顺序

先访问A节点，因为是第一次访问所以不输出，再访问左子节点到B，因为左子节点不为空，再访问左子节点到D，再访问D的左子节点H，因为H为叶子节点，直接输出H， -----> H
然后返回D，到D是第二次访问了，直接输出D， -----> HD
然后再访问右子节点I，右子节点是叶子节点，所以直接输出I ----->HDI
...

后序遍历

• 定义：从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问
  后序遍历输出结果是:HIDJEBFGCA
  访问顺序

从根结点出发，则第一次到达结点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；

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