二叉树的前序、中序、后序遍历详解

二叉树的前序、中序、后序遍历详解

研究了好长时间的二叉树的遍历，总是很迷糊，怕自己忘了，于是写篇博客来记录一下详细过程。
示例二叉树
1、前序遍历：A B D G C E F
根
左
右

(注意，笔者下文用的词记录就是指写到遍历次序里的意思，不同于访问)

首先，记录A结点，访问根节点A，遍历A的左子树B，因为B也要符合前序遍历规则，所以记录B结点访问B结点，将B当作根节点，遍历B的左子树D，记录D访问D，将D当作根节点，遍历D的左子树，发现没有左子树，于是遍历D的右子树G，记录G结点访问G结点，遍历G的左子树，发现没有，接着遍历G的右子树，也没有。回溯到D，D处理完了，回溯到B，B也处理完了，于是到A，遍历A的右子树C。记录C结点访问C，遍历E，记录E访问E，遍历E的左右子树，发现都无。回溯到C，接着处理C的右子树F，记录F访问F，处理F的左右子树，发现都无，此时发现A的右子树全部处理完毕。结束！

2、中序遍历：D G B A E C F
左
根
右

访问根节点A，遍历A的左子树B，将B当作根节点，遍历B的左子树D，将D当作根节点，遍历D的左子树，发现没有，于是记录进行中序遍历第二步，记录D结点，访问D结点，遍历D的右子树G，将G当作根节点，遍历G的左子树，没有，于是记录G，遍历G的右子树，没有，回溯到B，发现B的左子树处理完毕，于是记录B，访问B，遍历B的右子树，发现没有，回溯到A，A的左子树处理完毕，记录A访问A，遍历A的右子树C，将C当作根节点，遍历C的左子树E，将E当作根节点，遍历E的左子树没有，记录E，遍历E的右子树没有，回溯到C，C的左子树处理完毕，记录C访问C，遍历C的右子树F，将F当作根节点，遍历F的左子树没有，记录F访问F，遍历F的右子树没有，回溯到A，A的右子树处理完毕。结束！

3、后序遍历：G D B E F C A
左
右
根

访问根节点A，遍历A的左子树B，将B当作根节点，遍历B的左子树D，将D当作根节点，遍历D的左子树没有，于是遍历D的右子树G，将G当作根节点，遍历G的左子树没有，右子树没有，于是记录G。回溯到D，D的左右子树处理完毕，记录D。回溯到B，B的左右子树处理完毕，记录B，回溯到A，A的左子树处理完毕，接着遍历A的右子树C，将C当作根节点，遍历C的左子树E，将E当作根节点，遍历E的左子树没有，E的右子树没有，于是记录E，回溯到C，C的左子树处理完毕，接着遍历C的右子树F，将F当作根节点，遍历F的左子树没有，右子树也没有，于是记录F，回溯到A，发现A的右子树全部处理完毕，于是记录A。结束！