欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

使用Java實(shí)現(xiàn)通用樹形結(jié)構(gòu)構(gòu)建工具類

 更新時(shí)間：2025年03月28日 15:23:05   作者：少年醬105974  
這篇文章主要為大家詳細(xì)介紹了如何使用Java實(shí)現(xiàn)通用樹形結(jié)構(gòu)構(gòu)建工具類,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下

完整代碼

package com.pig4cloud.pigx.common.core.util.tree;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 通用樹結(jié)構(gòu)構(gòu)建工具類
 *
 * <p>重要說明：
 * <ol>
 *   <li>所有節(jié)點(diǎn)必須具有唯一ID</li>
 *   <li>父節(jié)點(diǎn)不存在時(shí)自動(dòng)成為根節(jié)點(diǎn)</li>
 *   <li>節(jié)點(diǎn)排序依賴comparator實(shí)現(xiàn)</li>
 *   <li>支持循環(huán)依賴檢測(cè)和錯(cuò)誤路徑提示</li>
 * </ol>
 *
 * @param <T> 原始數(shù)據(jù)類型
 * @param <K> 節(jié)點(diǎn)ID類型（建議使用包裝類型）
 */
public class TreeBuilder<T, K> {
    private final Function<T, K> idGetter;
    private final Function<T, K> parentIdGetter;
    private final ChildSetter<T> childSetter;
    private final Comparator<T> comparator;

    /**
     * 構(gòu)造方法
     */
    public TreeBuilder(Function<T, K> idGetter,
                       Function<T, K> parentIdGetter,
                       ChildSetter<T> childSetter,
                       Comparator<T> comparator) {

        this.idGetter = Objects.requireNonNull(idGetter, "ID獲取器不能為null");
        this.parentIdGetter = Objects.requireNonNull(parentIdGetter, "父ID獲取器不能為null");
        this.childSetter = Objects.requireNonNull(childSetter, "子節(jié)點(diǎn)設(shè)置器不能為null");
        this.comparator = Objects.requireNonNull(comparator, "排序比較器不能為null");
    }

    /**
     * 構(gòu)建完整樹結(jié)構(gòu)
     */
    public List<T> buildTree(List<T> items) {
        Objects.requireNonNull(items, "節(jié)點(diǎn)列表不能為null");
        if (items.isEmpty()) return Collections.emptyList();

        // 1. 構(gòu)建數(shù)據(jù)索引
        Map<K, T> nodeMap = createNodeMap(items);
        Map<K, List<T>> parentChildrenMap = items.stream()
                .collect(Collectors.groupingBy(
                        parentIdGetter,
                        LinkedHashMap::new,  // 保持插入順序
                        Collectors.toList()
                ));

        // 2. 循環(huán)依賴檢測(cè)
        detectCyclicDependencies(items, nodeMap);

        // 3. 構(gòu)建樹結(jié)構(gòu)
        nodeMap.forEach((nodeId, node) -> {
            List<T> children = parentChildrenMap.getOrDefault(nodeId, Collections.emptyList())
                    .stream()
                    .sorted(comparator)
                    .collect(Collectors.toList());

            childSetter.setChildren(node, Collections.unmodifiableList(children));
        });

        // 4. 獲取根節(jié)點(diǎn)（parentId為null或不存在于nodeMap）
        return items.stream()
                .filter(item -> isRootNode(item, nodeMap))
                .sorted(comparator)
                .collect(Collectors.toList());

    }

    /**
     * 判斷是否為根節(jié)點(diǎn)（抽離方法提升可讀性）
     */
    private boolean isRootNode(T item, Map<K, T> nodeMap) {
        K parentId = parentIdGetter.apply(item);
        return parentId == null || !nodeMap.containsKey(parentId);
    }

    /**
     * 構(gòu)建搜索結(jié)果樹
     */
    public List<T> buildSearchTree(List<T> allItems, Set<K> matchIds) {
        Objects.requireNonNull(allItems, "節(jié)點(diǎn)列表不能為null");
        Objects.requireNonNull(matchIds, "匹配ID集合不能為null");

        Set<K> relatedIds = findRelatedIds(allItems, matchIds);
        List<T> relatedItems = allItems.stream()
                .filter(item -> relatedIds.contains(idGetter.apply(item)))
                .collect(Collectors.toList());

        return buildTree(relatedItems);
    }

    /**
     * 創(chuàng)建節(jié)點(diǎn)ID映射表（含重復(fù)檢測(cè)）
     */
    private Map<K, T> createNodeMap(List<T> items) {
        Map<K, T> map = new LinkedHashMap<>(items.size());
        for (T item : items) {
            K id = idGetter.apply(item);
            if (map.containsKey(id)) {
                throw new IllegalArgumentException(String.format(
                        "發(fā)現(xiàn)重復(fù)節(jié)點(diǎn)ID: %s (沖突對(duì)象1: %s, 沖突對(duì)象2: %s)",
                        id, map.get(id), item));
            }
            map.put(id, item);
        }
        return map;
    }

    /**
     * 循環(huán)依賴檢測(cè)核心邏輯
     */
    private void detectCyclicDependencies(List<T> items, Map<K, T> nodeMap) {
        Set<K> verifiedNodes = new HashSet<>();
        Map<K, K> idToParentMap = items.stream()
                .collect(Collectors.toMap(idGetter, parentIdGetter));

        for (T item : items) {
            K currentId = idGetter.apply(item);
            if (verifiedNodes.contains(currentId)) continue;

            Set<K> path = new LinkedHashSet<>();
            K tracingId = currentId;

            while (tracingId != null) {
                if (!path.add(tracingId)) {
                    throw new CyclicDependencyException(buildCyclePath(path, tracingId));
                }

                // 短路已驗(yàn)證節(jié)點(diǎn)
                if (verifiedNodes.contains(tracingId)) break;

                K parentId = idToParentMap.get(tracingId);
                if (parentId == null) break;

                // 直接循環(huán)檢測(cè)
                if (parentId.equals(tracingId)) {
                    throw new CyclicDependencyException("直接循環(huán)依賴: " + tracingId);
                }

                tracingId = parentId;
            }
            verifiedNodes.addAll(path);
        }
    }

    /**
     * 構(gòu)造循環(huán)路徑描述
     */
    private String buildCyclePath(Set<K> path, K duplicateId) {
        List<K> pathList = new ArrayList<>(path);
        int index = pathList.indexOf(duplicateId);
        List<K> cycle = pathList.subList(index, pathList.size());
        return "檢測(cè)到循環(huán)依賴鏈: " + cycle.stream()
                .map(Object::toString)
                .collect(Collectors.joining(" → "));
    }

    /**
     * 查找相關(guān)ID集合（匹配節(jié)點(diǎn)+路徑節(jié)點(diǎn)）
     */
    private Set<K> findRelatedIds(List<T> allItems, Set<K> matchIds) {
        Map<K, K> idToParentMap = allItems.stream()
                .collect(Collectors.toMap(idGetter, parentIdGetter));

        return matchIds.stream()
                .flatMap(id -> traceAncestors(id, idToParentMap).stream())
                .collect(Collectors.toSet());
    }

    /**
     * 追溯父節(jié)點(diǎn)鏈
     */
    private Set<K> traceAncestors(K startId, Map<K, K> idToParentMap) {
        Set<K> ancestors = new LinkedHashSet<>();
        K currentId = startId;

        while (currentId != null && ancestors.add(currentId)) {
            currentId = idToParentMap.get(currentId);
        }
        return ancestors;
    }

    /**
     * 自定義循環(huán)依賴異常
     */
    public static class CyclicDependencyException extends RuntimeException {
        public CyclicDependencyException(String message) {
            super(message);
        }
    }

    /**
     * 子節(jié)點(diǎn)設(shè)置接口
     */
    @FunctionalInterface
    public interface ChildSetter<T> {
        void setChildren(T parent, List<T> children);
    }

    /* 快捷構(gòu)造方法 */

    public static <T, K> TreeBuilder<T, K> create(
            Function<T, K> idGetter,
            Function<T, K> parentIdGetter,
            ChildSetter<T> childSetter,
            Comparator<T> comparator) {
        return new TreeBuilder<>(idGetter, parentIdGetter, childSetter, comparator);
    }

    public static <T, K extends Comparable<? super K>> TreeBuilder<T, K> createWithNaturalOrder(
            Function<T, K> idGetter,
            Function<T, K> parentIdGetter,
            ChildSetter<T> childSetter) {
        return new TreeBuilder<>(
                idGetter,
                parentIdGetter,
                childSetter,
                Comparator.comparing(idGetter, Comparator.nullsLast(Comparator.naturalOrder()))
        );
    }
}

一、設(shè)計(jì)思想與核心功能

本工具類采用泛型設(shè)計(jì)，可處理任意類型的節(jié)點(diǎn)數(shù)據(jù)，具備以下核心能力：

  • 多類型支持：通過泛型參數(shù)T（數(shù)據(jù)類型）和K（ID類型），支持各種業(yè)務(wù)場(chǎng)景
  • 自動(dòng)化構(gòu)建：自動(dòng)識(shí)別根節(jié)點(diǎn)、建立父子關(guān)系
  • 安全防護(hù)：內(nèi)置循環(huán)依賴檢測(cè)、重復(fù)ID校驗(yàn)
  • 靈活擴(kuò)展：支持自定義排序規(guī)則、子節(jié)點(diǎn)設(shè)置方式
  • 高效查詢：提供子樹構(gòu)建功能，適用于搜索場(chǎng)景

二、核心實(shí)現(xiàn)原理

1. 數(shù)據(jù)結(jié)構(gòu)準(zhǔn)備階段

Map<K, T> nodeMap = createNodeMap(items);
Map<K, List<T>> parentChildrenMap = items.stream()
        .collect(Collectors.groupingBy(...));
  • 節(jié)點(diǎn)映射表：通過ID快速定位節(jié)點(diǎn)，驗(yàn)證ID唯一性
  • 父子關(guān)系映射：預(yù)先生成父節(jié)點(diǎn)→子節(jié)點(diǎn)列表的關(guān)系字典

2. 循環(huán)依賴檢測(cè)算法

采用路徑追蹤法，時(shí)間復(fù)雜度O(n)：

Set<K> path = new LinkedHashSet<>();
while (tracingId != null) {
    if (!path.add(tracingId)) {
        throw new CyclicDependencyException(...);
    }
    // 追溯父節(jié)點(diǎn)鏈
}

可檢測(cè)兩種異常情況：

  • 直接循環(huán)：父節(jié)點(diǎn)指向自身
  • 間接循環(huán)：A→B→C→A型循環(huán)鏈

3. 樹形結(jié)構(gòu)構(gòu)建

采用兩階段構(gòu)建模式：

  • 初始化所有節(jié)點(diǎn)的子節(jié)點(diǎn)列表
  • 篩選根節(jié)點(diǎn)（父ID不存在或?qū)?yīng)節(jié)點(diǎn)缺失）

4. 搜索子樹生成

通過ID回溯算法構(gòu)建有效路徑：

Set<K> traceAncestors(K startId) {
    // 向上追溯所有祖先節(jié)點(diǎn)
}

確保搜索結(jié)果的完整樹形結(jié)構(gòu)

三、關(guān)鍵代碼詳解

1. 節(jié)點(diǎn)排序?qū)崿F(xiàn)

childSetter.setChildren(node, 
    children.stream()
        .sorted(comparator)
        .collect(Collectors.toList())
);

支持兩種排序方式：

  • 自然排序（createWithNaturalOrder）
  • 自定義比較器（推薦業(yè)務(wù)相關(guān)排序）

2. 異常處理機(jī)制

自定義異常類型增強(qiáng)可讀性：

public class CyclicDependencyException extends RuntimeException {
    // 攜帶具體循環(huán)路徑信息
}

提供明確的錯(cuò)誤定位信息：

檢測(cè)到循環(huán)依賴鏈: 1001 → 1002 → 1003 → 1001

3. 函數(shù)式接口應(yīng)用

@FunctionalInterface
public interface ChildSetter<T> {
    void setChildren(T parent, List<T> children);
}

使用時(shí)可通過Lambda表達(dá)式實(shí)現(xiàn)：

TreeBuilder<Department, Long> builder = 
    new TreeBuilder<>(..., (parent, children) -> parent.setChildDepts(children));

四、使用示例

基礎(chǔ)用法

List<Menu> menus = getFromDB();

TreeBuilder<Menu, Integer> builder = TreeBuilder.create(
    Menu::getId,
    Menu::getParentId,
    (parent, children) -> parent.setChildren(children),
    Comparator.comparing(Menu::getSortOrder)
);

List<Menu> tree = builder.buildTree(menus);

搜索場(chǎng)景應(yīng)用

Set<Integer> matchIds = searchService.findIds("關(guān)鍵");
List<Menu> resultTree = builder.buildSearchTree(allMenus, matchIds);

五、注意事項(xiàng)

  • ID規(guī)范：
    • 必須實(shí)現(xiàn)有效的hashCode()和equals()
    • 推薦使用包裝類型（避免Long與long的匹配問題）
  • 對(duì)象狀態(tài)：
    • 原始數(shù)據(jù)對(duì)象應(yīng)支持子節(jié)點(diǎn)集合設(shè)置
    • 建議使用不可變集合防止意外修改
  • 特殊場(chǎng)景：
    • 空集合處理返回emptyList()
    • 允許游離節(jié)點(diǎn)（父節(jié)點(diǎn)不存在時(shí)成為根節(jié)點(diǎn)）
  • 性能考量：
    • 萬級(jí)數(shù)據(jù)量建議分批處理
    • 頻繁構(gòu)建時(shí)可緩存nodeMap

以上就是使用Java實(shí)現(xiàn)通用樹形結(jié)構(gòu)構(gòu)建工具類的詳細(xì)內(nèi)容，更多關(guān)于Java構(gòu)建樹形結(jié)構(gòu)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

最新評(píng)論