Рекурсивно заполнить древовидную структуру

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, как и несколько родителей. Дерево - неправильное название.
• Параметризировал класс Info как <D>, чтобы его можно было повторно использовать.
• Геттеры для коллекций, не поддающихся изменению.
• addIn и addOut garantuee правильная структура.
• removeIn/removeOut "left as excercise".
• Я использовал Set s, полагаясь на равенство Object (pointer).

---

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, требуется две фазы/fors.