递归填充树图

Question

我有一个数据结构，其中节点可以有多个父母。
我有一个我想插入到树中的节点列表。 列表中的节点包含数据及其父项的子列表。

我想从这个列表中构建一棵树。

private class Treenode { 

     private List<Treenode> children; 
     private List<Treenode> parents; 

     public List<Treenode> getChildren() { 
      return children; 
     } 

     public List<Treenode> getParents() { 
      return parents; 
     } 

     private Info data; 


     public Info getData() { 
      return data; 
     } 

     public void setData(Info data) { 
      this.data = data; 
     } 

     public Treenode() { 
      children = new ArrayList<Treenode>(); 
      parents = new ArrayList<Treenode>(); 
     } 

     public Treenode(Info data) { 
      children = new ArrayList<Treenode>(); 
      parents = new ArrayList<Treenode>(); 
      this.data = data; 
     } 

     public boolean addChild(Treenode n) { 
      return children.add(n); 
     } 

     public boolean removeChild(Treenode n) { 
      return children.remove(n); 
     } 
     public boolean addParent(Treenode n) { 
      return parents.add(n); 
     } 

     public boolean removeParent(Treenode n) { 
      return parents.remove(n); 
     } 



    } 


private void scanListAndAddToTree(final List list,Treenode parent){ 

     for (Iterator iter = list.iterator(); iter.hasNext();) { 
      Info info = (Info) iter.next(); 
      String [] parents = info.getParents(); 
      if(parents==null){ //no parents 
       Treenode newNode = new Treenode(info); 
       parent.addChild(newNode); 
       scanTree(list,newNode); 
      } else 

      for (int i = 0; i < parents.length; i++) { 
       if (parents[i].getID.equals(parent.data.getID())){ 
        Treenode newNode = new Treenode(info); 
        parent.addChild(newNode); 
        scanTree(list,newNode); 
       } 
      }   

}

但我的代码是错误的:(

递归从未停止并重新添加同一节点

Answer 1

如果你让你的类防弹如下列表插入，按物品完成是没有问题的

import java.util.Collections; 
import java.util.HashSet; 
import java.util.Set; 

public class GraphNode<D> { 

    private D data; 
    private Set<GraphNode<D>> ins = new HashSet<>(); 
    private Set<GraphNode<D>> outs = new HashSet<>(); 

    public GraphNode(D data) { 
     this.data = data; 
    } 

    public D getData() { 
     return data; 
    } 

    public void setData(D data) { 
     this.data = data; 
    } 

    public Set<GraphNode<D>> getIns() { 
     return Collections.unmodifiableSet(ins); 
    } 

    public Set<GraphNode<D>> getOuts() { 
     return Collections.unmodifiableSet(outs); 
    } 

    public void addIn(GraphNode<D> node) { 
     if (node == null) { 
      throw new NullPointerException(); // Never add null. 
     } 
     if (ins.add(node)) { 
      node.outs.add(this); 
     } 
    } 

    public void addOut(GraphNode<D> node) { 
     if (node == null) { 
      throw new NullPointerException(); // Never add null. 
     } 
     if (outs.add(node)) { 
      node.ins.add(this); 
     } 
    } 
} 

备注

• 这是写在Java 7中，对于以前的Java变化<>到<GraphNode<D>>。
• 我已经使用了名称Graph，与多个父母一样Tree是一个用词不当的人。
• 将Info类参数化为<D>，因此可以重用该类。
• 无法修改收藏集的吸气剂。
• addIn和addOut garantuee一个正确的结构。
• removeIn/removeOut“left excercise”。
• 我已经使用Set s依靠对象（指针）的平等。

---

public static class Info { 
    private String id; 
    private String[] parents; 

    private String getID() { 
     return id; 
    } 

    public String[] getParents() { 
     return parents; 
    } 
} 

public static class TreeNode extends GraphNode<Info> { 
    public TreeNode(Info info) { 
     super(info); 
    } 
} 

private void insertGraph(Map<String, TreeNode> allNodes, List<Info> insertList) { 
    for (Info info : insertList) { 
     TreeNode newNode = new TreeNode(info); 
     allNodes.put(info.getID(), newNode); 
    } 
    for (TreeNode node : allNodes.values()) { 
     for (String parentID: node.getData().getParents()) { 
      TreeNode parentNode = allNodes.get(parentID); 
      parentNode.addOut(node); 
     } 
    } 
} 

private TreeNode scanTree(Info rootInfo, List<Info> insertList) { 
    Map<String, TreeNode> allNodes = new HashMap<>(); 
    insertList.add(rootInfo); 
    insertGraph(allNodes, insertList); 
    return allNodes.get(rootInfo.getID()); 
} 

由于没有保证与所有的家长一棵树，和信息已经包含了结构，不需要递归，但需要节点的集合。 由于信息可能涉及没有定义TreeNode的ID，因此需要两个阶段/ fors。