golang工程师应该会的数据结构与算法二叉树遍历
@author 汪春波
遍历
树的遍历方法也同样适用于二叉树（如右图4-11所示），不过由于二叉树的自身特点，还有一种中序遍历法。
前序遍历（根左右）
前序遍历（根左右，先访问根结点，然后分别用前序分别遍历左、右子树，也称为前根遍
历）。图4-11的前序遍历结果是：1，2，4，5，7，8，3，6。
中序遍历（左根右）
中序遍历（左根右，先按中序遍历左子树，再访问根结点，然后再按中序遍历右子树，也称为
中根遍历）。图4-11的中序遍历的结果是：4，2，7，8，5，1，3，6。
首先 根为 1
最左边。2 的子树， 左4 2 ；得到遍历数字4 2
左边有 5 的子树， 左 7 根5
但是 7 也有子树， 左 空 根 7 右 8
这里得到7 8 5
总共为 4 2 7 8 5
同理推出：右边 从1 开始（这里最右就是1开始）
1 下面 左 空 根 1 右边 3
得到 1 3
3 子节点， 左空 根 3 右 6
得到 3 6
加起来 为 1 3 6
所以全部加起来为：4，2，7，8，5，1，3，6
后序遍历
后序遍历（左右根，分别按后序遍历要左、右子树，然后再访问根结点，也称为后根遍历）。
图4-11的后序遍历的结果是：4，8，7，5，2，6，3，1。
分析：
左右根，则 根节点1 肯定最后。
左边：
4开始， 4
7开始， 8 7
5开始， 7 5
得到 4 8 7 5
从 2 开始， 4 5 2
结合推一下，得到 4 8 7 5 2
右边： 3 开始， 6 3。
1开始， 3 1。
结合为 6 3 1
上边左右全部结合为： 4 8 7 5 2 6 3 1
层次遍历（最简单的）
层次遍历（首先访问处于0层的根结点，然后从左到右访问1层上的结点，以此类推，层层向下
访问）。图4-11的层次遍历的结果是：1，2，3，4，5，6，7，8。
关于 LearnKu
粤公网安备 44030502004330号