java树的深度优先遍历

① 在线等，计算机高手，java深度搜索树代码

//伪代码。我文本框里直接写的
void dfs(treeNode<T> a)
{
iteretor itr=a.children();
while (itr.hasNext())
{
dfs((treeNode)itr.next());//递归调用
}
}
就是这样了。每次迭代的查询子节点，
如果子节点还有子节点就继续向下找，一直找到最深。
直到没有了就弹栈，看看上一级还有没有其他的子节点。
有就遍历他的第二个子节点，没有就弹。
这样的话就是深度优先搜索了。

② 深度优先遍历的过程

设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新的顶点，继续遍历。
template <int max_size>void Digraph<max_size> :: depth_first(void (*visit)(Vertex &)) const
/* Post: The function *visit has been performed at each vertex of the Digraph in depth-first order.
Uses: Method traverse to proce the recursive depth-first order. */
{
bool visited [max_size];
Vertex v;
for (all v in G) visited [v] = false;
for (all v in G) if (!visited [v])
traverse (v, visited, visit);
}
template <int max_size>
void Digraph<max_size>::traverse(Vertex &v, bool visited[ ],void (*visit)(Vertex &)) const
/* Pre: v is a vertex of the Digraph.
Post: The depth-first traversal, using function *visit, has been completed for v and for all vertices that can be reached from v.
Uses: traverse recursively. */
{
Vertex w;
visited [v] = true;
(*visit) (v);
for (all w adjacent to v)
if (!visited [w])
traverse (w, visited, visit);
}
java代码如下：//求DFS的深度优先递归算法public class DNFSreach {
/*** 这里是文档说明* 算法如下*开始*Start;** procere DFS_visit(G,u)* color[u] = Gray;//白色结点u已被发现* for each edge (u,v)do* if color[u] = White then* DFS_visit(G,v);* repeat color[u]=black;//完成后置u为黑色 * end;* * procere DFS(G)* for each vertex u 属于V do* color[u] = white* for vertex each u 属于 V do* if color[u]=white* then DFS_visit(G,u)* repeat* * * 构建一个无向图* 无穷大表示这两个点无边，1表示两者有边* 白色用1表示，灰色用2表示，黑色用3表示* 初始状态均为白色* 搜索中被发现的顶点置为灰色* 结束时，即其邻接表被完全检索之后，其被置为黑色* 构建一个color[8]数组，其中color[0]不用* 初始化为0* S表示无穷大* 0 1 2 3 4 5 6 7 8* -------------------------* 0 * 1 s 1 1 s s s s s* 2 1 s s 1 1 s s s* 3 1 s s s s 1 1 s* 4 s 1 s s s s s 1* 5 s 1 s s s s s 1* 6 s s 1 s s s 1 s* 7 s s 1 s s 1 s s* 8 s s s 1 1 s s s* * 深度优先搜索的结果应该为* 1-2-4-8-5-3-6-7* * @param args*/static int color[];static int d =0;public static void main(String[] args) {int s = Integer.MAX_VALUE;int G[][]={{s,s,s,s,s,s,s,s,s},{s,s,1,1,s,s,s,s,s},{s,1,s,s,1,1,s,s,s},{s,1,s,s,s,s,1,1,s},{s,s,1,s,s,s,s,s,1},{s,s,1,s,s,s,s,s,1},{s,s,s,1,s,s,s,1,s},{s,s,s,1,s,s,1,s,s},{s,s,s,s,1,1,s,s,s}};color = new int [9];ProcereDFS(G,9);}public static void ProcereDFS(int [][]G,int n){//图是以二维数组的形式保存//n是二维数组的维数for(int i=1;i <= n-1;i++){color[i]=1;//把每一个顶点都置为白色，表示还没搜索}for(int i=1;i<= n-1;i++){//对于每一个顶点没被访问的顶点进行访问if(color[i] == 1){DFS_visit(G,i);//遍历其访问的顶点}}}
private static void DFS_visit(int[][] g, int i) {// TODO 自动生成的方法存根color[i] = 2;//标志为灰色，表示被访问过d++;if(d != g.length-1)System.out.print(+i+ -> );if(d == g.length-1){System.out.println(+i);}for(int t=1;t<= g.length-1;t++){//邻接点没有被访问到if(color[t] == 1 && g[i][t] != Integer.MAX_VALUE){DFS_visit(g,t);}}color[i] = 3;//标志位黑色}}

③ 简述深度优先搜索遍历的方法。

简述深度优先搜索遍历的方法？深度优先搜索算法(Depth-First-Search, DFS)，最初是一种用于遍历或搜索树和图的算法，在LeetCode中很常见，虽然感觉不难，但是理解起来还是有点难度的。

简要概括，深度优先的主要思想就是“不撞南墙不回头”，“一条路走到黑”，如果遇到“墙”或者“无路可走”时再去走下一条路。

思路
假如对树进行遍历，沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当达到边际时回溯上一个节点再进行搜索。如下图的一个二叉树。


首先给出这个二叉树的深度优先遍历的结果(假定先走左子树)：1->2->4->5->3->6->7

那是怎样得到这样的结果呢？
根据深度优先遍历的概念：沿着这树的某一分支向下遍历到不能再深入为止，之后进行回溯再选定新的分支。

定义节点

class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
递归的方式

分别对左右子树进行递归，一直到底才进行回溯。如果不了解递归可以参考我的博客你真的懂递归吗？。

class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式

上面实现了递归方式的深度优先遍历，也可以利用栈把递归转换为迭代的方式。

但是为了保证出栈的顺序，需要先压入右节点，再压左节点。

class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.print(node.val + "->");
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
}
接着再列举个利用深度优先遍历的方式的题目

扫雷
给定一个表示游戏板的二维字符矩阵，'M'表示一个未挖出的地雷，'E'表示一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。

根据以下规则，返回相应位置被点击后对应的面板：

如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。
示例

输入:

[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

输出:

[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
思路：根据给定的规则，当给定一个Click坐标，当不为雷的时候以此坐标为基点向四周8个方向进行深度遍历，把空格E填充为B，并且把与地雷M相连的空方块标记相邻地雷的数量。

注意 ：



在这个题中可以沿着8个方向递归遍历，所有要注意程序中，采用了两个for循环可以实现向8个方向递归。