不使用遞迴,如何構造樹結構

2023-11-10 18:00:51

原理很簡單,利用物件參照特性。

科普一下知識點:

淺拷貝:
淺拷貝又稱為淺複製,淺克隆,淺拷貝是指拷貝時只拷貝物件本身(包括物件中的基本變數),而不拷貝物件包含的參照所指向的物件,拷貝出來的物件的所有變數的值都含有與原來物件相同的值,而所有對其他物件的參照都指向原來的物件,簡單地說,淺拷貝只拷貝物件不拷貝參照。

深拷貝:
深拷貝又稱為深複製,深克隆,深拷貝不僅拷貝物件本身,而且還拷貝物件包含的參照所指向的物件,拷貝出來的物件的所有變數(不包含那些參照其他物件的變數)的值都含有與原來物件的相同的值,那些參照其他物件的變數將指向新複製出來的新物件,而不指向原來的物件,簡單地說,深拷貝不僅拷貝物件,而且還拷貝物件包含的參照所指向的物件。

思路:

在構建樹形結構時,我們最常用方法是使用遞迴演演算法進行處理,讓程式按照我們的想法一步一步的向下查詢子節點,這個過程是程式設計師通過程式碼控制的;

參考物件參照的特性,這個過程其實完全可以利用參照特性自動執行;

進入正題:

第一步:判斷實體中包含 id parentId childList這三個構建一顆樹的必備屬性;

第二步:查詢到每一列資料的下一級元素;

第三步:記錄所有的 id,用於篩選出來第一級的節點,一個簡單的思路,如果 parentId  不存在於 ids陣列中,那麼當前節點一定是一級節點;

第四步:將一級節點加入新陣列,並返回;

直接上程式碼:

 1 public <E extends Object> List<E> tree(List<E> e) {
 2         List<E> result = new ArrayList<>();
 3         List<Long> ids = new ArrayList<>();
 4         for (E e1 : e) {
 5             Method setChildList = e1.getClass().getMethod("setChildList",List.class);
 6             if(ObjectUtils.isEmpty(setChildList)) continue;
 7             Method getId = e1.getClass().getMethod("getId");
 8             if(ObjectUtils.isEmpty(getId)) continue;
 9             long id = (long) getId.invoke(e1);
10             if(ObjectUtils.isEmpty(id)) continue;
11             Method getParentId = e1.getClass().getMethod("getParentId");
12             if(ObjectUtils.isEmpty(getParentId)) continue;
13             long parentId = (long) getParentId.invoke(e1);
14             if(ObjectUtils.isEmpty(parentId)) continue;
15             ids.add(id);
16             List<E> es = e.stream().filter(p -> {
17                 try {
18                     Method pk = p.getClass().getMethod("getParentId");
19                     if (ObjectUtils.isEmpty(pk)) return false;
20                     long pv = (long) pk.invoke(p);
21                     if (ObjectUtils.isEmpty(pv)) return false;
22                     return pv == id;
23                 } catch (Throwable ex) {
24                     return false;
25                 }
26             }).collect(Collectors.toList());
27             if(!ObjectUtils.isEmpty(es)) setChildList.invoke(e1,es);
28         }
29         for (E e1 : e) {
30             Method getParentId = e1.getClass().getMethod("getParentId");
31             if(ObjectUtils.isEmpty(getParentId)) continue;
32             long parentId = (long) getParentId.invoke(e1);
33             if(ObjectUtils.isEmpty(parentId)) continue;
34             if(!ids.contains(parentId)) result.add(e1);
35         }
36 
37         return result;
38     }