ノードを追加中にバイナリ検索ツリーがスローするエラー

Question

私はJavaで書いたこのバイナリ検索ツリーを持っています。それは正常に動作しているようです。しかし、複数の呼び出しを呼び出すと、StackOverFlowエラーが発生します。私はJavaで書くことを学んでいます。誰かが私が間違っていることを教えてもらえますか？

public class TreeApp<E extends Comparable<E>> 
{ 
    private Node<E> root=null; 
    private int size=0; 

    private static class Node<E> 
    { 
     private E e; 
     private Node<E> left; 
     private Node<E> right; 
     private Node<E> parent; 

     public Node(E e,Node<E> parent,Node<E> left,Node<E> right) 
     { 
      this.e=e; 
      this.left=left; 
      this.right=right; 
      this.parent=parent; 
     } 

     public Node(E e) 
     { 
      this.e=e; 
     } 

     public E getE() { 
      return e; 
     } 

     public void setE(E e) { 
      this.e = e; 
     } 

     public Node<E> getLeft() { 
      return left; 
     } 

     public void setLeft(Node<E> left) { 
      this.left = left; 
     } 

     public Node<E> getRight() { 
      return right; 
     } 

     public void setRight(Node<E> right) { 
      this.right = right; 
     } 

     public Node<E> getParent() { 
      return parent; 
     } 

     public void setParent(Node<E> parent) { 
      this.parent = parent; 
     } 


    }//end of Node<E> class 

    public TreeApp() 
    { 

    } 

    public Node<E> createRoot(E e,Node<E> l,Node<E> r) 
    { 
     if(!(root==null)) 
     System.out.println("Root is already present"); 
     root=new Node<E>(e,root,l,r); 
     size++; 
     return root; 


    } 

    public Node<E> addNode(Node<E> left,E e) 
    { 

     //lets start with root 
     if(root==null) 
      createRoot(e,null,null); 
     Node<E> focusNode=root; 

     //Node<E> newLeft 
     Node<E> newNode=new Node<E>(e); 

     //while(true) 
     if(e.compareTo(focusNode.e) < 0) 
     { 
      if(focusNode.getLeft()==null) 
      { 
       focusNode.setLeft(newNode); 
       size++; 
      } 
      else 
      { 
       focusNode=focusNode.getLeft(); 
       //addNode(focusNode,e); 
      } 

     }else if(e.compareTo(focusNode.e) >= 0) 
     { 
      if(focusNode.getRight()==null) 
      { 
       focusNode.setRight(newNode); 
       size++; 
      } 
      else 
      { 
       focusNode=focusNode.getRight(); 

       //addNode(focusNode,e); 
      } 
     } 
     return focusNode; 
    } 

    public void preorderTraverseTree(Node<E> focusNode) { 

     if (focusNode != null) { 

      System.out.println("starting traversal: " + focusNode.getE()); 

      preorderTraverseTree(focusNode.getLeft()); 
      preorderTraverseTree(focusNode.getRight()); 

     } 

    } 

    public String toString() { 
     if (root == null) { 
      return ""; 
     } else { 
      return root.toString(); 
     } 
     } 

    public static void main(String args[]) 
    { 
     //Node<String> p=new Node<String>(); 
     TreeApp<String> ta=new TreeApp<String>(); 
     System.out.println("size before: " + ta.size); 

     ta.createRoot("3",null,null); 
     Integer i=1; 
     Integer j=2; 
     System.out.println("comparison " + i.compareTo(j)); 
     //System.out.println("size after: " + ta.size); 
     ta.addNode(ta.root,"2"); 
     ta.addNode(ta.root,"4"); 
     ta.addNode(ta.root,"1"); 
     ta.addNode(ta.root,"6"); 

     //ta.addNode(ta.root,"5"); 
     ta.preorderTraverseTree(ta.root); 
     //System.out.println("size after: " + ta.size); 



    } 

} 

Answer 1

stackoverflowのがため、ルートノードを優先して無視さleft引数によって引き起こさ無限再帰ループの起こります。

ルートノード3にすでに左の子2と右の子4があるため、ノード1を追加するとエラーが発生します。したがって、ノード1を左または右として試して追加する再帰呼び出しを行いますノード2の子であるが、方法に再び入ると、ノード2を無視して、ルートノード3の下にノード1を再び収めようと試み、これが継続して行われる。

public Node<E> addNode(Node<E> left, E e) { 
    //lets start with root 
    // if (root == null) 
    //  createRoot(e, null, null); 
    // Node<E> focusNode = root;  // <-- wrong 
    Node<E> focusNode = left;   // <-- correct 

    //Node<E> newLeft 
    Node<E> newNode = new Node<E>(e); 

    //while(true) 
    if (e.compareTo(focusNode.e) < 0) { 
     if (focusNode.getLeft() == null) { 
      focusNode.setLeft(newNode); 
      size++; 
     } else { 
      focusNode = focusNode.getLeft(); 
      addNode(focusNode,e);  // <-- uncomment this line 
     } 

    } else if (e.compareTo(focusNode.e) >= 0) { 
     if (focusNode.getRight() == null) { 
      focusNode.setRight(newNode); 
      size++; 
     } else { 
      focusNode = focusNode.getRight(); 
      addNode(focusNode,e);  // <-- uncomment this line 
     } 
    } 
    return focusNode; 
}