多級樹的深度優(yōu)先遍歷與廣度優(yōu)先遍歷（Java實(shí)現(xiàn)）
深度優(yōu)先遍歷與廣度優(yōu)先遍歷其實(shí)是屬于圖算法的一種，多級樹可以看做是一種特殊的圖骚揍，所以多級數(shù)的深/廣遍歷直接套用圖結(jié)構(gòu)的遍歷方法即可。
工程中后端通常會用多級樹來存儲頁面表單的各級聯(lián)動類目跨嘉，本文提供了深度遍歷與廣度遍歷的示例抗悍，在使用時只要根據(jù)你的業(yè)務(wù)需求稍加改動即可。
我們知道脸狸，遍歷有遞歸最仑，非遞歸兩種方式。在工程項目上肥惭，一般是禁用遞歸方式的盯仪，因?yàn)檫f歸非常容易使得系統(tǒng)爆棧。同時蜜葱，JVM也限制了最大遞歸數(shù)量全景，在你的樹結(jié)構(gòu)非常深的時候很容易出現(xiàn)StackOverflowError異常，所以最好采用非遞歸的方式牵囤。
節(jié)點(diǎn)模型
public class Node {
//值
public int value;
//所有的子節(jié)點(diǎn)
public ArrayList<Node> nexts;
public Node(int value) {
this.value = value;
}
}
深度優(yōu)先遍歷
深度優(yōu)先搜索英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止爸黄，而且每個節(jié)點(diǎn)只能訪問一次。多級樹可以看做一個特殊的圖結(jié)構(gòu)揭鳞，總的來說遍歷的方法還是不變的炕贵，都是利用棧和Set來進(jìn)行操作。
主要步驟：
- 準(zhǔn)備一個棧結(jié)構(gòu)和一個Set結(jié)構(gòu)的集合野崇，棧用來記錄還有孩子沒有被遍歷到的節(jié)點(diǎn)称开，Set用來記錄遍歷的歷史記錄
- 將首節(jié)點(diǎn)加入到棧和set中
- 彈棧拿到首節(jié)點(diǎn)
- 從首節(jié)點(diǎn)開始深度遍歷，下面示例代碼配合注解近進(jìn)行理解。
public static void dfs(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<>();
HashSet<Node> set = new HashSet<>();
stack.add(node);
set.add(node);
System.out.println(node.value);
while (!stack.isEmpty()) {
//彈棧獲得一個節(jié)點(diǎn)
Node cur = stack.pop();
//查看這個節(jié)點(diǎn)的所有孩子
for (Node next : cur.nexts) {
//如果有孩子是之前沒有遍歷到的鳖轰，說明這個節(jié)點(diǎn)沒有深度遍歷完
if (!set.contains(next)) {
//此節(jié)點(diǎn)與其孩子加入棧與Set中
stack.push(cur);
stack.push(next);
set.add(next);
System.out.println(next.value);
break;
}
}
}
}
廣度優(yōu)先遍歷
寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是最簡便的圖的搜索算法之一清酥，這一算法也是很多重要的圖的算法的原型。對于多級數(shù)來說蕴侣，就是先遍歷該節(jié)點(diǎn)的所有孩子焰轻，然后在遍歷孩子節(jié)點(diǎn)的所有孩子，先遍歷一層再遍歷下一次層昆雀。
主要思路就是利用隊列來將下一層的所有節(jié)點(diǎn)記錄下來辱志，然后順序遍歷就可以了。
public static void bfs(Node node) {
if (node == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
//用來注冊已加入隊列的節(jié)點(diǎn)——>防止重復(fù)添加節(jié)點(diǎn)
HashSet<Node> set = new HashSet<>();
queue.add(node);
set.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value);
//將節(jié)點(diǎn)的所有下游節(jié)點(diǎn)加入到隊列
for (Node next : cur.nexts) {
if (!set.contains(next)) {
set.add(next);
queue.add(next);
}
}
}
}
