2010-09-17 191 views
0

我一直在使用一个驱动程序来测试我的一个数据结构(二叉搜索树),我遇到过这个问题。 - 当我向bst插入2个以上的对象时发生 - 我正在尝试做的事情是:我将4个对象插入树中,然后删除2个对象,然后打印出我的find方法,以显示是否不是它找到我要求的对象。例如:空指针异常

public class Driver5 { 

public static void main(String[] args) { 
    Integer c1 = new Integer(1); 
    Integer c2 = new Integer(2); 
    Integer c3 = new Integer(3); 
    Integer c4 = new Integer(4); 
    Integer c5 = new Integer(5); 
    Integer c6 = new Integer(6); 
    Integer c7 = new Integer(7); 
    Integer c8 = new Integer(8); 
    Integer c9 = new Integer(9); 
    Integer c10 = new Integer(10); 
    Integer c11 = new Integer(11); 
    Integer c12 = new Integer(23); 
    Integer c13 = new Integer(65); 
    Integer c14 = new Integer(45); 
    Integer c15 = new Integer(18); 
    Integer c16 = new Integer(33); 
    Integer c17 = new Integer(54); 

    DataStructure1<Integer> theData = new DataStructure1<Integer>(); 
    System.out.println("DS1");  
    long start = System.currentTimeMillis(); 
    theData.insert(c1); 
    theData.insert(c2); 
    theData.insert(c3); 
    theData.insert(c4); 
    theData.insert(c5); 
    theData.insert(c6); 
    theData.insert(c7); 
    theData.insert(c8); 
    theData.insert(c9); 
    theData.insert(c10); 
    theData.insert(c11); 
    theData.insert(c12); 
    theData.insert(c13); 
    theData.insert(c14); 
    theData.insert(c15); 
    theData.insert(c16); 
    theData.insert(c17); 
    theData.delete(c2); 
    theData.delete(c4); 
    System.out.println(theData.find(c1)); 
    System.out.println(theData.find(c2)); 
    System.out.println(theData.find(c3)); 
    System.out.println(theData.find(c4)); 
    theData.delete(c2); 
    theData.insert(c3); 
    System.out.println(theData.find(c2)); 
    System.out.println(theData.find(c3)); 
    System.out.println(theData.find(c4)); 
    System.out.println(theData.find(c5)); 
    System.out.println(theData.find(c6)); 
    System.out.println(theData.find(c7)); 
    System.out.println(theData.find(c8)); 
    System.out.println(theData.find(c9)); 
    System.out.println(theData.find(c10)); 
    System.out.println(theData.find(c11)); 
    System.out.println(theData.find(c12)); 
    System.out.println(theData.find(c13)); 
    System.out.println(theData.find(c14)); 
    System.out.println(theData.find(c15)); 
    System.out.println(theData.find(c16)); 
    System.out.println(theData.find(c17)); 

    long elapsed = System.currentTimeMillis() - start; 
    System.out.println("The time elapsed was: " + elapsed + " ms."); 
    System.out.println(); 

BinarySearchTree<Integer> theData1 = new BinarySearchTree<Integer>(); 
    System.out.println("BST");  
    long start1 = System.currentTimeMillis(); 
    theData1.insert(c1); 
    theData1.insert(c2); 
    theData1.insert(c3); 
    theData1.insert(c4); 
    theData1.insert(c5); 
    theData1.insert(c6); 
    theData1.insert(c7); 
    theData1.insert(c8); 
    theData1.insert(c9); 
    theData1.insert(c10); 
    theData1.insert(c11); 
    theData1.insert(c12); 
    theData1.insert(c13); 
    theData1.insert(c14); 
    theData1.insert(c15); 
    theData1.insert(c16); 
    theData1.insert(c17); 
    theData1.delete(c2); 
    theData1.delete(c4); 
    System.out.println(theData1.find(c1)); 
    System.out.println(theData1.find(c2)); 
    System.out.println(theData1.find(c3)); 
    System.out.println(theData1.find(c4)); 
    theData1.delete(c2); 
    theData1.insert(c3); 
    System.out.println(theData1.find(c2)); 
    System.out.println(theData1.find(c3)); 
    System.out.println(theData1.find(c4)); 
    System.out.println(theData1.find(c5)); 
    System.out.println(theData1.find(c6)); 
    System.out.println(theData1.find(c7)); 
    System.out.println(theData1.find(c8)); 
    System.out.println(theData1.find(c9)); 
    System.out.println(theData1.find(c10)); 
    System.out.println(theData1.find(c11)); 
    System.out.println(theData1.find(c12)); 
    System.out.println(theData1.find(c13)); 
    System.out.println(theData1.find(c14)); 
    System.out.println(theData1.find(c15)); 
    System.out.println(theData1.find(c16)); 
    System.out.println(theData1.find(c17)); 

    long elapsed1 = System.currentTimeMillis() - start1; 
    System.out.println("The time elapsed was: " + elapsed1 + " ms."); 




} 


} 

我在BST得到一个错误的位置:

if(nd.getLeft() == null && nd.getRight() == null) 
     { 

      nd = null; 
     } 

全删除是:

public void delete(E item) { 

     TreeNode<E> nd = root; 

     while(nd != null && nd.getItem().compareTo(item) != 0) 
     { 
      if(nd.getItem().compareTo(item) < 0) 
       nd = nd.getRight(); 

      else 
       nd = nd.getLeft(); 
     } 

     if(nd.getLeft() == null && nd.getRight() == null) 
     { 

      nd = null; 
     } 

     else if(nd.getLeft() != null && nd.getRight() == null) 

     { 
      nd.setItem((E)nd.getLeft().getItem()); 

     } 
     else if(nd.getLeft() == null && nd.getRight() != null) 
     {  
      nd.setItem((E)nd.getRight().getItem()); 

     } 

     else if(nd.getLeft() != null && nd.getRight() != null) 
     { 

      nd.setItem((E)findsucc(nd)); 
     }  


} 

回答

2

如果ndnull,那么你不能打电话给getLeft()就可以了。因此,请您检查

if (nd != null && nd.getLeft() == null && nd.getRight() == null) 

all causes of a NullPointerException,以便下次你遇到它的时候,你知道该怎么做,立即。

0

nd必须是空的某些原因。在打电话给getLeft()getRight()之前检查它。

+0

了解了很久很久以前我应该知道的一些新东西,非常感谢您的帮助 – user450267 2010-09-17 06:33:17

+0

@ user450267如果答案适合您,请将其标记为已接受(在投票计数器下面打钩) – Bozho 2010-09-17 06:34:11