Java實(shí)現(xiàn)平鋪列表(List)互轉(zhuǎn)樹形(Tree)結(jié)構(gòu)
很多時候?yàn)闈M足前后端交互的數(shù)據(jù)結(jié)構(gòu)需求，往往我們需要把平鋪的
List數(shù)據(jù)與Tree型層級數(shù)據(jù)結(jié)構(gòu)進(jìn)行互轉(zhuǎn)，這篇文章提供詳實(shí)的遞歸和非遞歸的方式去實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換，為了使用到lambda的特性，Java version >=8。
需求
我們從基礎(chǔ)設(shè)施層獲取了一個列表數(shù)據(jù)，列表其中的對象結(jié)構(gòu)如下，注意約束條件如果沒有pid，默認(rèn)為null。
@Getter
@Setter
@ToString
@Builder
public class NodeEntity {
/**
* id
*/
private Long id;
/**
* 父id
*/
private Long pid;
}現(xiàn)在我們要將List<NodeEntity> 數(shù)據(jù)，按照屬性pid進(jìn)行Tree型層級封裝，并且支持多層級封裝。一般很容易想到遞歸的實(shí)現(xiàn)方法，接下來這篇文章使用一套通用的解決辦法，非遞歸實(shí)現(xiàn)結(jié)構(gòu)轉(zhuǎn)換。
實(shí)踐List to Tree
遞歸實(shí)現(xiàn)
首先定義通用的Tree形數(shù)據(jù)接口。
public interface INodeDTO {
/**
* id
* @return id
*/
public Long getId();
/**
* pid
* @return pid
*/
public Long getPid();
/**
* 獲取Children
* @return Children
*/
public List<INodeDTO> getChildren();
/**
* 設(shè)置children
* @param children children
*/
public void setChildren(List<INodeDTO> children);
}每個方法接口有詳細(xì)的注釋，無需多說。然后提供通用的轉(zhuǎn)換Function。
/**
* 非遞歸實(shí)現(xiàn)平鋪數(shù)據(jù)轉(zhuǎn)成Tree型結(jié)構(gòu)
*/
static final Function<List<INodeDTO>,List<INodeDTO>> MULTI_TREE_CONVERTER = sources->
sources.stream()
.filter(item->{
item.setChildren(
sources.stream()
.filter(e-> Objects.equals(e.getPid(), item.getId()))
.collect(Collectors.toList()));
return item.getPid() == null;})
.collect(Collectors.toList());我們利用對象引用，淺拷貝的原理，通過循環(huán)查找來組裝層級，最后根據(jù)pid==null的數(shù)據(jù)一定是Tree型第一層的數(shù)據(jù)的條件進(jìn)行過濾，篩選出第一層的數(shù)據(jù)組合成新的列表，達(dá)到目的。
非遞歸實(shí)現(xiàn)
//Establish tree structure
static List<INodeDTO> buildTree (List<INodeDTO>sources){
List<INodeDTO> results = new ArrayList<>();
//get root nodes
List<INodeDTO> rootNodes = sources.stream().filter(x->x.getPid() == null).collect(Collectors.toList());
for (INodeDTO rootNode : rootNodes) {
results.add(buildChildTree(sources,rootNode));
}
return results;
}
//Recursion, building subtree structure
static INodeDTO buildChildTree(List<INodeDTO>sources,INodeDTO pNode){
List<INodeDTO> children = new ArrayList<>();
for (INodeDTO source : sources) {
if(source.getPid()!=null && source.getPid().equals(pNode.getId())){
children.add(buildChildTree(sources,source));
}
}
pNode.setChildren(children);
return pNode;
}遞歸的實(shí)現(xiàn)先獲取所有根節(jié)點(diǎn)，方法builTree總結(jié)根節(jié)點(diǎn)來創(chuàng)建一個樹結(jié)構(gòu)，buildChilTree為節(jié)點(diǎn)構(gòu)建一個輔助樹，并拼接當(dāng)前樹，遞歸調(diào)用buildChilTree來不斷打開當(dāng)前樹的分支和葉子，直到?jīng)]有找到新的子樹, 完成遞歸，得到樹結(jié)構(gòu)。
遞歸最大的問題可能堆棧太深，容易造成溢出，使用需要謹(jǐn)慎，而且從代碼簡潔度來說，肯定是使用了非遞歸的方式更好。
遞歸代碼還能進(jìn)一步優(yōu)化，比如改成尾遞歸的方式，有興趣的小伙伴可以嘗試一下。
實(shí)例
實(shí)例只測試非遞歸實(shí)現(xiàn)方法。
那具體怎么使用呢？首先我們通過implements接口INodeDTO,實(shí)現(xiàn)我們自己的業(yè)務(wù)DTO。
@Getter
@Setter
@ToString
@Builder
public class NodeDTO implements INodeDTO {
private Long id;
private Long pid;
List<INodeDTO> children;
}然后在我們Service層組裝業(yè)務(wù)邏輯，這里提供一個listBy的條件查詢接口，從基礎(chǔ)設(shè)施層按照條件撈出List<NodeEntity>，期望轉(zhuǎn)成內(nèi)部包含層級關(guān)系的List<INodeDTO>。
public class UseCase {
public List<INodeDTO> listBy(String ... condtions){
System.out.println(Arrays.stream(condtions).reduce((a, b) -> a + ";" + b).orElse(""));
//TODO get NodeEntities from database
List<NodeEntity> entities = Arrays.asList(
NodeEntity.builder().id(1L).pid(null).build(),
NodeEntity.builder().id(2L).pid(1L).build(),
NodeEntity.builder().id(3L).pid(1L).build(),
NodeEntity.builder().id(4L).pid(3L).build()
);
List<INodeDTO> sources = entities.stream()
.map(Factory.NODE_DTO_BUILDER::apply)
.collect(Collectors.toList());
return INodeDTO.MULTI_TREE_CONVERTER.apply(sources);
}
}提供一個main方法進(jìn)行測試。
public static void main(String[] args) throws JsonProcessingException {
UseCase useCase = new UseCase();
List<INodeDTO> results = useCase.listBy("condtion1", "condtion2");
//convert json with style
ObjectMapper objectMapper = new ObjectMapper();
String json = objectMapper.writerWithDefaultPrettyPrinter().writeValueAsString(results);
System.out.println(json);
}運(yùn)行后輸出結(jié)果如下，經(jīng)人工肉眼檢驗(yàn)，達(dá)到Tree型層級結(jié)構(gòu)。
實(shí)踐Tree to List
上面講到了平鋪列表（List）轉(zhuǎn)樹形（Tree）結(jié)構(gòu)，一般來說對于足夠后端數(shù)據(jù)轉(zhuǎn)成前端想要的結(jié)構(gòu)了。但都支持了正向轉(zhuǎn)換，那么反向轉(zhuǎn)換，即樹形（Tree）結(jié)構(gòu)如何轉(zhuǎn)平鋪列表（List）呢？
遞歸實(shí)現(xiàn)
遞歸實(shí)現(xiàn)，分為兩個函數(shù)，List<INodeDTO> flatten(List<INodeDTO> flatList) 接受外部調(diào)用，傳入待轉(zhuǎn)換的Tree形結(jié)構(gòu)。第一步便是收集所有的根節(jié)點(diǎn)，然后將所有的根節(jié)點(diǎn)傳入到遞歸函數(shù)List<INodeDTO> flatten(INodeDTO node, List<INodeDTO> flatList中深度遍歷，最后匯總再使用distinct做去重處理得到最終的list結(jié)構(gòu)。
/**
* Flatten a Tree to a list using recursion(遞歸實(shí)現(xiàn))
* @param flatList flatList
* @return list
*/
static List<INodeDTO> flatten(List<INodeDTO> flatList){
return flatList.stream()
.filter(x -> x.getPid() == null)
.collect(Collectors.toList())
.stream()
.map(x->{return flatten(x,flatList);})
.flatMap(Collection::stream)
.distinct()
.collect(Collectors.toList());
}
/**
* recursion
* @param node root node
* @param flatList flatList
* @return list
*/
static List<INodeDTO> flatten(INodeDTO node, List<INodeDTO> flatList) {
List<INodeDTO> results = new ArrayList<>();
if(node != null){
// get rid of children & parent references
INodeDTO n = NodeDTO.builder()
.pid(node.getPid())
.id(node.getId())
.build();
results.add(n);
}
List<INodeDTO> children = node.getChildren();
for (INodeDTO child : children) {
if(child.getChildren() != null) {
// Recursive call - Keep flattening until no more children
List<INodeDTO> flatten = flatten(child, flatList);
results.addAll(flatten);
}
}
// stop or exit condition
return results;
}非遞歸實(shí)現(xiàn)
在非遞歸，即循環(huán)的實(shí)現(xiàn)中，我們要用到dequeue數(shù)據(jù)結(jié)構(gòu)。
deque表示一個雙端隊(duì)列，這意味著可以從隊(duì)列的兩端添加和刪除元素。 deque的不同之處在于添加和刪除條目的不受限制的特性。
在實(shí)現(xiàn)中，ArrayDeque將被用作LIFO(即后進(jìn)先出)數(shù)據(jù)結(jié)構(gòu)(即堆棧)。
/**
* Flatten a Tree to a list using a while Loop instead of recursion
* @param flatList flatList
* @return list
*/
static List<INodeDTO> flatten2(List<INodeDTO> flatList){
return flatList.stream()
.filter(x -> x.getPid() == null)
.collect(Collectors.toList())
.stream()
.map(TreeToMapUtils::flatten2)
.flatMap(Collection::stream)
.distinct()
.collect(Collectors.toList());
}
/**
* . Flatten using a Deque - Double ended Queue
*
**/
static List<INodeDTO> flatten2(INodeDTO node) {
if (node == null) {
return null;
}
List<INodeDTO> flatList = new ArrayList<>();
Deque<INodeDTO> q = new ArrayDeque<>();
//add the root
q.addLast(node);
//Keep looping until all nodes are traversed
while (!q.isEmpty()) {
INodeDTO n = q.removeLast();
flatList.add(NodeDTO.builder().id(n.getId()).pid(n.getPid()).build());
List<INodeDTO> children = n.getChildren();
if (children != null) {
for (INodeDTO child : children) {
q.addLast(child);
}
}
}
return flatList;
}實(shí)例
在實(shí)例中，我們主要用到list to map 中的輸出，看是否能用flatten函數(shù)還原結(jié)構(gòu)。
public static void main(String[] args) throws JsonProcessingException {
UseCase useCase = new UseCase();
List<INodeDTO> results = useCase.listBy("condtion1", "condtion2");
//convert json with style1 = {NodeDTO@1502} "NodeDTO(id=1, pid=null, children=null)"
ObjectMapper objectMapper = new ObjectMapper();
String json = objectMapper.writerWithDefaultPrettyPrinter().writeValueAsString(results);
System.out.println(json);
//flatten now
List<INodeDTO> flatten = TreeToMapUtils.flatten2(results);
System.out.println(flatten);
}輸出結(jié)果不但包含Tree形數(shù)據(jù)結(jié)構(gòu)，還獲取到了list數(shù)據(jù)，如下圖所示，至此，達(dá)到效果。
總結(jié)
至此，遞歸和非遞歸分別實(shí)現(xiàn)list to tree 和tree to list已完成，實(shí)現(xiàn)比較倉促，有很多細(xì)節(jié)處未處理好，希望看到的小伙伴及時指出，不勝感激。
到此這篇關(guān)于Java實(shí)現(xiàn)平鋪列表(List)互轉(zhuǎn)樹形(Tree)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)Java List轉(zhuǎn)樹形Tree結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Springcloud中的region和zone的使用實(shí)例
這篇文章主要介紹了Springcloud中的region和zone的使用實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-10-10
Java實(shí)現(xiàn)OJ多組測試數(shù)據(jù)的輸入方法
今天小編就為大家分享一篇Java實(shí)現(xiàn)OJ多組測試數(shù)據(jù)的輸入方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
Java存儲過程調(diào)用CallableStatement的方法
這篇文章主要介紹了Java存儲過程調(diào)用CallableStatement的方法，幫助大家更好的理解和學(xué)習(xí)Java，感興趣的朋友可以了解下2020-11-11
這篇文章主要介紹了Jenkins安裝以及郵件配置相關(guān)問題，并通過圖文給大家做了詳細(xì)講解步驟，需要的朋友參考下吧。2017-12-12
使用泛型的目的是利用Java編譯機(jī)制,在編譯過程中幫我們檢測代碼中不規(guī)范的有可能導(dǎo)致程序錯誤的代碼,下面這篇文章主要給大家介紹了關(guān)于Java泛型與通配符的相關(guān)資料,需要的朋友可以參考下2022-03-03
這篇文章主要介紹了自定義log4j日志文件命名規(guī)則說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
這篇文章主要介紹了JAVA用戶自定義事件監(jiān)聽實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-04-04
Java8使用LocalDate計(jì)算日期實(shí)例代碼解析
這篇文章主要介紹了Java8使用LocalDate計(jì)算實(shí)例代碼解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-04-04
java編程經(jīng)典案例之基于斐波那契數(shù)列解決兔子問題實(shí)例
這篇文章主要介紹了java編程經(jīng)典案例之基于斐波那契數(shù)列解決兔子問題,結(jié)合完整實(shí)例形式分析了斐波那契數(shù)列的原理及java解決兔子問題的相關(guān)操作技巧,需要的朋友可以參考下2017-10-10
Java微信小程序oss圖片上傳的實(shí)現(xiàn)方法
這篇文章主要介紹了Java微信小程序oss圖片上傳的實(shí)現(xiàn)方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12