二叉树遍历方法

众所周知，二叉树的遍历方法分为4类，分别为先序遍历、中序遍历、后序遍历和分层遍历。记得当初学习二叉树的时候，对先序遍历、中序遍历和后序遍历总是混淆（上课时没认真听讲），忘记访问的顺序，后来自己归纳总结了两点，然后就再也没忘记过，下面来介绍下我的记忆小窍门

先、中、后代表根的位置
子节点的顺序是从左至右不变

先序遍历：根、左子树、右子树
中序遍历：左子树、根、右子树
后序遍历：左子树、右子树、根

好了下面通过示例，再描述下二叉树遍历的过程。

分层遍历

最容易理解的就是分层遍历，分层遍历按照从上至下、从左至右的顺序依次访问每个结点。下面通过一个示意图来表示二叉树分层遍历顺序

分层遍历二叉树结果：ABCDEF

分层遍历访问结点顺序

先序遍历

首先回忆下先序遍历的规则：根、左子树、右子树。根据规则，首先访问根A，然后是左子节点B，再访问完B后，并不是直接去访问A的右子节点C，因为A的左子树还没有访问完，所以下面访问的节点是D。节点D没有子节点，所以接着访问结点E。当访问完节点E后，根A的整个左子树访问完毕，接下来开始访问A的右子节点C，后面的访问顺序同节点B。

先序遍历二叉树结果：ABDECFG

先序遍历访问节点顺序

中序遍历

回忆下中序遍历的规则：左子树、根、右子树。根据规则，首先判断节点A，因为A是根节点，所以接下来判断其左子结点B。节点B相对于节点D、E来说，也是根节点，所以继续判断节点B的左子结点D，节点D是叶子节点，所以第一个访问的是节点D。访问完节点D后，节点B的左子树都访问完成，然后紧接着访问结点B，节点E。访问完节点E后，节点A的左子树都访问完成，然后访问节点A，紧接着同理访问节点A的右子树。