遞歸填充樹圖

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。