递归计算它有多少级和多少个孩子

Question

来源是：

id, pid,name

1,  0,  a

2,  1,  b

3,  1,  c

我们预期的结果是：

id,pid,name,upnum,uplevel,downum,downlevel

1,  0,  a,  0,    0,      2,     1  

2,  1,  b,  1,    1,      0,     0

3,  1,  c,  1,    1,      0,     0

这里，name是人的名字，id标识每个人，pid表示父id，例如，人a是人b的上级。upnum表示他总共有多少个上级，uplevel表示他有多少个上级，downnum和downlevel差不多是这样

为了得到这个结果，我想我有两种方法

1.使用数据库，比如oralce，我用connect byand nocycle，一切正常。但是对于每个人，我必须再次运行“connect by”sql，似乎很慢。而且我们必须在客户端安装一个oracle，有些客户端不喜欢它。如果我们使用h2或一些嵌入式数据库，我们可以使用nocycleoracle的特性吗？但我想它也很慢。或者我们应该制作id的索引？

2.使用java hashMap来存储id和pid的关系，但是当数据变大时，可能会出现out of memory的异常。代码怎么写？

什么是最好的方法？还是有更好的方法？比如一些图形算法或图形数据库（数据库）？

Answer 1

没有真正需要数据库。一个简单的迭代和一个递归函数可以进行所需的分析：import java.util.ArrayList;import java.util.List;public class Graph {&nbsp; &nbsp; private final List<Node> nodes;&nbsp; &nbsp; private final Node root;&nbsp; &nbsp; //Graph assumes unique id > 0, and only root with pid = 0&nbsp; &nbsp; Graph(Node root){&nbsp; &nbsp; &nbsp; &nbsp; this.root = root;&nbsp; &nbsp; &nbsp; &nbsp; nodes = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; nodes.add(root);&nbsp; &nbsp; };&nbsp; &nbsp; void add(Node node){&nbsp; &nbsp; &nbsp; &nbsp; nodes.add(node);&nbsp; &nbsp; }&nbsp; &nbsp; void analyze(){&nbsp; &nbsp; &nbsp; &nbsp; //sort by pid so iteration goes from top level down&nbsp; &nbsp; &nbsp; &nbsp; nodes.sort( (n1,n2) -> Integer.compare(n1.getPid(), n2.getPid()) );&nbsp; &nbsp; &nbsp; &nbsp; for(Node node : nodes){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node parent = getNode(node.getPid());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (parent == null ) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; //skip root&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.setUpLevel(parent.getUpLevel()+1);&nbsp; //add 1 to parent value&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.setUpNum(node.getUpNum() +1);&nbsp; &nbsp; &nbsp; &nbsp;//increment by 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; parent.setDowNum(parent.getDowNum() +1); //increment by 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; updateHigherLevels(node);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; //recursively update higher levels&nbsp; &nbsp; private void updateHigherLevels(Node node) {&nbsp; &nbsp; &nbsp; &nbsp; Node parent = getNode(node.getPid());&nbsp; &nbsp; &nbsp; &nbsp; if(parent == null) return;&nbsp; &nbsp; &nbsp; &nbsp; parent.setDownLevel(node.getDownLevel() + 1);&nbsp; &nbsp; &nbsp; &nbsp; updateHigherLevels(parent);&nbsp; &nbsp; }&nbsp; &nbsp; void print(){&nbsp; &nbsp; &nbsp; &nbsp; //sort by id for nice printing&nbsp; &nbsp; &nbsp; &nbsp; nodes.sort( (n1,n2) -> Integer.compare(n1.getId(), n2.getId()) );&nbsp; &nbsp; &nbsp; &nbsp; String format = "\n%2s %3s %4s %5s %7s %7s&nbsp; %8s";&nbsp; &nbsp; &nbsp; &nbsp; System.out.printf(format,"id","pid","name","upnum","uplevel", "downnum" , "downlevel");&nbsp; &nbsp; &nbsp; &nbsp; for(Node node : nodes){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.printf(format, node.getId(), node.getPid(), node.getName(), node.getUpNum(), node.getUpLevel()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; , node.getDowNum(), node.getDownLevel());&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; Node getNode(int id){&nbsp; &nbsp; &nbsp; &nbsp; for(Node node : nodes){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(node.getId() == id) return node;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; //make graph&nbsp; &nbsp; &nbsp; &nbsp; Graph graph = new Graph(new Node(1, 0, "a"));&nbsp; &nbsp; &nbsp; &nbsp; graph.add(new Node(2, 1, "b"));&nbsp; &nbsp; &nbsp; &nbsp; graph.add(new Node(3, 1, "c"));&nbsp; &nbsp; &nbsp; &nbsp; graph.add(new Node(4, 2, "d"));&nbsp; &nbsp; &nbsp; &nbsp; graph.add(new Node(5, 2, "e"));&nbsp; &nbsp; &nbsp; &nbsp; graph.analyze();&nbsp; &nbsp; &nbsp; &nbsp; graph.print();&nbsp; &nbsp; }}class Node {&nbsp; &nbsp; private final int id,pid;&nbsp; &nbsp; private int upnum = 0, uplevel = 0, downum = 0,&nbsp; downlevel = 0;&nbsp; &nbsp; private final String name;&nbsp; &nbsp; Node(int id, int pid, String name) {&nbsp; &nbsp; &nbsp; &nbsp; super();&nbsp; &nbsp; &nbsp; &nbsp; this.id = id;&nbsp; &nbsp; &nbsp; &nbsp; this.pid = pid;&nbsp; &nbsp; &nbsp; &nbsp; this.name = name;&nbsp; &nbsp; }&nbsp; &nbsp; int getId() { return id; }&nbsp; &nbsp; int getPid() { return pid;&nbsp; }&nbsp; &nbsp; String getName() { return name; }&nbsp; &nbsp; int getUpNum() { return upnum;&nbsp; }&nbsp; &nbsp; void setUpNum(int upnum) { this.upnum = upnum; }&nbsp; &nbsp; int getUpLevel() { return uplevel; }&nbsp; &nbsp; void setUpLevel(int uplevel) { this.uplevel = uplevel; }&nbsp; &nbsp; int getDowNum() { return downum; }&nbsp; &nbsp; void setDowNum(int downum) { this.downum = downum; }&nbsp; &nbsp; int getDownLevel() { return downlevel; }&nbsp; &nbsp; void setDownLevel(int downlevel) { this.downlevel = downlevel; }}输出：