二叉树遍历

¶二叉树遍历

二叉树遍历是沿着某条路径，依次对每个节点均做一次且仅做一次访问。
二叉树遍历按照节点访问顺序分为前序遍历、中序遍历和后序遍历。

¶前序遍历

¶访问方式

按照根节点->左子树->右子树的方式访问二叉树。

¶理解

1. 首先访问根节点A
2. 之后访问根节点的左子树的B节点
3. 以B节点为根，访问B节点的左边节点D，D节点已经是最末节点
4. 之后访问B节点的右边节点F
5. 然后以节点F为根，首先访问F节点的左边节点E，E节点已经为最末节点
6. 并且F节点没有右边节点，这时，二叉树的左子树访问完毕
7. 开始访问二叉树的右子树的C节点
8. 节点C有左节点G，首先访问左节点G
9. G没有左节点，却有右节点，因此访问G节点的右边节点H
10. 节点H已经是最末节点，C节点的左子树访问完毕
11. 开始访问C节点的右子树上的节点I
12. 节点I没有任何子树，因此I节点是末端节点
13. 至此，整个二叉树的节点访问完毕
    前序遍历结果：A->B->D->F->E->C->G->H->I

¶中序遍历

¶访问方式

按照左子树->根节点->右子树的方式访问二叉树。

¶理解

1. 首先访问左子树，从左子树的最左端D节点开始
2. 由于D节点没有子节点，因此D节点回溯到D的父节点B
3. 从B节点的右子树的最左端E开始
4. E节点访问父节点F,此时，二叉树的左子树访问完毕
5. 开始访问二叉树的根节点A
6. 开始访问二叉树的右子树，从右子树的最左端G开始
7. G有一个子节点H，首先访问H
8. G访问完子节点后开始回溯到父节点C
9. C节点有右边节点I
10. I没有任何子节点，此时，整个二叉树访问完毕。
    中序遍历的结果：D->B->E->F->A->G->H->C->I
    由此可知，中序遍历是从左到右遍历的，计算中序遍历有简单直观的投影法
    

¶后序遍历

¶访问方式

按照左子树->右子树->根节点的方式访问二叉树。

¶理解

1. 从左子树的最左端D节点开始访问，D节点的父节点是B节点
2. 之后从左子树的最右端E节点访问，E节点的父节点是F节点
3. E节点已经是最右端了，因此开始访问E节点的父节点F节点
4. F节点也已经是最右端节点，并且与D节点有同一个父节点B
5. 因此，最终访问父节点B，B节点的父节点A是整个二叉树的根节点，需要最后访问
6. 左子树访问完毕，开始访问右子树。从右子树的最左端H节点开始访问
7. H节点没有子节点，因此访问父节点G
8. G节点的子节点访问完后，开始访问其父节点C的右子树的节点I
9. I节点没有子节点，因此可以最终访问父节点C
10. 这时二叉树的右子树访问完毕，并且左子树也访问完毕，最终访问根节点A
    后序遍历的结果：D->E->F->B->H->G->I->C->A

¶结论

由以上二叉树访问流程可知，整个二叉树的遍历就是一个递归的过程。