二叉树遍历算法
2018-08-04 本文已影响29人
萧修
图文解说
二叉树遍历算法
1、先序遍历又称为根左右
遍历规则：
先遍历根节点，然后遍历左节点，最后遍历呦节点。
举例
首先遍历A节点，因为此时A为根节点，记录下来，遍历A下的左节点B
遍历B节点，此时B作为根节点，记录下，B下的左节点，有C
遍历C节点，无左节点，记录C节点，遍历右D节点
D下无左右节点，记录D节点
遍历B的右E节点，无左右节点，记录E
遍历A的右G节点，记录G，有F左节点
遍历F，查询没有左节点，记录F
遍历右H节点，无左右节点，记录H
遍历G下I节点，叶子节点，记录返回。
遍历顺序：ABCDEGFHI
先序遍历：ABCDEGFHI
2、中序遍历又称为左根右
优先遍历左节点，其次遍历根节点，最后遍历右节点。
如图：CDBEAFHGI
3、后序遍历又称为左右根
优先遍历左节点，其次遍历根节点，最后遍历右节点。
如图：DCEBHFIGA
