java - 递归计算它有多少级别和 child 数量

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表示他总共有多少个superior，uplevel表示他有多少级superior，downnum和downlevel差不多是这样

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

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

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

什么是最好的方法？或者有更好的方法吗？比如一些图算法，或者 graph-db(数据库)？

Answer 1

没有真正需要数据库。一个简单的迭代和一个递归函数就可以完成所需的分析:

import java.util.ArrayList;
import java.util.List;

public class Graph {

    private final List<Node> nodes;
    private final Node root;

    //Graph assumes unique id > 0, and only root with pid = 0
    Graph(Node root){
        this.root = root;
        nodes = new ArrayList<>();
        nodes.add(root);
    };

    void add(Node node){
        nodes.add(node);
    }

    void analyze(){
        //sort by pid so iteration goes from top level down
        nodes.sort( (n1,n2) -> Integer.compare(n1.getPid(), n2.getPid()) );
        for(Node node : nodes){
            Node parent = getNode(node.getPid());
            if (parent == null ) {
                continue;  //skip root
            }
            node.setUpLevel(parent.getUpLevel()+1);  //add 1 to parent value
            node.setUpNum(node.getUpNum() +1);       //increment by 1
            parent.setDowNum(parent.getDowNum() +1); //increment by 1
            updateHigherLevels(node);
        }
    }

    //recursively update higher levels
    private void updateHigherLevels(Node node) {
        Node parent = getNode(node.getPid());
        if(parent == null) return;
        parent.setDownLevel(node.getDownLevel() + 1);
        updateHigherLevels(parent);
    }

    void print(){
        //sort by id for nice printing
        nodes.sort( (n1,n2) -> Integer.compare(n1.getId(), n2.getId()) );
        String format = "\n%2s %3s %4s %5s %7s %7s  %8s";
        System.out.printf(format,"id","pid","name","upnum","uplevel", "downnum" , "downlevel");
        for(Node node : nodes){
            System.out.printf(format, node.getId(), node.getPid(), node.getName(), node.getUpNum(), node.getUpLevel()
                    , node.getDowNum(), node.getDownLevel());
        }
    }

    Node getNode(int id){

        for(Node node : nodes){
            if(node.getId() == id) return node;
        }

        return null;
    }

    public static void main(String[] args) {
        //make graph
        Graph graph = new Graph(new Node(1, 0, "a"));
        graph.add(new Node(2, 1, "b"));
        graph.add(new Node(3, 1, "c"));
        graph.add(new Node(4, 2, "d"));
        graph.add(new Node(5, 2, "e"));

        graph.analyze();
        graph.print();
    }
}

class Node {

    private final int id,pid;
    private int upnum = 0, uplevel = 0, downum = 0,  downlevel = 0;
    private final String name;

    Node(int id, int pid, String name) {
        super();
        this.id = id;
        this.pid = pid;
        this.name = name;
    }

    int getId() { return id; }

    int getPid() { return pid;  }

    String getName() { return name; }

    int getUpNum() { return upnum;  }

    void setUpNum(int upnum) { this.upnum = upnum; }

    int getUpLevel() { return uplevel; }

    void setUpLevel(int uplevel) { this.uplevel = uplevel; }

    int getDowNum() { return downum; }

    void setDowNum(int downum) { this.downum = downum; }

    int getDownLevel() { return downlevel; }

    void setDownLevel(int downlevel) { this.downlevel = downlevel; }
}

输出: