如何在Java中

Question

創建動態樹數據結構

具體我要代表如下：

1. 在任何節點的樹能有孩子任意數量的
2. （後根）每個父節點只是一個字符串（其子也是字符串）
3. 我需要能夠獲得父和列出所有的孩子（某種列表或字符串數​​組）給定輸入字符串代表給定節點
4. 動態填充基於參數關係的樹結構恩和孩子。 給出的例子是我有一個member1贊助另一個member2和member2贊助成員3等等。已經有表格記錄關係

有沒有可用的結構？

我的數據是從數據庫或表，我會遍歷的名稱和關係有關的信息，以確定該節點是根，父母或孩子。

因此，在循環過程中，我找到了一個孩子，我需要一個父對象的引用，以便在將子對象添加到其父對象之前，可以將其與父對象進行比較。

我找到的最接近的代碼。

public class TreeNode<T> implements Iterable<TreeNode<T>> { 

    T data; 
    TreeNode<T> parent; 
    List<TreeNode<T>> children; 

    public TreeNode(T data) { 
     this.data = data; 
     this.children = new LinkedList<TreeNode<T>>(); 
    } 

    public TreeNode<T> addChild(T child) { 
     TreeNode<T> childNode = new TreeNode<T>(child); 
     childNode.parent = this; 
     this.children.add(childNode); 
     return childNode; 
    } 

    // other features ... 

} 
Sample usage: 

TreeNode<String> root = new TreeNode<String>("root"); 
{ 
    TreeNode<String> node0 = root.addChild("node0"); 
    TreeNode<String> node1 = root.addChild("node1"); 
    TreeNode<String> node2 = root.addChild("node2"); 
    { 
     TreeNode<String> node20 = node2.addChild(null); 
     TreeNode<String> node21 = node2.addChild("node21"); 
     { 
      TreeNode<String> node210 = node20.addChild("node210"); 
     } 
    } 
} 

這就是我迄今爲止所做的。父母將被最新的條目覆蓋，所以我無法檢索我以前添加的內容。

public static TreeNode<String> getSet1() throws IOException { 

     BufferedReader reader = new BufferedReader(new FileReader("test.txt")); 
     String line; 

     while ((line = reader.readLine()) != null) { 
      String[] items = line.split(":"); 

      String name = items[0]; 
      String parent = items[1]; 
      String type = items[2]; 

      if (parent.equalsIgnoreCase("-") && type.equalsIgnoreCase("mainparent")) { 

       root = new TreeNode<String>(name); 


      } else if (type.equalsIgnoreCase("ChildParent") && parent.equalsIgnoreCase(root.toString())) { 

       childParent = root.addChild(name); 

      } else if (type.equalsIgnoreCase("Child") && parent.equalsIgnoreCase(childParent.toString())) { 

       child = childParent.addChild(name); 
      } 

     } 

     return root; 
    } 

Answer 1

你的圖表示任意深度的樹，但你的代碼只處理祖父母 - >父 - >子關係（與在根單祖父母）。

我會忽略這個類型，因爲所有你需要的是一個人的名字和他們父母的名字。如果父母的名字是短劃線，那麼你知道你有根。

現在，對於每個人，您需要在樹中已經獲得父節點（假設父母在列表中的孩子之前） - 如果情況並非如此，則問題變得更加複雜，因爲您必須存儲孤兒暫時和每個新人看到他們是否是孤兒的父母）。

爲了按名稱獲取父項，應該將已經處理的每個人存儲在第二個數據結構中，並行於樹。第二個數據結構應該可以很容易地按名稱查看某個人。地圖，特別是哈希表，對此非常理想。這是如何工作的：

Map processedPersonsMap=new Hashtable<String, TreeNode<String>>(); 

對於每個人，你將它們存儲在地圖上，他們的名字索引：

TreeNode<String> person=...; 
processedPersonsMap.put(person.getData(), person); 

當你在一個新的人閱讀和他們的父母的名字是不是短跑，你看父母：

String parentName=items[1]; 
TreeNode<String> parent=processedPersonsMap.get(parentName); 

這樣，無論樹多深，你總能找到正確的父母。但是請記住，這需要一個有效的輸入文件，其中每個孩子都在父母之後，並且不包含循環引用或缺少父母。

如果這些條件不符合，您必須明確處理它們。