從根節點遍歷所有孩子的n-Tree

Question

我有一個數據庫中的一些表的列表，其中每行包含引用另一行的父字段。這樣

標題，父
A，空
B，A
C，A
d，C
E，B
女，空

在這裏，甲和F是根節點，B和C對A來說是子對象，D對C是子對象，E對B是子對象。

從這個列表中產生樹結構的最好方法是什麼？

一種方法是遍歷列表找到根（沒有父母的標題），然後爲每個根再次遍歷列表並附加根節點。然後，這些節點再次遍歷整個列表以附加他們自己的任何孩子。

例子：

private Node getNode(SomeData d) { 
    List<SomeData> tmp = getChildren(d); 
    if (tmp == null OR empty) return new Node(d); 

    Node n = new Node(d); 
    for (SomeData m : tmp) { 
     n.addChild(getNode(m)); // recurse 
    } 
    return n; 
} 

private List<SomeData> getChildren(SomeData parent) { 
    List<SomeData> tmp = new ArrayList<SomeData>(); 
    for (SomeData candidateChild : myBigFlatDataList.values()) { 
     if (parent.equals(candidateChild)) { 
      tmp.add(candidateChild); 
     } 
    } 
    return tmp; 
} 

有沒有更好的方式來做到這一點？

Answer 1

這是一個相當不錯的方式，但它比它更天真。

另一條路線只需要線性時間。是否有關於唯一標識它的SomeData？我會這樣認爲的;這可能是SomeData本身正確實現equals（）和hashCode（）。

假設有一個方法int SomeData.getID()。然後，我們可以將我們之前看到的節點保存在HashMap中。

Map<Integer, Node> visitedNodes = new HashMap... 

然後，我們只是通過讀取的行數着：

for (SomeData data : ...) { 
    SomeData parent = data.getParent(); 
    Node<SomeData> parentNode = getOrCreateNode(parent); 
    Node<SomeData> childNode = getOrCreateNode(data); 
    parentNode.addChild(childNode); 
} 

private Node<SomeData> getOrCreateNode(SomeData data) { 
    Node<SomeData> node = visitedNodes.get(data.getID()); 
    if (node == null) { 
     node = new Node<SomeData>(data); 
     visitedNodes.put(data.getID(), node); 
    } 
    return node; 
} 

Answer 2

由於您從數據庫獲取數據，因此可以根據父級屬性對行進行排序。然後，每次搜索節點的子節點時，都不需要遍歷整個列表。

編輯： 當列表排序時，你可以停止迭代列表，當你找到所有你要找的孩子。例如，當你有根「A」，並開始在此列表中尋找它的孩子：

B, A 
C, A 
E, B <- when you reach "B" you can assume that there are no 
D, C  other nodes which are children of "A" and stop the iteration 

Answer 3

重讀整個文件（或更糟查詢數據庫）爲每個節點是相當昂貴的。我寧願你在閱讀清單時建立樹。這是我的2美分

1. 讓節點爲一組節點（最初是一個空集）。
2. 讓RootNodes成爲一組所有根節點（最初是一個空集）。
3. 對於每對節點（N1，N2）：
   
   1. 對於每個N（N1，N2）如果N不是在節點，創建N和插入節點。
   2. 如果N2 == null，也可以在根節點中插入N2（另外您也可以將它從節點中刪除）
   3. Mark N2.child = N1。

如果遵循這一點，在迭代在列表的末尾，你應該有：

RootNodes = {A,F} 
Nodes = {B,C,D,E} 

A.child = B 
A.child = C 
C.child = D 
B.child = E 

希望這有助於。

Answer 4

您可以一次構建您的樹。你可以在表上建立所有節點（構建一個從名字到節點的散列表），然後做另一個路徑，你可以在兩個節點之間添加父子關係（將父指針添加到子節點並將子節點添加到父母的子女名單）。

Answer 5

List<User> list = new ArrayList<User>(); 
User blankNode; 
class User{ 
    String userid;  
    User child;  
    public User() { 
     //blankNode 
    } 
    public User(String userid) { 
     this.userid = userid; 
    } 
    @Override 
    public int hashCode(){ 
     return userid.hashCode(); 
    } 
} 
public void addUser(User parent,String userid){ 
    if(null == userid)return; 
    User child = new User(userid); 
    parent.child = child; 
    list.add(child);   
} 
public void removeUser(User child){ 
    if(null == child)return;   
    list.remove(child); 
} 
/* move the rank to up - assume 
* secParent - assign to new child 
*/ 
public void boubbleUp(User secParent, User oldParent, User child){ 
    if(null == child || null == secParent)return; 
    secParent.child = child; 
    oldParent.child = null; 
} 
public List<User> getTopUser(int num){ 
    if(num <1)return null; 
    Map<Integer, List<User>> map = new HashMap<Integer, List<User>>(); 
    for(User usr : list){ 
     int count =0; 
     User temp = usr.child; 
     while(null != temp){ 
      count++;temp=temp.child; 
     }   
     if(map.get(count)== null){ 
      List<User> sameNoOfChildren = new ArrayList<User>() ; 
      sameNoOfChildren.add(usr); 
      map.put(count, sameNoOfChildren); 
     }else{ 
      map.get(count).add(usr);     
     } 
    } 
    Integer[] arr = (Integer[]) map.keySet().toArray(); 
    Arrays.sort(arr); 
    List<User> result = new ArrayList<User>(); 
    for(int i = arr.length-1; i <=arr.length-num; i--){ 
     result.addAll(map.get(i)); 
    }  
    return result;  
}