Java：用於搜索節點樹狀結構的算法

我正在使用java中的「家族樹」程序，並且我無法圍繞用於搜索節點的算法進行包裝。Java：用於搜索節點樹狀結構的算法

一個節點由一個名稱和鏈接到一個夥伴，兄弟姐妹，孩子和一個整數標識符組成。

我正在嘗試的算法只是擊中死角，我會非常感激在正確的方向微調。

基本上，每個節點都有一個數字標識符，我希望能夠讓用戶輸入一個數字，搜索樹中的每個節點並將節點作爲子節點，兄弟節點或匹配節點的夥伴插入。樹結構例如：

注意，因爲它是一個賦值我不能改變結構

Alice[2] <--partner-- John[1] 
         | 
         Ted[3] --sibling--> Eric[4] --sibling--> Joanne[5] 
         | 
         Joe[6] --sibling--> Bret[7]

譜系圖類：

public class FamilyTree { 

    private class FamilyTreeNode{ 
    private int identifier ; 
    private String Name ; 
    private FamilyTreeNode partner; 
    private FamilyTreeNode sibling; 
    private FamilyTreeNode child; 

} 

private FamilyTreeNode ancestor; 
private FamilyTreeNode currentNode ; 
private int indexNumber = 1; 



public FamilyTree(){ 
    this.ancestor = new FamilyTreeNode(); 
    this.ancestor.Name = Input.getString("Enter ancestors Name: ");  
    this.ancestor.identifier = 0; 
} 

public FamilyTreeNode addChild(){  
    //Set up variables and create new node 

    currentNode = ancestor; 
    boolean matchFound = false ; 
    FamilyTreeNode newFamilyNode = new FamilyTreeNode() ; 
    newFamilyNode.Name = Input.getString("Enter Name");  
    // 

    //Checking for existing Name   
    if(currentNode.child != null){ 
     currentNode = currentNode.child;   
     if(currentNode.Name.compareToIgnoreCase(newFamilyNode.Name) == 0){ 
      matchFound = true; 
     }  
     while(currentNode.sibling != null){ 
      currentNode = currentNode.sibling; 
      if(currentNode.Name.compareToIgnoreCase(newFamilyNode.Name) == 0){ 
       matchFound = true; 
      }    
     }  
    } 
    //  
    //Check for existing siblings, add to end of list 
    currentNode = ancestor; 

    if(currentNode.child == null){ 
     newFamilyNode.identifier = indexNumber; 
     currentNode.child = newFamilyNode ; 
    }else{ 
     currentNode = currentNode.child; 
     while (currentNode.sibling != null){     
      currentNode = currentNode.sibling;} 
      if(matchFound == false){    
       indexNumber++; 
       newFamilyNode.identifier = indexNumber; 
       currentNode.sibling = newFamilyNode; 
      } 
      else{     
       System.out.println("Name already exists"); 
      } 
     }   
    //  
    return newFamilyNode ; 
} 

public FamilyTreeNode addPartner(){ 
    currentNode = ancestor ; 
    FamilyTreeNode newPartnerNode = new FamilyTreeNode() ; 
    int currentNodeIdentifier; 
    int partnerIdentifier; 
    boolean insertPointFound = false ; 
    display(); 
    partnerIdentifier = Input.getInteger("Input partner ID"); 
    while(insertPointFound == false){ 
     if(partnerIdentifier == currentNode.identifier){ 


     }else{ 
      currentNode 
     } 


    } 



    return newPartnerNode; 


} 






public void display(){  
    currentNode = ancestor; 
    System.out.println(currentNode.Name + " " + currentNode.identifier); 
    if(currentNode.child != null){ 
     currentNode = currentNode.child; 
     System.out.println(currentNode.Name + " " + currentNode.identifier); 
      while(currentNode.sibling != null){ 
       currentNode = currentNode.sibling; 
       System.out.println(currentNode.Name + " " + currentNode.identifier); 
       } 

     } 
    } 
}

來源

2013-05-07 Shuma

注意：您描述的圖形只是「幾乎」一棵樹;總會有夫妻以及兄弟姐妹形成周期。另外，我不明白你的實際問題是什麼;你只是想遍歷家庭圖嗎？你想要某種遍歷的順序嗎？你想根據某些謂詞對其進行「排序」嗎？ – 2013-05-07 23:33:56

基本上，每個節點都有一個數字標識符，我希望能夠讓用戶輸入一個數字，搜索樹中的每個節點並將節點作爲子節點，兄弟節點或匹配節點的夥伴插入。 – Shuma 2013-05-07 23:42:49

您可以使用散列將標識符映射到節點，也可以使用圖遍歷（BFS/DFS）執行節點搜索。 – 2013-05-07 23:57:48

假設所有標識符是唯一的，您可以使用任何樹遍歷算法來實現搜索。這是一個可以解決您的問題的示例DFS（您可以根據需要修改此功能）。

boolean[] visited = new boolean[n]; // n is no. of nodes in the tree 

public FamilyTreeNode dfs(FamilyTreeNode root, int searchKey) { 
    if(root == null) { 
     return null; 
    } 
    if(root.identifier == searchKey) { 
     return root; 
    } 
    visited[root.identifier] = true; 
    FamilyTreeNode next = null; 
    if((root.partner != null) && (!visited[root.partner.identifier])) { 
     next = dfs(root.partner, searchKey); 
    } 
    if(next != null) return next; 
    if((root.sibling != null) && (!visited[root.sibling.identifier])) { 
     next = dfs(root.sibling, searchKey); 
    } 
    if(next != null) return next; 
    if((root.child != null) && (!visited[root.child.identifier])) { 
     next = dfs(root.child, searchKey); 
    } 
    return next; 
}

來源

2017-04-04 10:28:23 iavanish

Java：用於搜索節點樹狀結構的算法

回答

相關問題