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，否則它會適當地遞減。