按級別扁平化一個動態的層次結構樹

我有一個層次結構樹，我在飛行中檢索（通過REST服務）。我根據深度和我想要的資料的限制來限制資料。我希望根據級別對該樹進行扁平化處理，因此首先是子孫，然后是孫子，等等。

例如：

1
 -2
   -4 -4
   -5 -5
     -8 -8
 -3 -3
   -6 -6
   -7 -7
     -9 -9

如果深度為100，極限為100，那么應該是2 3 4 5 6 7 8 9
。 如果深度為1，極限為100，則應該是2 3
。 深度為2，極限為5，應該是2 3 4 5 6

@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） {
    //這里我們通過REST WS獲得資料。
    結果 = .... (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

uj5u.com熱心網友回復：

下面的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"/span>, Arrays.asList("2"/span>, "3"/span>)。
            tree.put("2"/span>, Arrays.asList("4"/span>, "5"/span>)。
            tree.put("3"/span>, Arrays.asList("6"/span>, "7"/span>)。
            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("最大深度:"  maxDepth   " 最大節點:"  maxNodes  " - "  findChildren(maxDepth, maxNodes, tree) )。

            maxDepth =1; maxNodes =100。
            System.out.println("最大深度:"  maxDepth   " 最大節點:"  maxNodes  " - "  findChildren(maxDepth, maxNodes, tree) )。

            maxDepth =2; maxNodes =5。
            System.out.println("最大深度:"  maxDepth   " 最大節點:"  maxNodes  " - " findChildren（maxDepth, maxNodes, tree））。
        }

        //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<>();//保持當前深度的所有節點。
            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<>();//收集所有下一級的節點。
                //向nodesAtNextDepth添加所有下一深度節點，尊重maxNodes限制。
                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 max nodes:100 - [2, 3]
max depth:2 max nodes:5 - [2, 3, 4, 5, 6]

標籤：

上一篇：在Turtle中繪制分形的方形圖案

下一篇：如何用遞回將一個回圈的索引推入一個陣列？