java - 逐级展平动态层次结构树
问题描述
我有一个动态检索的层次结构树(通过 REST 服务)。我根据我想要的数据的深度和限制来限制数据。我想根据级别展平那棵树,所以首先是孩子,然后是孙子,等等。
例如:
1
-2
-4
-5
-8
-3
-6
-7
-9
深度 100 和限制 100 应该是 2 3 4 5 6 7 8 9
深度 1 和限制 100 应该是 2 3
深度 2 和限制 5 它应该是 2 3 4 5 6
现在我有一个递归算法,但它不会逐级变平,而是递归地(2 4 5 8 3 6 7 9)。
这是实际的代码:
@GET
@Path("/GetDatas")
public Response getDatas(@QueryParam("clientId") final String clientId,
@QueryParam("maxDepth") final Integer maxDepth,
@QueryParam("limit") final Integer limit) {
Set datas = new LinkedHashSet();
findChildren(clientId, maxDepth, limit, datas, 0);
return Response.status(Response.Status.OK).entity(datas).build();
}
private void findChildren(String clientId, Integer maxDepth, Integer limit, Set datas, Integer actualDepth) {
// here we are getting the data via a REST WS
results = .... (function(clientId))
for (final String result : results) {
if (datas.size() < limit) {
if (!datas.contains(result)) {
datas.add(result);
if (actualDepth < maxDepth) {
findChildren(result, maxDepth, limit, datas, actualDepth + 1);
}
}
}
}
}
我简化了一点。事实上,实际上一个节点也将自己作为孙子(getChildren 将根据算法检索匹配数据,因此如果 2 与 1 匹配,则 1 与 2 匹配)。
列表的顺序也很重要。
这是 JDoodle,您可以进行测试: jdoodle.com/ia/gFm
解决方案
以下 mre 使用BFS来展平树,遵守限制:
import java.util.*;
public class MyClass {
public static void main(String[] args) {
new DataClass().execute();
}
static class DataClass {
public void execute() {
Map<String, List<String>> tree = new LinkedHashMap();
tree.put("1", Arrays.asList("2", "3"));
tree.put("2", Arrays.asList("4", "5"));
tree.put("3", Arrays.asList("6", "7"));
tree.put("5", Arrays.asList("8"));
tree.put("7", Arrays.asList("9"));
tree.put("4", Arrays.asList());
tree.put("6", Arrays.asList());
tree.put("8", Arrays.asList());
tree.put("9", Arrays.asList());
int maxDepth =100, maxNodes =100;
System.out.println("max depth:"+ maxDepth + " max nodes:"+ maxNodes +" - "+ findChildren(maxDepth, maxNodes, tree));
maxDepth =1; maxNodes =100;
System.out.println("max depth:"+ maxDepth + " max nodes:"+ maxNodes +" - "+ findChildren(maxDepth, maxNodes, tree));
maxDepth =2; maxNodes =5;
System.out.println("max depth:"+ maxDepth + " max nodes:"+ maxNodes +" - "+findChildren(maxDepth, maxNodes, tree));
}
//helper method for bfs
Set<String> findChildren(int maxDepth, int maxNodes, Map<String, List<String>> tree) {
Set<String> flatTree = new LinkedHashSet<>(); //hold and return the flatten tree
final String root = "1";
List<String> nodesAtCurrentDepth = new ArrayList<>();//hold all nodes of the current depth
nodesAtCurrentDepth.add(root);
return findChildren(maxDepth, maxNodes, 0, flatTree, nodesAtCurrentDepth, tree);
}
//flatten tree using bfs
Set<String> findChildren(int maxDepth, int maxNodes, int currentDepth, Set<String> flatTree,
List<String> nodesAtCurrentDepth, Map<String, List<String>> tree) {
if(currentDepth < maxDepth && ! nodesAtCurrentDepth.isEmpty()) {
List<String> nodesAtNextDepth = new ArrayList<>();//collects all next level nodes
//add all next depth nodes to nodesAtNextDepth, respecting maxNodes limit
for(String node : nodesAtCurrentDepth){
for(String childNode : tree.get(node)){
if(flatTree.size() + nodesAtNextDepth.size() >= maxNodes) {
break;
}
nodesAtNextDepth.add(childNode);
}
}
flatTree.addAll(nodesAtNextDepth);
currentDepth++;
nodesAtCurrentDepth = new ArrayList<>(nodesAtNextDepth);
findChildren(maxDepth, maxNodes, currentDepth, flatTree, nodesAtCurrentDepth, tree);
};
return flatTree;
}
}
}
输出:
最大深度:100 最大节点:100 - [2, 3, 4, 5, 6, 7, 8, 9]
最大深度:1 最大节点:100 - [2, 3]
最大深度:2 最大节点:5 - [ 2、3、4、5、6]
推荐阅读
- c# - Identity Server 4 - 未经授权的客户端
- c - 无法理解 Deitel&Deitel 书中的插入节点功能
- c# - 在微服务之间进行端到端测试时,如何隔离测试数据或测试流程?
- python-3.x - 试图将列表输出保存到文件
- netsuite - 如何遍历销售订单的所有行项目并获取最早的学期开始日期
- c# - CsvHelper 无法读取双精度值
- sql - 具有多个条件的2个表之间的内部联接查询
- rust - 在 Rust 中实现图结构
- git - Redmine 3.4 重新导入 git repo
- react-native - 使用 React Native Expo 发送短信和切换 SIM 卡