Java遍歷樹深度優先和廣度優先的方法是什么

這篇文章主要介紹了Java遍歷樹深度優先和廣度優先的方法是什么的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Java遍歷樹深度優先和廣度優先的方法是什么文章都會有所收獲，下面我們一起來看看吧。

在編程生活中，我們總會遇見樹性結構，這幾天剛好需要對樹形結構操作，就記錄下自己的操作方式以及過程。現在假設有一顆這樣樹，（是不是二叉樹都沒關系，原理都是一樣的）

1、深度優先

英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。對于上面的例子來說深度優先遍歷的結果就是：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 First Search。其過程檢驗來說是對每一層節點依次訪問，訪問完一層進入下一層，而且每個節點只能訪問一次。對于上面的例子來說，廣度優先遍歷的 結果是：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<Map<String, Object>> nodeDeque = new ArrayDeque<Map<String, Object>>();

    Map<String, Object> node = new HashMap<String, Object>();

    nodeDeque.add(node);

    while (!nodeDeque.isEmpty()) {

        node = nodeDeque.peekFirst();

        System.out.println(node);

        //獲得節點的子節點，對于二叉樹就是獲得節點的左子結點和右子節點

        List<Map<String, Object>> children = getChildren(node);

        if (children != null && !children.isEmpty()) {

            for (Map child : children) {

                nodeDeque.add(child);

            }

        }

    }

}

//這里使用的是雙端隊列，和使用queue是一樣的

關于“Java遍歷樹深度優先和廣度優先的方法是什么”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Java遍歷樹深度優先和廣度優先的方法是什么”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。