树结构分页方案

背景

需要实现一个树结构的查询，分页，过滤功能。

难点

1.如果按照全数据分页，会出现一棵树在2个页上，出现断层。

2.过滤后，最好的体验是节点的上级节点需要展示。

方案思路

1.只对顶层节点进行分页。

2.递归的去过滤树节点。

实现

获取列表数据

此时树列表数据对应的是数据库的一行行记录，最小化粒度的获取到树的列表数据，方便后续的递归。

树转化

列表数据转化为树结构。

/**
     * 列表转树
     *
     * @param list     节点列表
     * @param parentId 根id
     * @return java.util.List<com.skuu.math.tree.page.Tree>
     * @author dcx
     * @date 2024/3/4 18:04
     **/
    public static List<Tree> listToTree(List<Tree> list, Long parentId) {
        Map<Long, Tree> idMap = new HashMap<>();
        List<Tree> rootData = new ArrayList<>();
        for (Tree item : list) {
            //1.遍历找到顶层节点
            if (item.getPid().equals(parentId)) {
                rootData.add(item);
            }
            //2.空间换时间，将tree缓存起来
            idMap.put(item.getId(), item);
        }
        for (Tree item : list) {
            Long tmpParentId = item.getPid();
            // 3.排除根节点
            if (tmpParentId.equals(parentId)) {
                continue;
            }
            //4.没有根节点的，不显示。
            Tree parent = idMap.get(tmpParentId);
            if (parent == null) {
                continue;
            }
            //5.如果该父节点没有child，初始化一个空的。
            if (parent.getChild() == null) {
                parent.setChild(new ArrayList<>());
            }
            //6.把循环到的节点，添加到父节点。
            parent.getChild().add(item);
        }
        return rootData;
    }

树过滤

使用递归的方式，对节点进行过滤。

过滤条件

/**
 * 树条件过滤
 *
 * @author dcx
 * @since 2024-03-05 09:47
 **/
@Data
public class TreeFilter {
    private String name;
    private Integer page;
    private Integer pageSize;
}

树过滤

/**
     * 树过滤
     * @param trees	 全部树
     * @param treeFilter	树过滤条件
     * @return void
     * @author dcx
     * @date 2024/3/5 09:52
     **/
    public void filterTree(List<Tree> trees, TreeFilter treeFilter) {
        bottomToUpRetain(trees, (tree) -> {
            //是否删除
            String name = treeFilter.getName();
            if (!StringUtils.isEmpty(name)) {
                boolean contains = tree.getName().contains(name);
                if (!contains){
                    return true;
                }
            }
            return false;
        });

    }


    /**
     * 传入一棵树，递归到子，从子到父过节点，只要存在符合条件的子节点，则保留从父到子的路径树，
     * 根据预留函数式接口，利用模板方法设计模式，过滤全量资产树
     * 因java8 collection只提供removeIf，无提供retainIf，故传参判断是否保留
     *
     * @param treeNodeModels   全量资产树
     * @param templateFunction 函数接口，封装模板方法设计模式，封装资产节点查询条件
     * @param isRemove         是否是要从树节点删除
     */
    private void filerAssetTree(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction, boolean isRemove) {
        treeNodeModels.removeIf(item -> {
            // 有子节点，进递归
            if (checkNotEmpty(item.getChild())) {
                filerAssetTree(item.getChild(), templateFunction, isRemove);
            }
            // 无子节点，判断当前节点是否符合条件，不符合删除
            if (checkEmpty(item.getChild())) {
                // 判断是否删除，为true的删除
                return isRemove == templateFunction.apply(item);
            }
            // 跳出递归，还存在符合条件的子节点，不删除
            return false;
        });
    }

    private boolean checkNotEmpty(List<Tree> list) {
        return list != null && !list.isEmpty();
    }

    private boolean checkEmpty(List<Tree> list) {
        return list == null || list.isEmpty();
    }

    /**
     * 自下而上，从子到父，过滤出符合条件的节点，保留完整树结构
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 资产节点查询条件
     */
    private void bottomToUpRetain(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction) {
        filerAssetTree(treeNodeModels, templateFunction, false);
    }

    /**
     * 自下而上，从子到父，删除掉符合条件的节点，留下来的节点，保留完整的树结构，从子到父
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 资产节点查询条件
     */
    private void bottomToUpRemove(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction) {
        filerAssetTree(treeNodeModels, templateFunction, true);
    }

    /**
     * 传入一棵树，由上到下过滤节点，过滤出符合条件的节点，只要不符合条件的节点，从树从删除该节点
     * 根据预留函数式接口，利用模板方法设计模式，过滤全量资产树
     * 因java8 collection只提供removeIf，无提供retainIf，故传参判断是否保留
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 函数接口，封装模板方法设计模式，封装资产节点查询条件
     * @param isRemove         是否是要从树节点删除
     */
    private void filterTopToDown(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction, boolean isRemove) {
        treeNodeModels.removeIf(item -> {
            // 判断当前节点是否符合条件，为true的删除
            if (templateFunction.apply(item)) {
                return isRemove == templateFunction.apply(item);
            }
            // 如果当前节点符合条件，并且存在子节点，则递归进入子节点继续遍历
            if (!item.getChild().isEmpty()) {
                filterTopToDown(item.getChild(), templateFunction, isRemove);
            }
            // 子节点符合条件，则保留
            return false;
        });
    }

    /**
     * 自上而下，从父到子，过滤出符合条件的节点
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 资产节点查询条件
     */
    private void topToDownRetain(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction) {
        filterTopToDown(treeNodeModels, templateFunction, false);
    }

    /**
     * 自上而下，从父到子，删除掉符合条件的节点
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 资产节点查询条件
     */
    private void topToDownRemove(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction) {
        filterTopToDown(treeNodeModels, templateFunction, true);
    }

树分页

 /**
     * 树分页
     * @param trees	
     * @param treeFilter	
     * @return java.util.List<com.skuu.math.tree.page.Tree>
     * @author dcx
     * @date 2024/3/5 10:09
     **/
    public List<Tree> page(List<Tree> trees, TreeFilter treeFilter) {
        Integer pageSize = treeFilter.getPageSize();
        List<List<Tree>> partition = Lists.partition(trees, pageSize);
        Integer page = treeFilter.getPage();
        return partition.get(page);
    }

使用

public static void main(String[] args) {
        TreeUtil treeUtil = new TreeUtil();
        //列表
        ArrayList<Tree> trees = Lists.newArrayList();
        Long parentId = 1L;
        //列表转树
        List<Tree> treeTree = treeUtil.listToTree(trees, parentId);
        //过滤条件
        TreeFilter treeFilter = new TreeFilter();
        //树过滤
        treeUtil.filterTree(treeTree,treeFilter);
        //树分页
        treeUtil.page(treeTree,treeFilter);
    }

全代码

package com.skuu.math.tree.page;

import com.google.common.collect.Lists;
import org.springframework.util.StringUtils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;

/**
 * @author dcx
 * @since 2024-03-04 17:54
 **/
public class TreeUtil {

    /**
     * 列表转树
     *
     * @param list     节点列表
     * @param parentId 根id
     * @return java.util.List<com.skuu.math.tree.page.Tree>
     * @author dcx
     * @date 2024/3/4 18:04
     **/
    public List<Tree> listToTree(List<Tree> list, Long parentId) {
        Map<Long, Tree> idMap = new HashMap<>();
        List<Tree> rootData = new ArrayList<>();
        for (Tree item : list) {
            //1.遍历找到顶层节点
            if (item.getPid().equals(parentId)) {
                rootData.add(item);
            }
            //2.空间换时间，将tree缓存起来
            idMap.put(item.getId(), item);
        }
        for (Tree item : list) {
            Long tmpParentId = item.getPid();
            // 3.排除根节点
            if (tmpParentId.equals(parentId)) {
                continue;
            }
            //4.没有根节点的，不显示。
            Tree parent = idMap.get(tmpParentId);
            if (parent == null) {
                continue;
            }
            //5.如果该父节点没有child，初始化一个空的。
            if (parent.getChild() == null) {
                parent.setChild(new ArrayList<>());
            }
            //6.把循环到的节点，添加到父节点。
            parent.getChild().add(item);
        }
        return rootData;
    }

    /**
     * 树过滤
     *
     * @param trees      全部树
     * @param treeFilter 树过滤条件
     * @return void
     * @author dcx
     * @date 2024/3/5 09:52
     **/
    public void filterTree(List<Tree> trees, TreeFilter treeFilter) {
        bottomToUpRetain(trees, (tree) -> {
            //是否删除
            String name = treeFilter.getName();
            if (!StringUtils.isEmpty(name)) {
                boolean contains = tree.getName().contains(name);
                if (!contains) {
                    return true;
                }
            }
            return false;
        });

    }


    /**
     * 传入一棵树，递归到子，从子到父过节点，只要存在符合条件的子节点，则保留从父到子的路径树，
     * 根据预留函数式接口，利用模板方法设计模式，过滤全量资产树
     * 因java8 collection只提供removeIf，无提供retainIf，故传参判断是否保留
     *
     * @param treeNodeModels   全量资产树
     * @param templateFunction 函数接口，封装模板方法设计模式，封装资产节点查询条件
     * @param isRemove         是否是要从树节点删除
     */
    private void filerAssetTree(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction, boolean isRemove) {
        treeNodeModels.removeIf(item -> {
            // 有子节点，进递归
            if (checkNotEmpty(item.getChild())) {
                filerAssetTree(item.getChild(), templateFunction, isRemove);
            }
            // 无子节点，判断当前节点是否符合条件，不符合删除
            if (checkEmpty(item.getChild())) {
                // 判断是否删除，为true的删除
                return isRemove == templateFunction.apply(item);
            }
            // 跳出递归，还存在符合条件的子节点，不删除
            return false;
        });
    }

    private boolean checkNotEmpty(List<Tree> list) {
        return list != null && !list.isEmpty();
    }

    private boolean checkEmpty(List<Tree> list) {
        return list == null || list.isEmpty();
    }

    /**
     * 自下而上，从子到父，过滤出符合条件的节点，保留完整树结构
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 资产节点查询条件
     */
    private void bottomToUpRetain(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction) {
        filerAssetTree(treeNodeModels, templateFunction, false);
    }

    /**
     * 自下而上，从子到父，删除掉符合条件的节点，留下来的节点，保留完整的树结构，从子到父
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 资产节点查询条件
     */
    private void bottomToUpRemove(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction) {
        filerAssetTree(treeNodeModels, templateFunction, true);
    }

    /**
     * 传入一棵树，由上到下过滤节点，过滤出符合条件的节点，只要不符合条件的节点，从树从删除该节点
     * 根据预留函数式接口，利用模板方法设计模式，过滤全量资产树
     * 因java8 collection只提供removeIf，无提供retainIf，故传参判断是否保留
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 函数接口，封装模板方法设计模式，封装资产节点查询条件
     * @param isRemove         是否是要从树节点删除
     */
    private void filterTopToDown(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction, boolean isRemove) {
        treeNodeModels.removeIf(item -> {
            // 判断当前节点是否符合条件，为true的删除
            if (templateFunction.apply(item)) {
                return isRemove == templateFunction.apply(item);
            }
            // 如果当前节点符合条件，并且存在子节点，则递归进入子节点继续遍历
            if (!item.getChild().isEmpty()) {
                filterTopToDown(item.getChild(), templateFunction, isRemove);
            }
            // 子节点符合条件，则保留
            return false;
        });
    }

    /**
     * 自上而下，从父到子，过滤出符合条件的节点
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 资产节点查询条件
     */
    private void topToDownRetain(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction) {
        filterTopToDown(treeNodeModels, templateFunction, false);
    }

    /**
     * 自上而下，从父到子，删除掉符合条件的节点
     *
     * @param treeNodeModels   资产树
     * @param templateFunction 资产节点查询条件
     */
    private void topToDownRemove(List<Tree> treeNodeModels, Function<Tree, Boolean> templateFunction) {
        filterTopToDown(treeNodeModels, templateFunction, true);
    }

    /**
     * 树分页
     * @param trees
     * @param treeFilter
     * @return java.util.List<com.skuu.math.tree.page.Tree>
     * @author dcx
     * @date 2024/3/5 10:09
     **/
    public List<Tree> page(List<Tree> trees, TreeFilter treeFilter) {
        Integer pageSize = treeFilter.getPageSize();
        List<List<Tree>> partition = Lists.partition(trees, pageSize);
        Integer page = treeFilter.getPage();
        return partition.get(page);
    }

    public static void main(String[] args) {
        TreeUtil treeUtil = new TreeUtil();
        //列表
        ArrayList<Tree> trees = Lists.newArrayList();
        Long parentId = 1L;
        //列表转树
        List<Tree> treeTree = treeUtil.listToTree(trees, parentId);
        //过滤条件
        TreeFilter treeFilter = new TreeFilter();
        //树过滤
        treeUtil.filterTree(treeTree,treeFilter);
        //树分页
        treeUtil.page(treeTree,treeFilter);
    }

}