前言
前面我们对二叉树进行了基础知识讲解，本篇我们对二叉树的遍历实现进行讲解
二叉树的遍历
二叉树的遍历分为四种，分别是：前序遍历、中序遍历、后序遍历、层序遍历
顾名思义
前序遍历：根节点在最前面，先遍历根节点，再遍历左子树，最后遍历右子树
中序遍历：根节点在中间，先遍历左子树，再遍历根节点，最后遍历右子树
后序遍历：根节点在最后面，先遍历左子树，再遍历右子树，最后遍历根节点
注意，此处的左右子树与根节点是相对而言的，例如下图
A是根节点，那么BDE就是它的左子树，CFG就是它的右子树
同样，在左子树BDE中，B又是根节点，D是它的左子树，E是它的右子树
在右子树CFG中，C是根节点，F是左子树，G是右子树
在D中，D是根节点，左右子树均为空
因此，根节点与左右子树都是相对的，是变化的，不是绝对的
前序遍历
前序遍历，就是先遍历根，再遍历左子树，最后遍历右子树
附图讲解：
如果我们采取前序遍历的话，假定遍历方式为输出
那么第一个输出的节点则是根节点A，之后进入左子树BDE；
在A的左子树BDE中，输出根节点B，之后进入左子树D；
在B的左子树D中，输出根节点D，之后进入左边的NULL（空），如图：
因为D没有链接到存在的左右子树，因此我们将它的左右子树均视为空，即NULL，也就是D的left和right指针均指向NULL，之后检测到root == NULL符合条件，返回
此时继续执行，进入右边的NULL，检测为空，返回
此时到达B的右子树E，输出根节点E，进入左边的NULL，后面同上，输出NULL后进入右边的NULL，输出NULL，返回到B
此时A的左子树BDE已经遍历完了，继续进入A的右子树CFG
在A的右子树CFG中，输出根节点C，进入左子树F
在C的左子树F中，输出根节点F，后面就同上，进入NULL并打印，返回
返回后进入C的右子树G，输出根节点G，后面同上，进入NULL并打印，返回
此时已经遍历完整棵树，并且顺序依次为：
代码实现：
中序遍历
中序遍历：就是先遍历左子树，再遍历根，最后遍历右子树
我们依据对前序遍历的讲解来看中序遍历
代码实现：
根据代码，我们可以看出，中序遍历是先不断地递归，从最开始的根节点起，一直找左子树，直到指向NULL为止
找到NULL后，输出NULL，返回到上一层，打印该层节点，此时打印的节点相当于该树的根节点，打印后再进入右子树
如图，从根节点A开始，不打印，遍历左子树，走左子树BDE
在BDE中，根节点B不打印，进入左子树D
在D中，不打印根节点D，进入左子树NULL,判断root == NULL符合，打印NULL，返回到D的递归函数中，打印D，再进入右子树NULL，打印NULL，后面依此类推
顺序为：
后序遍历
后序遍历：就是先遍历左子树，再遍历右子树，最后遍历根节点
代码实现：
遍历思路同之前一样，一直遍历左子树，再是右子树，最后输出根节点
经过ABD均不打印，到达D的左边的NULL后输出NULL，再进入D的右边NULL，输出NULL
然后输出D，再进入E，不打印E，进入E的左右NULL，输出两次NULL后再输出E
接着输出B，然后进入A的右子树CFG，一直不打印，直到进入F的左NULL，输出两次NULL，输出F，进入G，输出两次NULL，输出G
最后输出C，再输出A
顺序如下：
