Java - Двоичное семейное древо - Не удается найти узел

Question

Я работаю над назначением, которое требует от меня ввода и отображения генеалогического дерева, сначала преобразуя его в двоичное дерево - ребенок слева, а братья и сестры - справа. Я понимаю деревья, пересекающие деревья и как искать определенные узлы с использованием методов предварительной, ин-и послепорядка.

Я написал код, чтобы вставить новый узел, найти узел и распечатать все дерево, однако мой метод findNode работает неправильно. Мне нужно, чтобы он искал дерево, используя предварительный заказ, и возвращаю узел, который он ищет. В настоящее время рекурсивный метод делает это до самого нижнего левого (младший ребенок) и нижнего нижнего правого нижнего (самого низкого), но он никогда не возвращается к исходному узлу, из которого я звонил, - следовательно, нарушая рекурсию.

Вот код для моего FamilyTree и основных классов:

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

Проблема с вашей преждевременной return из поиска:

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! 
    } 
... 
} 

Это приводит к тому, что функция заканчивается после того, как левое поддерево было пройдено, даже если результат равен null, то есть ни один узел не найден.

Как о чем-то вроде этого:

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

Кроме того, в Java вы никогда не должны использовать == для сравнения строк. Это не сработает. С помощью строк всегда используйте String.equals(...). См., Например, код выше, и this SO question.