java - Java：搜索节点树结构的算法

Question

我正在使用 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);
                }   

        }
    }
}

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