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

前言

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

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

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

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

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

准备工作

表设计

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

用户表:

标签表:

用户标签关联表:

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

  1. 标签表有一个字段parentId,用来记录当前标签的父级标签ID,根标签的父级标签ID默认为0
  2. 用户和标签的关联关系,使用了一个中间表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 subTags;
    /**
     * 当前标签是否被绑定给用户
     */
    private boolean checked = false;
    /**
     * 当前节点层级
     */
    private Integer level;
    /**
     * 当前标签的全路径信息
     */
    private List titles;
}

代码实现

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

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

实现类重写该方法

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

递归+回溯 封装树形数据

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

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

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

@Service
public class TagServiceImpl extends ServiceImpl implements TagService {
@Autowired
private UserTagService userTagService;

@Override
public List<list<tagvo>&gt; list(Integer userId) {
    //查询所有标签数据
    List<tagentity> list = list();

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

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

    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 -&gt; tag.getParentId().equals(parentId))
            .map(tag -&gt; {
                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&lt;&gt;(titles));
                //递归封装子标签
                vo.setSubTags(getSubTags(list, tag.getId(), tagIdSet, titles));
                //进行回溯操作,将截止到当前层级封装的标签名称全部删除。避免在下次递归中影响其他分支的数据
                titles.subList(index, titles.size()).clear();
                return vo;
            }).collect(Collectors.toList());
}

}
</list</tagmapper,>

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

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

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

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

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

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

@Service
public class TagServiceImpl extends ServiceImpl implements TagService {
@Autowired
private UserTagService userTagService;

@Override
public List<list<tagvo>&gt; list(Integer userId) {
    //查询所有标签数据
    List<tagentity> list = list();

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

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

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

}
</list</list</list</list</tagmapper,>

总结

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

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

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


这是一个从 https://juejin.cn/post/7368653223797915689 下的原始话题分离的讨论话题