TreeSet/Contains方法

Question

作为练习，我尝试实现我自己的TreeSet。在编码添加和删除方法之前，我更喜欢从容器开始，这似乎更容易，但我卡住了。

我的树由具有Node和Leaf：

static class Leaf<E extends Comparable<E>> implements Tree<E> { 

       //stuff 
     @Override 
     public boolean contains() { 
      return false; 
     } 

} 

这里的Node类：

static class Node<E extends Comparable<E>> implements Tree<E> { 

    private final E value; 
    private Tree<E> left; 
    private Tree<E> right; 

    //some stuff 
    @Override 
    public boolean contains(E elem) { 
     //here i'm blocked 
    } 
} 

我怎样才能到我的树说，寻找到它的很大一部分（左或正确）与元素？

Answer 1

使用递归性！

正如你所看到的，Leaf对象组成了Tree的末尾，所以它将成为方法的停止条件。

您可以看到将存放在Tree中的对象必须实现Comparable。因此，含有可以是这样的：

@Override 
public boolean contains(E elem) { 
    int compare = elem.compareTo(value); //here we compare the element with 
             //the compareTo method that the objects 
             //used must redefined 

    if(compare==0) 
      return true; //here the current node contains elem ! 
     else if(compare < 0) 
      return left.contains(elem); //elem is inferior than the elem present in the current node hence we look into the left part of the tree 
     else 
      return right.contains(elem); //elem is superior than the elem present in the current node hence we look into the right part of the tree 
    } 

正如你所看到的，如果元素不存在于Tree，我们将在一个Leaf末，它将返回false。

您可以实现相同的逻辑进行编码add和remove

Answer 2

我怎样才能到我的树说，寻找到它的很大一部分与元素（左或右）？

那么，你需要使用compareTovalue比较elem。如果结果为0，则值已经相等，并且您可以返回true。

如果elem小于value，则可以递减为left.contains(elem)，否则递归为right.contains(elem)。如果left或right的值只是一个叶，那么将返回false，否则它会适当地递减。