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：用于搜索节点树状结构的算法

回答

相关问题