按级别展平动态层次结构树

Question

我有一个动态检索的层次结构树（通过 REST 服务）。我根据深度和我想要的数据限制来限制数据。我想根据级别压平那棵树，所以首先 children 然后是 grandchildren，等等

例如：

如果深度为 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

Answer 1

下面的 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;
        }
    }
}

输出：

max depth:100 max nodes:100 - [2, 3, 4, 5, 6, 7, 8, 9]
max depth:1 max nodes:100 - [2, 3]
max depth:2 max nodes:5 - [2, 3, 4, 5, 6]

按级别展平动态层次结构树

Flatten a dynamic hierarchy tree by level

java

tree

recursion

hierarchy

flatten