2

我有一个将使用外部源提供的图表。到目前为止，大致的结构是这样的：

TreeGraph，以这种方式显示以适合 . 在那里，红线代表节点的兄弟姐妹，这可能是依赖关系，但不是父母身份本身。它可能存在也可能不存在。

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



    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。

鉴于此，我的麻烦是：

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

  • 我怎么走树？例如，给定 D，移动 D->H->I->L（依此类推）。我知道递归将是最简单和最干净的方法，但我不知道如何实现它:(

4

2 回答 2

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");
}
于 2012-10-30T21:02:10.040 回答
0 
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);
        }
    }
}
于 2013-08-08T13:04:00.360 回答