实现二叉搜索树 - 包含方法

Question

我目前有3个类 - DictionaryApp，BSTSet和BSTNode - BSTSet和BSTNode都包含方法。

public class BSTSet <E extends Comparable<E>> extends AbstractSet <E> { 

    // the root of the supporting binary search tree 
    private BSTNode<E> root; 

    // number of elements in the set 
    private int count = 0; 


    public boolean isEmpty() { 
     return count == 0; 
    } 


    public boolean contains(E item) throws ClassCastException { 
     if(root == null) return false; 
     return root.contains(item); 
    } 

    public boolean add(E item) { 
     if (item == null) 
      throw new IllegalArgumentException("Null cannot be added to a BSTSet"); 
     if(contains(item))return false; 
     if(root == null){ 
      root = new BSTNode(item); 
      count++; 
      return true; 
     }else{ 
      root.add(item); 
      count++; 
      return true; 
     } 
    } 
} 


public class BSTNode <E extends Comparable<E>> { 

    private E value; 
    private BSTNode<E> left; 
    public BSTNode<E> right; 

    public BSTNode(E value) { 
    this.value = value; 
    } 

    public E getValue() { 
     return value; 
    } 

    public BSTNode<E> getLeft() { 
     return left; 
    } 

    public BSTNode<E> getRight() { 
     return right; 
    } 


    public boolean contains(E item) { 
     if(item.compareTo(value) == 0) return true; 
     if(left != null) left.contains(item); 
     if(right != null) right.contains(item); 
     // no matching node was found 
     return false; 

    } 

    public boolean add(E item) { 
     if(item.compareTo(value) < 0) {left = new BSTNode(item); return true;} 
     if(item.compareTo(value) > 0) {right = new BSTNode(item); return true;} 
     return false; 
    } 
} 

我的问题是，在BSTNode类中的包含方法永远不会返回true，我不明白为什么。如果您想再看到我的代码或需要更多信息，请随时询问。

Answer 1

在你BSTNode的contains方法，你无视left和right调用contains的结果。如果子节点发现它，立即返回true。另外，使用比较结果来确定下一个要搜索的孩子。

public boolean contains(E item) { 
    int comp = item.compareTo(value); 
    if(comp == 0) return true; 
    if(comp < 0 && left != null && left.contains(item)) return true; 
    if(comp > 0 && right != null && right.contains(item)) return true; 
    // no matching node was found 
    return false; 
} 

你add方法忽略可能已存在的任何子节点。首先测试他们的存在。如果它们不存在，则按照您已经在做的那样分配它。如果它们已经存在，则对该孩子递归地调用add。

public boolean add(E item) { 
    if(item.compareTo(value) < 0) { 
     if (left == null) left = new BSTNode(item); return true; 
     else return left.add(item); 
    } 
    if(item.compareTo(value) > 0) { 
     if (right == null) right = new BSTNode(item); return true; 
     else return right.add(item); 
    } 
    return false; 
}