二进制搜索树，用对象遍历列表

Question

我有一个问题在我的树中漫步，并检查所有项目以查看树是否包含该项目。我必须用Object来做...有没有人可以帮忙？

testSet.clear(); 
    testSet.add(10); 
    testSet.add(20); 
    testSet.add(30); 
    testSet.add(40); 
    testSet.add(15); 
    testSet.add(25); 
    testSet.add(5); 
    testSet.add(1); 
    assertFalse("contains must return false for the element 80", testSet.contains(80)); 
    assertFalse("contains must return false for the element 3", testSet.contains(3)); 
    assertTrue("contains must return true for the element 10", testSet.contains(10)); 
    assertTrue("contains must return true for the element 5", testSet.contains(5)); 
    assertTrue("contains must return true for the element 1", testSet.contains(1)); 
    assertTrue("contains must return true for the element 20", testSet.contains(20)); 
    assertTrue("contains must return true for the element 25", testSet.contains(25)); 
    assertTrue("contains must return true for the element 40", testSet.contains(40));  
    testSet.clear(); 
    assertFalse("contains must return false for any element after a clear", testSet.contains(10)); 

我收到错误： assertTrue（ “包含必须的元素20返回true”，testSet.contains（20））;

public boolean contains(Object o) 
{ 
    if (o == null) 
    { 
     throw new NullPointerException("Null Items are not allowed in the Tree"); 
    } 
    Node cur = root; 
    for(int i =0; i <size -1; i++) 
    { 
    if(cur.item.equals(o)) 
      { 

       return true; 
      } 
      if(!cur.item.equals(o)) 
      { 
      cur=cur.lChild; 

       if (cur.item.equals(o)) 
       { 
       return true; 
       } 
       if (!cur.item.equals(o)) 
       { 
        cur=cur.lChild; 
       } 
       if (cur.item.equals(o)) 
       { 
        return true; 
       } 
       else 
       { 
        return false; 
       } 

      } 


     else{ 
       cur = cur.rChild; 
       if(cur.item.equals(o)) 
       { 
        return true; 
       } 
       if (!cur.item.equals(o)) 
       { 
        cur=cur.rChild; 
        if (cur.item.equals(o)) 
        { 
         return true; 
        } 
        else 
        { 
         return false; 
        } 
       } 
     } 




     } 
    return true; 
} 

} 

Answer 1

首先，你需要确定是否cur小于或大于o较大时cur不等于o。这意味着你不能使用Object，而需要使用Comparable。功能compareTo(T anotherObject)可以告诉你哪里的物体较小，大于或等于anotherObject。当cur小于o时，您需要向左走，否则向右走。

此外，您需要递归搜索它，这意味着当您停下来时，您需要调用函数本身，如contains(cur.lChild)或contains(cur.rChild)。

你contains函数应该是这样的：

public boolean contains(Comparable o) { 
    if (o == null) { 
     throw new NullPointerException("Null Items are not allowed in the Tree"); 
    } 
    Node cur = this; 
    for (int i = 0; i < size - 1; i++) { 
     if (cur.item.compareTo(o) == 0) { 
      return true; 
     } else if (cur.item.compareTo(o) < 0) { 
      cur = cur.lChild; 
     } else { 
      cur = cur.rChild; 
     } 
     return cur.contains(o); 
    } 
    return true; 
}