0

作为练习，我尝试实现自己的TreeSet. 在编写 add 和 remove 方法之前，我更喜欢从 contains 开始，这似乎更容易，但我被卡住了。

我的树由Nodeand组成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
   }
}

我怎么能对我的树说用元素查看它的好部分（左或右）？

4

2 回答 2

2

使用递归！

如您所见，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

于 2013-05-08T11:38:10.337 回答
2

我怎么能对我的树说用元素查看它的好部分（左或右）？

好吧，您需要elem与valueusing进行比较compareTo。如果结果为 0，则值已经相等，您可以返回true.

如果elem小于value，则可以递归成left.contains(elem)，否则递归成right.contains(elem)。如果leftorright值只是一个叶子，那将返回false，否则它将适当地向下递归。

于 2013-05-08T11:39:12.043 回答