Java實(shí)現(xiàn)平鋪列表(List)互轉(zhuǎn)樹形(Tree)結(jié)構(gòu)

更新時間：2022年08月05日 09:48:29 作者：青Cheng序員石頭的個人資料頭像青Cheng序員石頭

本文主要介紹了Java實(shí)現(xiàn)平鋪列表(List)互轉(zhuǎn)樹形(Tree)結(jié)構(gòu)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

很多時候為滿足前后端交互的數(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)人工肉眼檢驗，達(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表示一個雙端隊列，這意味著可以從隊列的兩端添加和刪除元素。 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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: