与只有一种逻辑遍历它们的线性数据结构（数组、链表、队列、堆栈等）不同，树可以以不同的方式遍历，常见的有中序遍历，前序遍历和后序遍历。
实现各种遍历的方法又包括：
以上图为例：
深度优先遍历：
（a）中序（左，根，右）：4 2 5 1 3
（b）前序（根，左，右）：1 2 4 5 3
（c）后序（左，右，根）： 4 5 2 3 1
广度优先或级别顺序遍历：1 2 3 4 5
中序遍历的使用
在二叉搜索树 (BST) 的情况下，中序遍历以非递减顺序遍历节点。如果要以非递增顺序获取 BST 的节点，可以使用反向的中序遍历的变体。
示例：上图中的中序遍历是 4 2 5 1 3。
前序遍历的使用
前序遍历用于创建树的副本。前序遍历也用于获取表达式树上的前缀表达式。
示例：上图的前序遍历是 1 2 4 5 3。
后序遍历的使用
后序遍历用于创建树的副本。后序遍历也用于获取表达式树上的后缀表达式。
示例：上图的后序遍历为 4 5 2 3 1。
注意：
中序，前序，后序三种不同遍历在算法上的不同主要体现在访问节点的时间不同，分别在遍历中，遍历前，遍历后访问。
再来一个例子：
前序遍历：
中序遍历：
后序遍历：
时间复杂度： O(n)
让我们看看不同的极端情况。
复杂度函数 T(n) — 对于涉及树遍历的所有问题 — 可以定义为：
T(n) = T(k) + T(n – k – 1) + c
其中 k 是根结点一侧的节点数，n - k - 1为另一侧的节点数。
让我们来分析一下极限情况
案例1：倾斜的树（其中一个子树为空，另一个子树为非空）
在这种情况下k为0。
T(n) = T(0) + T(n-1) + c
T(n) = 2T(0) + T(n-2) + 2c
T(n) = 3T(0) + T(n- 3) + 3c T(n) = 4T(0) + T(n-4) +
4c
………………………………………………………………………………
…………。
T(n) = (n-1)T(0) + T(1) + (n-1)c
T(n) = nT(0) + (n)c
T(0) 的值将变成某个常数，我们设为 d。（遍历一棵空树需要一些常数时间）
T(n) = n(c+d)
因此T(n) = O(n)
空间复杂度
如果我们不考虑函数调用的堆栈大小，那么 O(1) 否则 O(h) 其中 h 是树的高度。倾斜树的高度为 n（元素数量），因此最差的空间复杂度为 O(n)，平衡树的高度为 (Log n)，因此最佳空间复杂度为 O(Log n)。
（包含各种语言：C语言、Python、Java，C++等均有示例）
免费资源下载：树的遍历
