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を参照してください。