java动态创建一个树形图并遍历它

Question

我有一个图形，它将使用外部源输入。到目前为止，大致的结构是这样的：

.在这里，红线代表节点的同级，可能是依赖关系，但不是父关系本身。它可能存在，也可能不存在

目前，我对每个节点都有以下代码：

    public class TreeNode {    
        private int id;
        private int container; 
        private int status;
        private int value;  
        private boolean visited;
        private String node_name;       
        private ArrayList children = new ArrayList();
        private ArrayList siblings = new ArrayList();
        private ArrayList parents = new ArrayList();

        public TreeNode()
        {
            this.id = 0;
            this.status = 0;
            this.visited = false;
            this.node_name="";
        }
        //Getters and setters below.    
        //parents/siblings/children are added through addParent(treeNode);
    }

然后，我有以下代码来设置值：

    public class TreeSetter {

        public static void main(String[] args) {

            TreeNode A = new TreeNode();        
            TreeNode B = new TreeNode();
            TreeNode C = new TreeNode();
            TreeNode D = new TreeNode();        
            TreeNode E = new TreeNode();
            TreeNode F = new TreeNode();
            TreeNode G = new TreeNode();
            TreeNode H = new TreeNode();

            A.setId(1);
            A.setNode_name("A");
            A.setStatus(1);
            A.addParent(null);

            B.setId(2);
            B.setNode_name("B");
            B.setStatus(1);
            B.addParent(A);
            A.addChildren(B);

            C.setId(3);
            C.setNode_name("C");
            C.setStatus(1);
            C.addParent(A);
            A.addChildren(C);

            D.setId(4);
            D.setNode_name("D");
            D.setStatus(1);
            D.addParent(A);
            A.addChildren(D);

            E.setId(5);
            E.setNode_name("E");
            E.setStatus(1);
            E.addParent(B);
            E.addParent(C);
            E.addParent(D);
            B.addChildren(E);
            C.addChildren(E);
            D.addChildren(E);
            E.addSiblings(F);
            E.addSiblings(G);
            E.addSiblings(H);       

            F.setId(6);
            F.setNode_name("F");
            F.setStatus(1);
            F.addParent(B);
            F.addParent(C);
            F.addParent(D);
            B.addChildren(F);
            C.addChildren(F);
            D.addChildren(F);
            F.addSiblings(E);
            F.addSiblings(G);
            F.addSiblings(H);

            G.setId(7);
            G.setNode_name("G");
            G.setStatus(1);
            G.addParent(B);
            G.addParent(C);
            G.addParent(D);
            B.addChildren(G);
            C.addChildren(G);
            D.addChildren(G);
            G.addSiblings(E);
            G.addSiblings(F);
            G.addSiblings(H);

            H.setId(8);
            H.setNode_name("H");
            H.setStatus(1);
            H.addParent(B);
            H.addParent(C);
            H.addParent(D);
            B.addChildren(H);
            C.addChildren(H);
            D.addChildren(H);
            H.addSiblings(E);
            H.addSiblings(F);
            H.addSiblings(G);
            //Set all other nodes

            //Set all node values.  
        }    
    }

所以，我需要的是，假设给定H，我需要知道：

• H->；的值是多少；I->；L（H+I+L）
• 如果H发生变化，谁会受到影响。H->；B、 C，D->；A
• H的依赖性是什么？F、 G，E

鉴于此，我的问题是：

• 如何动态创建树？例如，假设不是12个节点，而是1000个节点。使用我的代码，我需要很多行来设置值和关系，因为我手工创建每个对象。我应该使用反射、工厂范例来创建1000个对象吗

• 我怎么走在树上？例如，给定D，移动D->；H->；I->；L（等等）。 我知道递归是最简单、最干净的方法，但我不知道如何实现它：（

Answer 1

如何动态创建树：

public class Tree {

    private class Node {
        public int value;
        public List<Node> = new children ArrayList<Node>();
        public List<Node> = new parents ArrayList<Node>();
        public static final INFINITY = Integer.MAX_VALUE;

        public void addChild(Node n) {
            children.add(n);
        }

        public void addParent(Node n) {
            parents.add(n);
        }

        public int getValue() {return value;}

        //What is the value from H -> I -> L (H+I+L):
        int getValueToNode(Node Destination, HashSet<Node> s) {
           int minValue = INFINITY;
           int value = 0;

           if(s.contains(this)) return INFINITY; //we already checked this
           s.add(this);
           if(this.equals(Destination)) return Destination.value();

           for(int i = 0; i < children.size(); i++) {
               Node c = children.get(i);
               int value = c.getValueToNode(Destination);
               if (value != Integer.MAX_VALUE && value < minValue) {
                   minValue = value + this.getValue();
               }
           }

           for(int i = 0; i < parents.size(); i++) {
               Node p = parents.get(i);
               value = p.getValueToNode(Destination);
               if (value != Integer.MAX_VALUE && value < minValue) {
                   minValue = value + this.getValue();
               }
           }
           return minValue;
        }

        //Who will be affected if H changes. H -> B,C,D -> A
        public int getDependency(ArrayList<Node> affected) {
          for(int i = 0; i < children.size(); i++) {
               Node c = children.get(i);
               affected.add(c);
           }

           for(int i = 0; i < parents.size(); i++) {
               Node p = parents.get(i);
               affected.add(p);
           }
        }

        //What are the dependencies of H? F, G, E.
        List<Node> getDependency() {
           List<Node> dependency = new ArrayList<Node>();
           for(int i = 0; i < parents.size(); i++) {
               Node p = parents.get(i);
               for(int j= 0 ; j < p.children.size(); j++) {
                   Node c = p.children.get(i);
                   if(!c.equals(this)) dependency.add(c);
               }
           }
           return dependency;
        }
    }

    //data here.
    private Map<String, Node> mapping = new HashMap<String, Node>();

    public connectParentToChild(String parent, String child) {
        Node p = getNode(parent);
        Node c = getNode(child);
        p.addChild(c);
        c.addParent(p);
    }

    public int getValue(String first, String second) {
        a = getNode(first);
        b = getNode(second);
        HashSet<Node> s = new HashSet<Node>();
        return a.getValueToNode(b, s);
    }

    private Node getNode(String s) {
        if(!mapping.containsKey(s)) {
           mapping.put(s, new Node(...));
        }
        return mapping.get(s);
    }

    //members here.
}

这是一种动态添加节点的简单方法

public static void main(String[] args) {
    Tree t;
    t.connectParentToChild("A", "D");
    t.connectParentToChild("A", "B");
    t.connectParentToChild("A", "C");
    t.connectParentToChild("B", "C");
    t.connectParentToChild("B", "H");
    t.connectParentToChild("B", "F");
    t.connectParentToChild("B", "E");
    //Set all other nodes
    t.getValue("H", "L");
}

Answer 2

public void printWholeNode(Node root) {
    if (root.getChildren().size() == 0) {
        if (root.visited == false) {
            System.out.println(root.name);
            root.visited = true;
        }
        return ;
    } else {
        System.out.println(root.name);
        root.visited = true;
        for (Node childNode : root.getChildren()) {
            printWholeNode(childNode);
        }
    }
}