在編程生活中，我們總會遇見樹性結構，這幾天剛好需要對樹形結構操作，就記錄下自己的操作方式以及過程。現在假設有一顆這樣樹，（是不是二叉樹都沒關係，原理都是一樣的）
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代碼大概如下：
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代碼大概如下：
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實現代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！