Java: Algorithm for Searching Tree Structure of Nodes

Question

Im working on a "family tree" program in java, and I am having trouble wrapping my head around an algorithm for searching through the nodes.

A node consists of a Name, and link to a partner, sibling, child and an integer identifier.

The algorithms I am trying just hit dead ends and I would be extremely grateful for a nudge in the right direction.

Basically, with each node having a a numerical identifier, I want to be able to have the user enter a number, search each node in the tree and insert a node as a child, sibling or partner of the matching node. Tree structure example:

Note, as it is an assignment I cannot change the structure

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

FamilyTree Class:

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

        }
    }
}

Note: the graph you describe is only "almost" a tree; there are always cycles formed by couples as well as by siblings. Also, I don't see what your actual question is; do you just want to traverse the family graph? Do you want some sort of order for a traversal? Do you want to "sort" it according to some predicate? — G. Bach
Basically, with each node having a a numerical identifier, I want to be able to have the user enter a number, search each node in the tree and insert a node as a child, sibling or partner of the matching node. — Shuma
You can either use hashing to map identifiers to nodes, or you can do a search for the node using graph traversal (BFS/DFS). — G. Bach
One issue is that you are going to have is that you are setting up your tree to only allow nodes to have one child. You might consider using an arrayList to hold as many children as needed. This will also allow you to search the children easier. Here is a link to a binary tree, which you can modify to a full tree. github.com/BlaineOmega/BinarySearchTree — BlackHatSamurai
Thanks for the reply, but as this is part of an assignment I cannot change the structure. — Shuma

iavanish iavanish · Accepted Answer · 2017-04-04T10:28:23

Assuming that all the identifiers are unique, you can achieve searching using any tree traversal algorithm. Here is a sample DFS that would solve your problem (you can modify this function as per your requirement).

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

Java: Algorithm for Searching Tree Structure of Nodes

1 Answers