자바 : 노드의 트리 구조 검색 알고리즘

Question

자바의 "패밀리 트리"프로그램에서 일하고있는 Im이 노드를 검색하기 위해 알고리즘을 고민하는 데 어려움을 겪고 있습니다.

노드는 이름과 파트너, 형제, 자식 및 정수 식별자에 대한 링크로 구성됩니다.

알고리즘은 내가 막 다른 골목에 닿았을 때 올바른 방향으로 조금 움직여 주셔서 감사하게 생각합니다.

기본적으로 각 노드에는 숫자 식별자가 있습니다. 사용자가 숫자를 입력하고 트리의 각 노드를 검색하여 해당 노드의 자식, 형제 또는 파트너로 노드를 삽입 할 수 있기를 원합니다. 트리 구조의 예 :이 할당 그대로

주, 나는 구조

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); 
       } 

     } 
    } 
} 

Answer 1

을, 트리 탐색 알고리즘을 사용하여 검색을 수행 할 수 있습니다. 다음은 문제를 해결할 수있는 샘플 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; 
}