非遞歸多層樹形結構
非遞歸多層樹形結構
開發過程中經常會遇到返回一些多層樹形結構的需求，而且該屬性結構層級不確定，沒辦法確定用循環次數。此時最方便的方法是使用遞歸來解決，簡單快捷，但是該方式在層級特別深的情況就有問題，可能會導致棧溢出，所以需要使用非遞歸的方式。
數據準備
// 樣例數據，為了圖方便使用 guava 包的數據結構
List<Map<String, Object>> treeData() {
List<Map<String, Object>> list = new ArrayList<Map<String,Object>>();
list.add(ImmutableMap.of("id", "1", "pid", "0"));
list.add(ImmutableMap.of("id", "2", "pid", "0"));
list.add(ImmutableMap.of("id", "3", "pid", "1"));
list.add(ImmutableMap.of("id", "4", "pid", "1"));
list.add(ImmutableMap.of("id", "5", "pid", "3", "tag", "A1"));
list.add(ImmutableMap.of("id", "5", "pid", "3", "tag", "A2"));
list.add(ImmutableMap.of("id", "6", "pid", "3", "tag", "B1"));
list.add(ImmutableMap.of("id", "6", "pid", "3", "tag", "B2"));
list.add(ImmutableMap.of("id", "7", "pid", "4", "tag", "C1"));
list.add(ImmutableMap.of("id", "8", "pid", "4", "tag", "D1"));
list.add(ImmutableMap.of("id", "8", "pid", "4", "tag", "D2"));
list.add(ImmutableMap.of("id", "9", "pid", "2"));
list.add(ImmutableMap.of("id", "10", "pid", "2"));
list.add(ImmutableMap.of("id", "11", "pid", "9", "tag", "E1"));
list.add(ImmutableMap.of("id", "11", "pid", "9", "tag", "E2"));
list.add(ImmutableMap.of("id", "12", "pid", "9", "tag", "F1"));
list.add(ImmutableMap.of("id", "12", "pid", "9", "tag", "F2"));
list.add(ImmutableMap.of("id", "13", "pid", "10", "tag", "G1"));
list.add(ImmutableMap.of("id", "14", "pid", "13", "tag", "H1"));
// ImmutableMap是不可變的，所以需要修改為可修改的map
list = list.stream().map( m -> {
return new HashMap<String, Object>(m);
}).collect(Collectors.toList());
return list;
}
// 根據ID查詢所有子節點
List<Map<String, Object>> findData(String id) {
return treeData().stream().collect(Collectors.groupingBy( m -> m.get("pid").toString(), Collectors.toList())).get(pid);
}
遞歸
@Test
public void testRecuruly() {
List<Map<String, Object>> list = recursively("0");
System.out.println(JSON.toJSONString(list));
}
// 使用遞歸
List<Map<String, Object>> recursively(String pid) {
List<Map<String,Object>> list = findData(pid);
if(list != null && list.size() > 0) {
for(Map<String, Object> m : list) {
List<Map<String,Object>> list2 = recursively(m.get("id").toString());
m.put("children", list2);
}
}
return list;
}
非遞歸
遞歸方式邏輯上很簡單，使用非遞歸的時候主要是參照遞歸的思路，遞歸使用jvm棧空間，我們可以創建自己的棧數據結構，在需要入棧的時候代碼入棧，來達到遞歸的效果。java.util.Stack<E>提供了棧的實現。我們直接用就好了。
// 使用非遞歸 OK
@Test
public void testStack () {
List<Map<String,Object>> list = findData("0");
// 創建棧
Stack<List<Map<String,Object>>> stack = new Stack<List<Map<String,Object>>>();
stack.push(list); // 入棧
while(!stack.isEmpty()) {
List<Map<String,Object>> popList = stack.pop();
for(Map<String, Object> m : popList) {
List<Map<String,Object>> subList = findData(m.get("id").toString());
if(subList != null && subList.size() > 0) {
m.put("children", subList);
stack.push(subList); // 入棧
}
}
}
System.out.println(JSON.toJSONString(list));
}
結果
發現兩種方式的結果一致，說明了遞歸的優化改造完成了。
[
{
"children": [
{
"children": [
{
"pid": "3",
"id": "5",
"tag": "A1"
},
{
"pid": "3",
"id": "5",
"tag": "A2"
},
{
"pid": "3",
"id": "6",
"tag": "B1"
},
{
"pid": "3",
"id": "6",
"tag": "B2"
}
],
"pid": "1",
"id": "3"
},
{
"children": [
{
"pid": "4",
"id": "7",
"tag": "C1"
},
{
"pid": "4",
"id": "8",
"tag": "D1"
},
{
"pid": "4",
"id": "8",
"tag": "D2"
}
],
"pid": "1",
"id": "4"
}
],
"pid": "0",
"id": "1"
},
{
"children": [
{
"children": [
{
"pid": "9",
"id": "11",
"tag": "E1"
},
{
"pid": "9",
"id": "11",
"tag": "E2"
},
{
"pid": "9",
"id": "12",
"tag": "F1"
},
{
"pid": "9",
"id": "12",
"tag": "F2"
}
],
"pid": "2",
"id": "9"
},
{
"children": [
{
"pid": "10",
"id": "13",
"tag": "G1",
"children": [
{
"pid": "13",
"id": "14",
"tag": "H1"
}
]
}
],
"pid": "2",
"id": "10"
}
],
"pid": "0",
"id": "2"
}
]
