在編程生活中，我們總會遇見樹性結構，這幾天剛好需要對樹形結構操作，就記錄下自己的操作方式以及過程。現在假設有一顆這樣樹，（是不是二叉樹都沒關系，原理都是一樣的）
1、深度優先
英文縮寫為dfs即depth first search.
深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的html文件) 。在一個html文件中，當一個超鏈被選擇后，被鏈接的html文件將執行深度優先搜索，即在搜索其余的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著html文件上的超鏈走到不能再深入為止，然后返回到某一個html文件，再繼續選擇該html文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經結束。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。對于上面的例子來說深度優先遍歷的結果就是：a,b,d,e,i,c,f,g,h.(假設先走子節點的的左側)。
深度優先遍歷各個節點，需要使用到堆（stack）這種數據結構。stack的特點是是先進后出。整個遍歷過程如下：
首先將a節點壓入堆中，stack（a）;
將a節點彈出，同時將a的子節點c，b壓入堆中，此時b在堆的頂部，stack(b,c)；
將b節點彈出，同時將b的子節點e，d壓入堆中，此時d在堆的頂部，stack（d,e,c）；
將d節點彈出，沒有子節點壓入,此時e在堆的頂部，stack（e，c）；
將e節點彈出，同時將e的子節點i壓入，stack（i,c）；
...依次往下，最終遍歷完成，java代碼大概如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public void depthfirst() { stack<map<string, object>> nodestack = new stack<map<string, object>>(); map<string, object> node = new hashmap<string, object>(); nodestack.add(node); while (!nodestack.isempty()) { node = nodestack.pop(); system.out.println(node); //獲得節點的子節點，對于二叉樹就是獲得節點的左子結點和右子節點 list<map<string, object>> children = getchildren(node); if (children != null && !children.isempty()) { for (map child : children) { nodestack.push(child); } } }}?//節點使用map存放 |
2、廣度優先
英文縮寫為bfs即breadth firstsearch。其過程檢驗來說是對每一層節點依次訪問，訪問完一層進入下一層，而且每個節點只能訪問一次。對于上面的例子來說，廣度優先遍歷的 結果是：a,b,c,d,e,f,g,h,i(假設每層節點從左到右訪問)。
廣度優先遍歷各個節點，需要使用到隊列（queue）這種數據結構，queue的特點是先進先出，其實也可以使用雙端隊列，區別就是雙端隊列首位都可以插入和彈出節點。整個遍歷過程如下：
首先將a節點插入隊列中，queue（a）;
將a節點彈出，同時將a的子節點b，c插入隊列中，此時b在隊列首，c在隊列尾部，queue（b，c）；
將b節點彈出，同時將b的子節點d，e插入隊列中，此時c在隊列首，e在隊列尾部，queue（c，d，e）;
將c節點彈出，同時將c的子節點f，g，h插入隊列中，此時d在隊列首，h在隊列尾部，queue（d，e，f，g，h）；
將d節點彈出，d沒有子節點，此時e在隊列首，h在隊列尾部，queue（e，f，g，h）；
...依次往下，最終遍歷完成，java代碼大概如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public void breadthfirst() { deque> nodedeque = new arraydeque>(); map node = new hashmap(); nodedeque.add(node); while (!nodedeque.isempty()) { node = nodedeque.peekfirst(); system.out.println(node); //獲得節點的子節點，對于二叉樹就是獲得節點的左子結點和右子節點 list> children = getchildren(node); if (children != null && !children.isempty()) { for (map child : children) { nodedeque.add(child); } } }}//這里使用的是雙端隊列，和使用queue是一樣的 |
總結
以上就是本文關于深度優先與廣度優先java實現代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：https://www.cnblogs.com/toSeeMyDream/p/5816682.html
