Java實現平鋪列表(List)互轉樹形(Tree)結構

2022-08-05 14:03:13

需求

我們從基礎設施層獲取了一個列表資料，列表其中的物件結構如下，注意約束條件如果沒有pid，預設為null。

@Getter
@Setter
@ToString
@Builder
public class NodeEntity {

    /**
     * id
     */
    private Long id;

    /**
     * 父id
     */
    private Long pid;
}

現在我們要將List<NodeEntity> 資料，按照屬性pid進行Tree型層級封裝，並且支援多層級封裝。一般很容易想到遞迴的實現方法，接下來這篇文章使用一套通用的解決辦法，非遞迴實現結構轉換。

實踐List to Tree

遞迴實現

首先定義通用的Tree形資料介面。

public interface INodeDTO {

    /**
     * id
     * @return id
     */
    public Long getId();

    /**
     * pid
     * @return  pid
     */
    public Long getPid();


    /**
     * 獲取Children
     * @return  Children
     */
    public List<INodeDTO> getChildren();

    /**
     * 設定children
     * @param children  children
     */
    public void setChildren(List<INodeDTO> children);

}

每個方法介面有詳細的註釋，無需多說。然後提供通用的轉換Function。

/**
     * 非遞迴實現平鋪資料轉成Tree型結構
     */
    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());

我們利用物件參照，淺拷貝的原理，通過迴圈查詢來組裝層級，最後根據pid==null的資料一定是Tree型第一層的資料的條件進行過濾，篩選出第一層的資料組合成新的列表，達到目的。

非遞迴實現

//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;
}

遞迴的實現先獲取所有根節點，方法builTree總結根節點來建立一個樹結構，buildChilTree為節點構建一個輔助樹，並拼接當前樹，遞迴呼叫buildChilTree來不斷開啟當前樹的分支和葉子，直到沒有找到新的子樹, 完成遞迴，得到樹結構。

遞迴最大的問題可能堆疊太深，容易造成溢位，使用需要謹慎，而且從程式碼簡潔度來說，肯定是使用了非遞迴的方式更好。

遞迴程式碼還能進一步優化，比如改成尾遞迴的方式，有興趣的小夥伴可以嘗試一下。

範例

範例只測試非遞迴實現方法。

那具體怎麼使用呢？首先我們通過implements介面INodeDTO,實現我們自己的業務DTO。

@Getter
@Setter
@ToString
@Builder
public class NodeDTO implements INodeDTO {

    private Long id;

    private Long pid;

    List<INodeDTO> children;
}

然後在我們Service層組裝業務邏輯，這裡提供一個listBy的條件查詢介面，從基礎設施層按照條件撈出List<NodeEntity>，期望轉成內部包含層級關係的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方法進行測試。

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);
    }

執行後輸出結果如下，經人工肉眼檢驗，達到Tree型層級結構。

實踐Tree to List

上面講到了平鋪列表（List）轉樹形（Tree）結構，一般來說對於足夠後端資料轉成前端想要的結構了。但都支援了正向轉換，那麼反向轉換，即樹形（Tree）結構如何轉平鋪列表（List）呢？

遞迴實現

遞迴實現，分為兩個函數，List<INodeDTO> flatten(List<INodeDTO> flatList) 接受外部呼叫，傳入待轉換的Tree形結構。第一步便是收集所有的根節點，然後將所有的根節點傳入到遞迴函數List<INodeDTO> flatten(INodeDTO node, List<INodeDTO> flatList中深度遍歷，最後彙總再使用distinct做去重處理得到最終的list結構。

/**
 * Flatten a Tree to a list using recursion(遞迴實現)
 * @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;
}

非遞迴實現

在非遞迴，即迴圈的實現中，我們要用到dequeue資料結構。

deque表示一個雙端佇列，這意味著可以從佇列的兩端新增和刪除元素。 deque的不同之處在於新增和刪除條目的不受限制的特性。

在實現中，ArrayDeque將被用作LIFO(即後進先出)資料結構(即堆疊)。

/**
 * 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;
}

範例

在範例中，我們主要用到list to map 中的輸出，看是否能用flatten函數還原結構。

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);

}

輸出結果不但包含Tree形資料結構，還獲取到了list資料，如下圖所示，至此，達到效果。