树的遍历
遍历方法
BFS（宽度优先搜索）
以下图的顺序进行访问
即先被访问的结点先拿出来
与其相似地，队列也具有先进先出的特点
DFS（深度优先搜索）
以下图的顺序进行访问
先序遍历
以下图的顺序进行访问
即按照 根 左 右的顺序访问
函数实现：使用递归的方法
点击查看代码
// 递归求深度，NIL=-1
void set_depth(int u, int d) {
if (u == NIL) return;
D[u] = d;
set_depth(T[u].left, d + 1);
set_depth(T[u].right, d + 1);
}
中序遍历
以下图的顺序进行访问
即按照 左 根 右的顺序访问
函数实现：
点击查看代码
void set_depth(int u, int d) {
if (u == NIL) return;
set_depth(T[u].left, d + 1);
D[u] = d;
set_depth(T[u].right, d + 1);
}
后序遍历
以下图的顺序进行访问
即按照 左 右 根的顺序访问
函数实现：
点击查看代码
void set_depth(int u, int d) {
if (u == NIL) return;
set_depth(T[u].left, d + 1);
set_depth(T[u].right, d + 1);
D[u] = d;
}
结论
所以我们就可以通过一棵树对应的三种访问顺序来还原这棵树
比如如果一棵树的先序，中序，后序访问顺序分别为
1 2 3 4 5
3 2 4 1 5
3 4 2 5 1
那么我们就可以还原出这棵树是下图的样子