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

Question

我有一个动态检索的层次结构树(通过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，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;
        }
    }
}

输出：

最大深度:100个最大节点:100- 2，3，4，5，6，7，8，9 最大深度:1最大节点:100- 2，3 最大深度:2个最大节点:5- 2，3，4，5，6