Java實作建構樹狀菜單欄

文章目錄

• 一. 問題背景
• 二. 解決方案
• • 2.1 核心算法
  • • 2.1.1 用動态數組建構樹
    • 2.1.2 用隊列建構樹
  • 2.2 核心思路

一. 問題背景

在公司做項目遇到一個需求是要傳回一顆樹狀菜單欄的資料結構給前端。效果類似如下：

二. 解決方案

這裡先直接給出核心算法的代碼，有興趣研究的可以前往gitee頁面下載下傳，搭建該項目的所有資源（包括源碼、sql表結構、表資料都在項目裡面）都在裡面，部署方法可參考裡面的readme.md檔案

2.1 核心算法

這裡有2種方式，其實都差不多。一種是采用 動态數組 ，一種是采用 隊列層次周遊 。直接給出核心代碼，後面再給出思路圖

2.1.1 用動态數組建構樹

/**
         * 1. 建構一個map，存儲每個節點的孩子們
         * 2. 建構一個map，根據key可以擷取到這個節點
         * 3. 根據傳進來的字典定義名擷取那個節點，用動态數組建構樹
         */

        long startTime = System.currentTimeMillis();

        if (parentKey == null || parentKey.trim().length() == 0) {
            parentKey = PARENT_KEY;
        }

        // 建構一個map，存儲每個節點的孩子節點
        Map<Integer, List<DictDefine>> parentIdChildrenMap = new HashMap<>();
        // 建構一個map，根據key可以擷取到這個節點
        Map<String, DictDefine> defineNameDictDefineMap = new HashMap<>();
        for (DictDefine dictDefine : dictDefines) {
            Integer parentId = dictDefine.getParentId();
            List<DictDefine> dictDefineList = parentIdChildrenMap.get(parentId);
            if (dictDefineList == null) {
                dictDefineList = new ArrayList<>();
            }
            dictDefineList.add(dictDefine);
            parentIdChildrenMap.put(parentId, dictDefineList);
            defineNameDictDefineMap.put(dictDefine.getDefineName(), dictDefine);
        }

        // 根據傳進來的字典定義名擷取那個節點，用動态數組建構樹
        DictDefine rootDictDefine = defineNameDictDefineMap.get(parentKey);

        if (rootDictDefine == null) {
            return new ArrayList<DictDefine>();
        }

        //用動态數組list建構樹
        List<DictDefine> list = new ArrayList<>();
        list.add(rootDictDefine);

        int index = 0;
        while (!list.isEmpty() && index < list.size()) {
            DictDefine dictDefine = list.get(index);
            if (dictDefine == null) {
                continue;
            }
            List<DictDefine> childrenList = parentIdChildrenMap.get(dictDefine.getId());
            if (childrenList != null) {
                dictDefine.setChildren(childrenList);
                list.addAll(childrenList);
            }

            index++;
        }

        ArrayList<DictDefine> result = new ArrayList<>();
        result.add(rootDictDefine);

        long endTime = System.currentTimeMillis();

        log.info("It takes {}ms to deal it.", endTime-startTime);

        return result;
    }
           

2.1.2 用隊列建構樹

/**
     * 使用隊列建構樹
     * @param dictDefines
     * @param parentKey
     * @return
     */
    public static List<DictDefine> buildTreeByLinkedList(List<DictDefine> dictDefines,
                                                        String parentKey) {

        /**
         * 1. 建構一個map，存儲每個節點的孩子們
         * 2. 建構一個map，根據key可以擷取到這個節點
         * 3. 根據傳進來的字典定義名擷取那個節點，用隊列建構樹
         */

        long startTime = System.currentTimeMillis();

        if (parentKey == null || parentKey.trim().length() == 0) {
            parentKey = PARENT_KEY;
        }

        // 建構一個map，存儲每個節點的孩子節點
        Map<Integer, List<DictDefine>> parentIdChildrenMap = new HashMap<>();
        // 建構一個map，根據key可以擷取到這個節點
        Map<String, DictDefine> defineNameDictDefineMap = new HashMap<>();
        for (DictDefine dictDefine : dictDefines) {
            Integer parentId = dictDefine.getParentId();
            List<DictDefine> dictDefineList = parentIdChildrenMap.get(parentId);
            if (dictDefineList == null) {
                dictDefineList = new ArrayList<>();
            }
            dictDefineList.add(dictDefine);
            parentIdChildrenMap.put(parentId, dictDefineList);
            defineNameDictDefineMap.put(dictDefine.getDefineName(), dictDefine);
        }

        // 根據傳進來的字典定義名擷取那個節點，用動态數組建構樹
        DictDefine rootDictDefine = defineNameDictDefineMap.get(parentKey);

        if (rootDictDefine == null) {
            return new ArrayList<DictDefine>();
        }

        //用動态數組list建構樹
        Queue<DictDefine> queue = new LinkedList<>();
        queue.offer(rootDictDefine);

        while (!queue.isEmpty() ) {
            DictDefine dictDefine = queue.poll();
            if (dictDefine == null) {
                continue;
            }
            List<DictDefine> childrenList = parentIdChildrenMap.get(dictDefine.getId());
            if (childrenList != null) {
                dictDefine.setChildren(childrenList);
                queue.addAll(childrenList);
            }

        }

        ArrayList<DictDefine> result = new ArrayList<>();
        result.add(rootDictDefine);

        long endTime = System.currentTimeMillis();

        log.info("It takes {}ms to deal it.", endTime-startTime);

        return result;
    }
           

2.2 核心思路

核心思路如上，不管是采用動态數組，還是隊列，其實都是在進行層次周遊，有興趣可以去看看BFS層次周遊算法