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個方向遞歸。