作業中常用的關于樹的遞回演算法

遞回介紹

• 遞回演算法在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法，眾所周知的資料結構的快速排序演算法就是基于遞回實作的，遞回這是一種很重要的演算法思想，在C語言，Java中普遍應用，大學期間參加演算法競賽遞回演算法在所難免，
• 根據我個人的理解，一個遞回程式就是方法自身呼叫自身，一個遞回函式中主要包含三個部分，第一遞回出口，第二執行的邏輯代碼，第三子問題遞回執行，

案例介紹

遞回獲取選單樹

第一種: stream流實作(推薦)

/**
     * stream流獲取選單樹
     * @param parentId
     * @param list
     * @return
     */
    public List<Menu> selectTree(Long parentId,List<Menu> list) {
        List<Menu> leve1Menus = list.stream().filter(treeEntity ->
            treeEntity.getPid().equals(parentId)
        ).map((menus) -> {
            menus.setChildren(getChildNode(menus,list));
            return menus;
        }).collect(Collectors.toList());
        return leve1Menus;
    }
    /**
     * 遞回子節點
     * @param root   當前單個選單
     * @param allListTree   表中的所有選單集合
     * @return
     */
    private List<Menu> getChildNode(Menu root, List<Menu> allListTree){
        List<Menu> ChildNodeList = allListTree.stream().filter((treeEntity) -> {
            return treeEntity.getPid().equals(root.getId());
        }).map((treeEntity)->{
            treeEntity.setChildren(getChildNode(treeEntity,allListTree));
            return treeEntity;
        }).collect(Collectors.toList());
        return ChildNodeList;
    }

第二種: 普通遞回實作

/**
     * 遞回回傳選單樹
     * @param list
     * @return
     */
    public static List<Menu> getListMenu(Long parentId,List<Menu> list) {

        List menuListTree = new ArrayList<>();
        for (Menu menu : list) {
            if (menu.getPid() == parentId) { //如果是根節點(存在多個根)
                List<Menu> children = getListMenu(menu.getId(), list);
                if (!children.isEmpty()){
                    menu.setChildren(children);
                }
                menuListTree.add(menu);
            }
        }
        return menuListTree;
    }

第三種 :

@Override
    @Transactional(readOnly = true)
    public List<TreeNodeV2> queryTreeNode() {
        //根節點集合
        List<TreeNodeV2> tops = new ArrayList<>();
        //非跟節點集合
        List<TreeNodeV2> subs = new ArrayList<>();
        //所有節點集合
        List<TreeNodeV2> all = new ArrayList<>();
        List<TbContentCategory> categories = contentCategoryMapper.selectAll();
        //獲取根節點
        for(TbContentCategory category : categories) {
            TreeNodeV2 node = new TreeNodeV2(category.getId(),category.getParentId(), category.getName(), category.getIsParent()==1?false:true, new ArrayList<>());
            if (category.getParentId() == 0) {
                tops.add(node);
            } else {
                subs.add(node);
            }
            all.add(node);
        }
        //遍歷所有的非根節點
        for (TreeNodeV2 node : subs) {
            //根據父節點id在all找當前節點的父節點
            /*
            for (TreeNodeV2 n : all) {
                if (n.getId() == node.getParentId()) {
                    n就是parent
                }
            }
             */
            //node的父節點
            TreeNodeV2 parent = all.stream().filter(n -> node.getParentId().equals(n.getId())).findFirst().orElse(null);
            //將當前節點存放到parent的children中
            if (parent != null) {
                parent.getChildren().add(node);
            }

        }

        return tops;
    }

遍歷當前節點到根節點的路徑資訊

private static List<Menu> pathList = new ArrayList<>();
    /**
     * 組裝當前節點到根節點的路徑資訊保存到pathList
     * @param menu 當前節點編號
     * @param parentId 根節點編號
     * @param list 所有節點資料
     */
    public void assumbleParentMenu (Menu menu,Long parentId,List<Menu> list) {
        if(menu.getId().equals(parentId)) {
            return;
        }
        pathList.add(menu);
        Menu menu1 = list.stream().filter(item -> item.getId().equals(menu.getPid())).findFirst().orElse(null);
        assumbleParentMenu(menu1,parentId,list);
    }

遞回獲取當前節點（不包含自身）的所有孩子節點

private static List<Long> menuIds = new ArrayList<>();
    /**
     * 獲取當前節點（不包含自身）的所有孩子節點的物理主鍵
     * @param menu 當前節點
     * @param list 所有節點資料
     */
    public static void getMenuChildren(Menu menu,List<Menu> list) {
        List<Menu> collect = list.stream().filter(item -> item.getPid().equals(menu.getId())).collect(Collectors.toList());
        if (!collect.isEmpty()) {
            menuIds.addAll(collect.stream().map(Menu::getId).collect(Collectors.toList()));
            for(Menu temp : collect) {
                getMenuChildren(temp,list);
            }
        } else {
            return;
        }
    }

踩坑記錄–不斷補充

Java 堆疊溢位

• 首先查看資料庫的資料是否存在不斷相互呼叫的，因為JVM中Java的執行的壓堆疊執行，這樣不斷壓堆疊，就會導致最后的堆疊溢位，