树：熟练手写树的四种遍历方式

树的四种遍历方式

树也是一种用来提高查询效率的数据结构（和哈希表类似）。例如MySQL中的索引就可以基于B+树或者哈希表构建，MongoDB用B树（也称为B-树）来实现索引。

很多关于树的面试题其实都不难，基本上是基于树的四种遍历方式来实现的，所以熟练手写树的四种遍历方式非常重要

我们先说前中后序这三种遍历方式

前序遍历：根，左，右
中序遍历：左，根，右
后序遍历：左，右，根

发现规律没？左右的位置始终不变，前序遍历，根在前面，中序遍历，根在中间，后序遍历根在最后。

前序遍历：A B C D E F
中序遍历：C B D A E F
后序遍历：C D B F E A

这三种遍历方式的模版如下，三种遍历方式的区别只是对root节点做操作的时机不同