掘金后端 ( ) • 2024-05-14 15:36

SpringBoot 业务开发中的算法应用：广度优先搜索封装标签树中每层节点数据集合

前言

最近在工作中，有这样一个需求：存在标签这么一个概念，标签可以打给用户，它们之间是多对多的关系。现在需要在编辑用户的时候，查询出所有标签，并且要标记哪些标签是已经打给当前用户的，还需要封装每个标签的全路径信息，在勾选某个标签时，会进行展示。

因为标签是存在层级结构的，例如一级二级三级标签，所以只需要封装为一个树结构即可，页面会使用一些三方的tree组件来渲染。但最近页面改版了，现在需要将每一级的标签数据，分别封装为一个List集合，页面会将三级标签都渲染出来，并根据一定的规则展示不同的标签数据。

总结一下：就是需要将标签数据查询出来封装为树形结构，并且需要封装全路径信息。然后，需要将树结构中的每一级的数据，分别封装为List集合。

完成这个需求主要分为两步：

递归+回溯 封装标签树，递归过程中使用回溯算法封装标签的全路径信息。
将封装好的标签树进行二次处理，通过广度优先搜索来封装每一层的节点数据。

准备工作

表设计

这里将业务中的表进行了简化

用户表：

标签表：

用户标签关联表：

上面的表设计也很好理解：

标签表有一个字段parentId，用来记录当前标签的父级标签ID，根标签的父级标签ID默认为0。
用户和标签的关联关系，使用了一个中间表t_user_tag来维护。

代码

项目依赖为 SpringBoot v2.6.13，引入了mybatis-plus、lombok等依赖。

如下，生成了每个表对应的entity、mapper、service

同时还提供一个标签Vo，用来封装处理之后的标签数据：

@Data
public class TagVo {
    /**
     * 标签id
     */
    private Integer id;
    /**
     * 标签名称
     */
    private String name;
    /**
     * 子标签集合
     */
    private List<TagVo> subTags;
    /**
     * 当前标签是否被绑定给用户
     */
    private boolean checked = false;
    /**
     * 当前节点层级
     */
    private Integer level;
    /**
     * 当前标签的全路径信息
     */
    private List<String> titles;
}

代码实现

首先在TagService中定义一个方法list，返回值类型为List<List<TagVo>>，因为需求最后是要将每层的数据分别封装为一个集合，所以这里返回了List集合。

public interface TagService extends IService<TagEntity> {
    List<List<TagVo>> list(Integer userId);
}

实现类重写该方法

@Service
public class TagServiceImpl extends ServiceImpl<TagMapper, TagEntity> implements TagService {
    @Override
    public List<List<TagVo>> list(Integer userId) {
        return null;
    }
}

递归+回溯封装树形数据

我们首先通过递归，封装出树形结构的数据。递归的过程中，应用到了回溯算法的思想，封装了每个标签的全路径数据。

同时对于判断当前标签是否绑定时，提前封装了一个Set集合，避免了每次递归都要进行的数据库查询。

关于 递归+回溯封装树形数据 的详细介绍，感兴趣的朋友可以点击这里参考之前的文章，在此就不赘述。

@Service
public class TagServiceImpl extends ServiceImpl<TagMapper, TagEntity> implements TagService {

    @Autowired
    private UserTagService userTagService;

    @Override
    public List<List<TagVo>> list(Integer userId) {
        //查询所有标签数据
        List<TagEntity> list = list();

        //查询用户已绑定的所有标签id
        List<Integer> tagIdList = userTagService.list(new QueryWrapper<UserTagEntity>().eq("user_id", userId)).stream().map(ut -> ut.getTagId()).collect(Collectors.toList());

        //递归封装树形结构
        List<TagVo> vos = getSubTags(list, 0, new HashSet<>(tagIdList), new ArrayList<>());

        return null;
    }

    /**
     * 封装标签树形数据
     *
     * @param list     标签数据集合
     * @param parentId 本次递归中过滤中所使用的父标签ID
     * @param tagIdSet 当前用户已绑定的所有标签集合
     * @param titles   用于封装当前标签的全路径数据
     * @return
     */
    private List<TagVo> getSubTags(List<TagEntity> list, Integer parentId, Set<Integer> tagIdSet, List<String> titles) {
        return list.stream()
                .filter(tag -> tag.getParentId().equals(parentId))
                .map(tag -> {
                    TagVo vo = new TagVo();
                    //复制属性值
                    BeanUtils.copyProperties(tag, vo);
                    //设置当前标签是否已与用户绑定
                    vo.setChecked(tagIdSet.contains(tag.getId()));
                    //封装子标签及全标题信息
                    titles.add(tag.getName());
                    //记录上一步中 添加到集合中的元素下标：之后要根据这个下标做回溯操作
                    int index = titles.size() - 1;
                    //封装当前标签的全路径数据
                    vo.setTitles(new ArrayList<>(titles));
                    //递归封装子标签
                    vo.setSubTags(getSubTags(list, tag.getId(), tagIdSet, titles));
                    //进行回溯操作，将截止到当前层级封装的标签名称全部删除。避免在下次递归中影响其他分支的数据
                    titles.subList(index, titles.size()).clear();
                    return vo;
                }).collect(Collectors.toList());
    }
}

广度优先搜索封装每层数据

在上一步中，已经将树形数据封装完毕。下面需要对它进行处理，将树中每一层的数据封装为一个List集合，最后返回一个List<List<TagVo>>格式的数据。

如果想获取树结构中每一层的数据，可以借助于广度优先搜索的思想，使用队列来完成。队列是一种先入先出的数据结构。

我们自顶向下的遍历树结构，遍历到每一层时，先将当前层所有数据放入队列，然后记录一下队列的大小size，此时的size就是当前层的节点个数。

然后我们从队列中，取出size个元素，封装为一个List集合，这个List集合中封装的就是当前层的数据。同时，如果判断子标签不为空，将子标签的数据也添加到队列中。

通过while循环，将整棵树的所有节点数据封装到List集合中。

@Service
public class TagServiceImpl extends ServiceImpl<TagMapper, TagEntity> implements TagService {

    @Autowired
    private UserTagService userTagService;

    @Override
    public List<List<TagVo>> list(Integer userId) {
        //查询所有标签数据
        List<TagEntity> list = list();

        //查询用户已绑定的所有标签id
        List<Integer> tagIdList = userTagService.list(new QueryWrapper<UserTagEntity>().eq("user_id", userId)).stream().map(ut -> ut.getTagId()).collect(Collectors.toList());

        //递归封装树形结构
        List<TagVo> vos = getSubTags(list, 0, new HashSet<>(tagIdList), new ArrayList<>());

        //处理树形数据，封装每层的标签数据
        List<List<TagVo>> result = handleTreeData(vos);

        return result;
    }

    /**
     * 封装标签树形数据
     *
     * @param list     标签数据集合
     * @param parentId 本次递归中过滤中所使用的父标签ID
     * @param tagIdSet 当前用户已绑定的所有标签集合
     * @param titles   用于封装当前标签的全路径数据
     * @return
     */
    private List<TagVo> getSubTags(List<TagEntity> list, Integer parentId, Set<Integer> tagIdSet, List<String> titles) {
        //省略代码...
    }

    /**
     * 处理树形数据 封装每层的标签数据
     *
     * @param list
     * @return
     */
    private List<List<TagVo>> handleTreeData(List<TagVo> list) {
        List<List<TagVo>> result = new ArrayList<>();
        
        //先将本层的元素 放入队列
        Queue<TagVo> queue = new LinkedList<>();
        list.forEach(t -> queue.offer(t));
        
        //while循环，只要队列不为空 就继续遍历
        while (!queue.isEmpty()) {
            List<TagVo> vos = new ArrayList<>();
            //获取此时队列的size，实际就是当前层的节点个数
            int size = queue.size();
            //for循环处理，将当前层的所有数据 封装到List集合
            for (int i = 0; i < size; i++) {
                TagVo vo = queue.poll();
                vos.add(vo);
                //如果存在子标签，将子标签的数据也放到队列中
                if (vo.getSubTags() != null) {
                    vo.getSubTags().forEach(t -> queue.offer(t));
                }
            }
            result.add(vos);
        }
        
        return result;
    }
}

总结

如果不需要通过递归来封装全路径信息，其实可以不用这么麻烦。直接根据parent_id，单独查每一层的数据也可以。这里是因为需要借助递归来完成某些工作。

此外，代码中还有一些细节问题，例如handleTreeData中封装的TagVo中，每个对象都封装了包含自身节点以及子节点的全部数据，这无疑是浪费了很多空间。这里可以再定义一个类，只封装基本数据，不要再封装子标签数据了。这里可以自行修改。

以上，就完成了这个需求。感谢各位的阅读，文章中有不对的地方，感谢各位指正，谢谢~

前言

准备工作

表设计

代码

代码实现

递归+回溯 封装树形数据

广度优先搜索 封装每层数据

总结

递归+回溯封装树形数据

广度优先搜索封装每层数据