树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS），其实这两种方式主要是图的遍历方式，但是树可以被抽象为简单的图，所以这两种方式也可以作为树的遍历方式。
- 常见的DFS：先序遍历、中序遍历、后序遍历
- 常见的BFS：层序遍历（按层遍历）
深度优先搜索（DFS）简单来说就是沿着每一个分支路径遍历直到不能再深入为止，也就是到达了叶节点。如果到达叶节点，那我们就向上回溯，回到叶节点之前的那一个节点，接着遍历该节点未被访问过的子节点。一直重复这个过程直到所有的节点把遍历完。
以上图为例，我们走一下整体的遍历流程：
- 首先访问A节点，接着我们访问A的子节点B节点
- B节点访问之后，我们在访问B的子节点D节点
- D节点没有子节点，所以我们向上回溯，访问B节点
- 发现B节点的的子节点E未被访问，那么我们访问E节点
- E节点有子节点I节点，我们访问E节点的子节点I
- I节点为叶节点，没有子节点，所以我们向上回溯到E节点
- E节点的所有节点都被访问过了，继续回溯到上一个节点B
- B节点的所有子节点也都被访问过了，继续回溯到A节点，发现A的子节点C未被访问，访问C
- 重复上述过程，知道所有的节点被访问…
实现这个过程的时候有一个关键点，我们可以设置一个visited[]数组，长度为节点的个数，初始值为0，如果被访问了将其对应下标位置的visited[index]设置为1，防止重复访问，陷入死循环。
实现方式
深度优先搜索（DFS）的实现方式主要有两种：
- 递归实现
- 迭代实现（依靠栈数据结构）
递归实现
迭代实现
首先我们要知道栈这种数据结构是先进后出，所以我们入栈的时候要先压入最右的节点，然后依次从右往左压入节点，这样就能保证出栈的时候首先访问左节点。
具体的步骤如下：
- 首先我们将节点A压入栈中，stack(A)
- 然后我们将A出栈，同时将A的子节点从右到左压入栈中，此时B在栈的顶部，stack(B,C)
- 然后将B节点弹出，同时将B的子节点E，D压入栈中，此时D在栈的顶部，stack（D,E,C）
- 然后将D节点弹出，没有子节点压入,此时E在栈的顶部，stack（E，C）
- 然后将E节点弹出，同时将E的子节点I压入，stack（I,C）
- 重复上述过程，直到栈空，最终遍历完成
广度优先搜索就是层序遍历，顾名思义就是按照树的层次结构一层一层遍历，访问完一层我们就进入下一层，且每个节点只能访问一遍。上图按照广度优先搜索方式的结果为：A,B,C,D,E,F,G,H,I(假设每层节点从左到右访问)。
实现方式
广度优先搜索的实现方式主要有两种：
- 递归实现
- 迭代实现（依靠队列数据结构）
递归实现
广度优先搜索使用递归的方式较为繁琐，可以直接使用迭代的方式。
迭代实现
通过迭代实现树的层序遍历，需要借助数据结构队列先进先出的特性。我们以上图为例进行分析。
具体实现步骤
我们通过数组res[]来保存出队的元素
- 首先将节点A插入队列，队列中有元素A，queue(A)
- 接着将A出队，将A存入数组，同时将A的左右节点依次插入队列，queue(B,C)
- 然后将B出队，存入数组，同时将B的左右节点依次插入队列，queue(C,D,E)
- 然后将C出队，存入数组，同时将C的左右子节点依次插入队列，queue(D,E,F,G,H)
- 重复上述过程，直到队列为空，res中保存了树层序遍历的结果。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/3588.html