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

Question

来源是：id, pid,name1,  0,  a2,  1,  b3,  1,  c我们预期的结果是：id,pid,name,upnum,uplevel,downum,downlevel1,  0,  a,  0,    0,      2,     1  2,  1,  b,  1,    1,      0,     03,  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 {

    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; }

}

输出：