如何將列表轉換爲一棵樹，多個對象實例和循環檢測

Question

問題

我需要一個平坦的列表轉換爲一棵樹。與我發現的解決方案相反，我還需要考慮同一個對象可以多次與父對象關聯。而且我需要檢測週期，以避免無限循環。有沒有人有一個好的算法呢？

示例清單（請注意，列表中的項目可能是隨機IDS不分先後）：

null -> 1 
1 -> 2 
1 -> 3 
2 -> 3 
3 -> 4 

所以樹是這樣的：

null 
    --> 1 
    --> 2 
     --> 3 
     --> 4 
    --> 3 
     --> 4 

在換句話說，節點4的結構（如果它有孩子的話）將不得不被複制。

代碼

我在Java中的做法，但只有一個作品，未經3 -> 4關聯。

import java.awt.BorderLayout; 
import java.util.ArrayList; 
import java.util.Enumeration; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 

import javax.swing.JFrame; 
import javax.swing.JScrollPane; 
import javax.swing.JTree; 
import javax.swing.tree.DefaultMutableTreeNode; 

public class List2Tree { 

    public static void main(String args[]) { 

     // load list 
     List<Relation> relations = load(); 

     // convert to tree 
     DefaultMutableTreeNode root = convertUsingObject(relations); 

     // logging 
     log(root); 

     // create ui 
     JTree tree = new JTree(root); 
     JScrollPane scrollPane = new JScrollPane(tree); 
     JFrame frame = new JFrame(); 
     frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
     frame.add(scrollPane, BorderLayout.CENTER); 
     frame.setSize(300, 150); 
     frame.setVisible(true); 

    } 


    /** 
    * Load a relation list 
    * @return 
    */ 
    public static List<Relation> load() { 

     List<Relation> relations = new ArrayList<>(); 
     relations.add(new Relation(null, 1)); 
     relations.add(new Relation(1, 2)); 
     relations.add(new Relation(1, 3)); 
     relations.add(new Relation(2, 3)); 
     relations.add(new Relation(3, 4)); 

     return relations; 
    } 


    /** 
    * Convert the list to a tree using the relation object 
    * @param relations 
    * @return 
    */ 
    public static DefaultMutableTreeNode convertUsingObject(List<Relation> relations) { 

     // create a map of all possible tree node objects 
     Map<Relation,DefaultMutableTreeNode> nodeMap = new HashMap<>(); 
     Map<Integer,DefaultMutableTreeNode> childNodeMap = new HashMap<>(); 
     for(Relation relation: relations) { 

      DefaultMutableTreeNode node = new DefaultMutableTreeNode(relation); 
      nodeMap.put(relation, node); 
      childNodeMap.put(relation.child, node); 

     } 

     // create root 
     DefaultMutableTreeNode root = new DefaultMutableTreeNode(new Relation(null, null)); 

     // iterate through all children, find the tree node and link the child to the parent 
     for(Relation relation: relations) { 

      DefaultMutableTreeNode node = nodeMap.get(relation); 

      if(relation.parent == null) { 

       root.add(node); 

      } else { 

       DefaultMutableTreeNode parent = childNodeMap.get(relation.parent); 

       parent.add(node); 

      } 

     } 

     return root; 
    } 

    /** 
    * Logging 
    * @param root 
    */ 
    public static void log(DefaultMutableTreeNode root) { 

     // log 
     Enumeration e = root.preorderEnumeration(); 
     while (e.hasMoreElements()) { 
      System.out.println(e.nextElement()); 
     } 


    } 

    /** 
    * Parent-child relationship 
    */ 
    public static class Relation { 

     Integer parent; 
     Integer child; 

     public Relation(Integer parent, Integer child) { 
      this.parent = parent; 
      this.child = child; 
     } 

     public String toString() { 
      return "" + child; 
     } 
    } 
} 

非常感謝您的幫助！

Answer 1

首先，您需要以合理的順序輸入。然後，您可以按照Jim在評論中所建議的內容進行操作：當您遇到新的關係x -> y時，請查找所有節點x（使用地圖）併爲其中的每個節點創建一個新子項y。

該訂單可以定義如下：每個關係x -> y必須在任何其他關係y -> z之前。這基本上是節點的優先關係。如果關係列表中包含關係x -> y，那意味着必須在節點y之前處理節點x。因此，先建立這個優先圖（這裏沒有重複的節點）。然後序列化它。如果無法序列​​化圖形，則有一個循環。然後，按照序列化順序處理節點（即爲每個傳出弧創建新的子節點）。

Answer 2

根據評論，該解決方案有點複雜，但仍然很簡單。

下面是一些僞代碼：鑑於任何a -> b：

aList = list of references to all existing nodes labeled a 
bList = list of references to all existing nodes labeled b 
if (bList is empty) 
    bList.add(new b) 
for (a : aList) 
    for (b : bList) 
     if the subtree rooted at b contains a 
      throw CycleDetectedException 
     c = Deep Clone(b) 
     a.addChild(c); 

我相信，但還沒有被證明，那自b子樹被克隆，週期只能如果b的子樹包含的a一個實例創建