TreeSet / Contains方法

Question

作为练习，我尝试实现我自己的TreeSet。在编写add和remove方法之前，我更喜欢start by contains，它看起来更简单，但我被卡住了。

我的树由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。因此，contains可能如下所示：

@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

我怎样才能告诉我的树用元素查看它的好的部分(左或右)？

那么，您需要使用compareTo来比较elem和value。如果结果为0，则两个值已经相等，您可以返回true。

如果elem小于value，则可以递归到left.contains(elem)，否则递归到right.contains(elem)。如果left或right值只是一个叶，那么它将返回false，否则它将相应地向下递归。