Preface
Recently at work, I encountered the following requirement: We have the concept of tag, which can be assigned to users, and the relationship between them is many-to-many. When editing a user, we need to query all tags, mark which tags are already assigned to the current user, and also encapsulate the full path information for each tag, which will be displayed when a tag is checked.
Since tags have a hierarchical structure (for example, first-level, second-level, and third-level tags), they only need to be encapsulated into a tree structure, and the frontend will render it using a third-party tree component. However, the frontend has recently been redesigned, and now we need to encapsulate tag data of each level into a separate List collection. The frontend will render all three levels of tags and display different tag data according to specific rules.
To summarize: we need to query tag data, encapsulate it into a tree structure with full path information, then extract the data of each level from the tree structure and encapsulate each level into a separate List collection.
Completing this requirement is mainly divided into two steps:
Recursion + Backtrackingto encapsulate the tag tree; the backtracking algorithm is used to encapsulate the full path information of tags during the recursion process.- Secondary processing of the encapsulated tag tree, using
breadth-first searchto encapsulate node data for each level.
Preparation
Table Design
I have simplified the business tables for this explanation
User table:
Tag table:
User-tag relationship table:
The table design above is easy to understand:
- The tag table has a
parentIdfield, which is used to record the parent tag ID of the current tag. The parent tag ID of the root tag defaults to0. - The many-to-many relationship between users and tags is maintained by the intermediate table
t_user_tag.
Code
The project uses SpringBoot v2.6.13, with dependencies such as mybatis-plus and lombok introduced.
As shown below, the corresponding entity, mapper, and service for each table have been generated
We also provide a TagVo class to encapsulate the processed tag data:
@Data
public class TagVo {
/**
* Tag ID
*/
private Integer id;
/**
* Tag name
*/
private String name;
/**
* Collection of child tags
*/
private List subTags;
/**
* Whether the current tag is assigned to the user
*/
private boolean checked = false;
/**
* Current node level
*/
private Integer level;
/**
* Full path information of the current tag
*/
private List titles;
}
Code Implementation
First, we define a method list in TagService, with the return type of List<List>. Since the requirement asks to encapsulate data of each level into separate collections, we return this List of Lists.
public interface TagService extends IService {
List<List> list(Integer userId);
}
The implementation class overrides this method
@Service
public class TagServiceImpl extends ServiceImpl implements TagService {
@Override
public List<List> list(Integer userId) {
return null;
}
}
Recursion + Backtracking to Encapsulate Tree-structured Data
We first use recursion to encapsulate the tree-structured data. During the recursion process, we apply the idea of the backtracking algorithm to encapsulate the full path data of each tag.
At the same time, when judging whether a current tag is assigned, we pre-encapsulate a Set collection to avoid repeated database queries for each recursion.
For a detailed introduction to recursion + backtracking to encapsulate tree data, interested readers can click here to refer to my previous article, so I will not repeat the details here.
@Service public class TagServiceImpl extends ServiceImpl implements TagService {@Autowired private UserTagService userTagService; @Override public List<List<tagvo>> list(Integer userId) { // Query all tag data List<tagentity> list = list(); // Query all tag IDs already assigned to the user List<integer> tagIdList = userTagService.list(new QueryWrapper<usertagentity>().eq("user_id", userId)).stream().map(ut -> ut.getTagId()).collect(Collectors.toList()); // Recursively encapsulate the tree structure List<tagvo> vos = getSubTags(list, 0, new HashSet<>(tagIdList), new ArrayList<>()); return null; } /** * Encapsulate tag tree-structured data * * @param list Tag data collection * @param parentId Parent tag ID used for filtering in the current recursion * @param tagIdSet Set of all tags already assigned to the current user * @param titles Used to encapsulate the full path data of the current tag * @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(); // Copy property values BeanUtils.copyProperties(tag, vo); // Set whether the current tag is already assigned to the user vo.setChecked(tagIdSet.contains(tag.getId())); // Encapsulate child tags and full title information titles.add(tag.getName()); // Record the index of the element added to the collection in the previous step: we will perform backtracking based on this index later int index = titles.size() - 1; // Encapsulate the full path data of the current tag vo.setTitles(new ArrayList<>(titles)); // Recursively encapsulate child tags vo.setSubTags(getSubTags(list, tag.getId(), tagIdSet, titles)); // Perform backtracking: clear all tag names added up to the current level, to avoid affecting data of other branches in the next recursion titles.subList(index, titles.size()).clear(); return vo; }).collect(Collectors.toList()); }
}
</tagmapper,>
Breadth-first Search to Encapsulate Level-specific Data
In the previous step, we have finished encapsulating the tree-structured data. Next, we need to process it, extract the data of each level from the tree, encapsulate each level into a separate List collection, and finally return data in the format of List<List>.
If you want to get the data of each level in a tree structure, you can use the idea of breadth-first search and complete this with a queue. A queue is a first-in first-out data structure.
We traverse the tree structure from top to bottom. When we reach a level, we first put all data of the current level into the queue, then record the size of the queue. This size is exactly the number of nodes in the current level.
Then we take out size elements from the queue and encapsulate them into a List collection. This List collection holds all data of the current level. At the same time, if the child tags are not empty, we add the child tag data to the queue as well.
The while loop encapsulates all node data of the entire tree into the final List of Lists.
@Service public class TagServiceImpl extends ServiceImpl implements TagService {@Autowired private UserTagService userTagService; @Override public List<List<tagvo>> list(Integer userId) { // Query all tag data List<tagentity> list = list(); // Query all tag IDs already assigned to the user List<integer> tagIdList = userTagService.list(new QueryWrapper<usertagentity>().eq("user_id", userId)).stream().map(ut -> ut.getTagId()).collect(Collectors.toList()); // Recursively encapsulate the tree structure List<tagvo> vos = getSubTags(list, 0, new HashSet<>(tagIdList), new ArrayList<>()); // Process tree data, encapsulate tag data for each level List<List<tagvo>> result = handleTreeData(vos); return result; } /** * Encapsulate tag tree-structured data * * @param list Tag data collection * @param parentId Parent tag ID used for filtering in the current recursion * @param tagIdSet Set of all tags already assigned to the current user * @param titles Used to encapsulate the full path data of the current tag * @return */ private List<tagvo> getSubTags(List<tagentity> list, Integer parentId, Set<integer> tagIdSet, List<string> titles) { // Omitted code... } /** * Process tree-structured data and encapsulate tag data for each level * * @param list * @return */ private List<List<tagvo>> handleTreeData(List<tagvo> list) { List<List<tagvo>> result = new ArrayList<>(); // First add all elements of current level to the queue Queue<tagvo> queue = new LinkedList<>(); list.forEach(t -> queue.offer(t)); // while loop, continue traversal as long as the queue is not empty while (!queue.isEmpty()) { List<tagvo> vos = new ArrayList<>(); // Get the current queue size, which is actually the number of nodes in the current level int size = queue.size(); // Process with for loop, encapsulate all data of current level into a List collection for (int i = 0; i < size; i++) { TagVo vo = queue.poll(); vos.add(vo); // If there are child tags, add their data to the queue as well if (vo.getSubTags() != null) { vo.getSubTags().forEach(t -> queue.offer(t)); } } result.add(vos); } return result; }
}
</tagmapper,>
Summary
If you do not need to encapsulate full path information via recursion, this approach is actually unnecessarily complicated. You can directly query the data of each level separately based on parent_id. We use this approach here because we need recursion to complete other tasks.
Additionally, there are some details that can be optimized in the code. For example, the TagVo objects encapsulated in handleTreeData each store all data for themselves and their child nodes, which undoubtedly wastes a lot of memory space. You can define a new class that only encapsulates basic data and does not store child tag data, and modify the code on your own.
That's all, we have completed the implementation of this requirement. Thank you for reading. If there are any mistakes in this article, please feel free to correct me. Thank you~
This is a discussion topic separated from the original topic at https://juejin.cn/post/7368653223797915689