二元搜索樹在添加節點時拋出錯誤

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

的計算器是因爲一個無限遞歸循環，引起left參數有利於根節點的被忽略的。

在添加節點1時發生錯誤，因爲根節點3已經有一個左側子節點2和右側子節點4.因此，該方法執行遞歸調用，嘗試將節點1添加爲左側或右側但是當它重新進入該方法時，它會忽略節點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; 
}