java - TreeSet/包含方法

Question

作为练习，我尝试实现自己的 TreeSet。在编写添加和删除方法之前，我更喜欢从 contains 开始，这看起来更容易，但我陷入了困境。

我的树由节点和叶子组成:

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代码实现相同的逻辑