Java - Arbre généalogique binaire - Impossible de trouver un nœud

Question

Je travaille sur une tâche qui me demande d'entrer et d'afficher un arbre généalogique, en le convertissant d'abord en un arbre binaire - l'enfant est à gauche, et les frères et sœurs sont sur la droite. Je comprends les arbres, les arbres traversés et la façon de rechercher certains noeuds en utilisant des méthodes pré-, in- et post-order.

J'ai écrit du code pour insérer un nouveau noeud, trouver un noeud et imprimer l'arbre entier, mais ma méthode findNode ne fonctionne pas correctement. J'en ai besoin pour chercher dans l'arbre en utilisant la pré-commande, et retourner le nœud qu'il recherche. Actuellement, la méthode récursive fait tout le chemin en bas à gauche (enfant le plus bas), et en bas à droite de l'enfant le plus bas (frère le plus bas), mais elle ne remonte jamais au nœud d'origine.

Voici le code pour mon FamilyTree et les classes principales:

public class FamilyTree 
{ 
Node root; 

// Initialize tree 
public FamilyTree() 
{ 
    root = null; 
} 


// -------------------------------------------------------------- 
// This method inserts a new family member into the tree. 
// It takes two parameters - the parent who the new node should 
// be inserted under, and the name of the new member being added. 
// -------------------------------------------------------------- 

public void insertNode(String par, String name) 
{ 
    Node parent, current; 
    Node newMember = new Node(name); 

    // If tree is empty, then the new member becomes the root 
    if(root == null) 
     root = newMember; 


    // If adding a sibling to the root, insert to root's right child 
    else if(par == "") 
    { 
     // Check if root's sibling is empty 
     if(root.rightChild == null) 
      root.rightChild = newMember; 


     // Traverse root's siblings until end, then insert at end 
     else 
     { 
      current = root; 

      while(current.rightChild != null) 
       current = current.rightChild; 

      current.rightChild = newMember; 
     } 
    } 

    else 
    { 
     // Find the parent where we will insert under 
     parent = findNode(par, root); 

     System.out.println("parent is = " + parent); 
     System.out.println("newMember is = " + newMember + "\n"); 

     // If that parent doesn't exist, print error msg 
     if (parent == null) 
      System.out.println("Parent doesn't exist"); 


     // If parent does exist, but has no left child, 
     // then the new member becomes left child 
     else if(parent.leftChild == null) 
      parent.leftChild = newMember; 


     // If parent already has a left child, then traverse 
     // to the end of it's left children and insert node 
     else 
     { 
      current = parent.leftChild; 

      while(current.rightChild != null) 
       current = current.rightChild;    

      current.rightChild = newMember; 
     } 
    } 
} 


// ------------------------------------------------------------ 
// This method recursively finds a node in the family tree, 
// given the name of the node to look for, and the tree. 
// It is run pre-order, and, if found, returns the node 
// ------------------------------------------------------------ 

public Node findNode(String name, Node localTree) 
{ 
    Node current = localTree; 

    // Visit the node 
    if(current.name == name) 
     return current; 

    // Pre-order - go left 
    if(current.leftChild != null) 
    { 
     System.out.println("going left to " + current.leftChild); 
     return findNode(name, current.leftChild); 
    } 

    // Pre-order - go right 
    if(current.rightChild != null) 
    { 
     System.out.println("going right to " + current.rightChild); 
     return findNode(name, current.rightChild); 
    } 


    return null; 
} 

// ------------------------------------------------------------ 
// This method prints the family tree, given a parent name 
// and a tree to print from. It will attempt to find the parent 
// node with the given name, then print the entire tree 
// (all children and grandchildren) from that point. 
// ------------------------------------------------------------ 

public void printTree(String par, Node localTree) 
{ 
    Node parent, current; 

    // Find the parent to start printing from 
    parent = findNode(par, root); 
    System.out.println("parent= " + parent); 

    // If parent doesn't exist, print error msg 
    if (parent == null) 
     System.out.println(par + " doesn't exist."); 

    else 
    { 
     current = localTree; 

     System.out.println(current); 

     if(current.leftChild != null) 
      printTree(par, current.leftChild); 

     else if(current.rightChild != null) 
      printTree(par, current.rightChild); 
    } 

} 

public class Node 
{ 
    Node leftChild, rightChild; 
    String name; 

    public Node(String n) 
    { 
     leftChild = null; 
     rightChild = null; 
     name = n; 
    } 

    public String toString() 
    { 
     return name; 
    } 
} 

}

public class Main 
{ 
public static void main (String[] args) 
{ 
    FamilyTree myTree = new FamilyTree(); 

    myTree.insertNode("", "Grandma Marx"); 
    myTree.insertNode("", "Great-Aunt Peggie"); 
    myTree.insertNode("", "Great-Aunt Katherine"); 
    myTree.insertNode("Grandma Marx", "Aunt Sarah"); 
    myTree.insertNode("Grandma Marx", "Aunt Tory"); 
    myTree.insertNode("Grandma Marx", "Uncle Frank"); 
    myTree.insertNode("Grandma Marx", "Uncle Charles"); 
    myTree.insertNode("Grandma Marx", "Mom");  

    myTree.insertNode("Aunt Sarah", "Morgan"); 
    myTree.insertNode("Aunt Sarah", "Tommy"); 
    myTree.insertNode("Aunt Sarah", "Austin"); 
    myTree.insertNode("Aunt Sarah", "Luke"); 

    myTree.insertNode("Aunt Tory", "Tim"); 

    myTree.insertNode("Mom", "Barret"); 
    myTree.insertNode("Mom", "Jeremy"); 
    myTree.insertNode("Mom", "Elliot"); 


    //myTree.printTree("Grandma Marx", myTree.findNode("Grandma Marx", myTree.root)); 
} 

}

Answer 1

Le problème est avec votre return prématuré de la recherche:

public Node findNode(String name, Node localTree) 
{ 
... 
    // Pre-order - go left 
    if(current.leftChild != null) 
    { 
     System.out.println("going left to " + current.leftChild); 
     return findNode(name, current.leftChild); // <===== HERE! 
    } 
... 
} 

Cela provoque la fin de la fonction après que le sous-arbre gauche a été traversé, même si le résultat est null, c'est-à-dire qu'aucun noeud n'a été trouvé.

Que diriez-vous quelque chose comme ceci:

public Node findNode(String name, Node localTree) 
{ 
    Node current = localTree; 

    // Visit the node 
    if(current.name.equals(name)) 
     return current; 

    // Pre-order - go left 
    if(current.leftChild != null) 
    { 
     System.out.println("going left to " + current.leftChild); 
     Node nodeFound = findNode(name, current.leftChild); 
     if (nodeFound != null) { 
      // Only return from findNode if we have already found what we're looking for. 
      return nodeFound; 
     } 
    } 

    // Pre-order - go right 
    if(current.rightChild != null) 
    { 
     System.out.println("going right to " + current.rightChild); 
     return findNode(name, current.rightChild); 
    } 

    return null; 
} 

En outre, en Java, vous ne devez jamais utiliser == pour comparer des chaînes. Cela ne fonctionnera pas correctement. Avec Strings, utilisez toujours String.equals(...). Voir le code ci-dessus par exemple, et this SO question.