使用可比较的或比较器来实施BST
我试图创建一个通用的BinarySearchTree<T>类。 我想提供两个选项（构造函数），
实现Comparable<T>的泛型类的空构造函数，即如果Dog是实现Comparable<Dog> ，则：
BinarySearchTree<Dog> bst = new BinarySearchTree<Dog>();
为Comparator<T>传递一个不需要实现Comparable<T>的泛型类，即如果Dog是一个类（没有实现Comparable<Dog> ），并且DogComp是一个实现Comparator<Dog>的类，那么
BinarySearchTree<Dog> bst = new BinarySearchTree<Dog>(new DogComp());
我在我的BinarySearchTree类中有一个Comparator字段。 对于空的construuctor，我会创建新的比较。 如果比较器已通过，我将简单地将其分配给该比较器字段。
我应该如何声明类和构造函数？
我想提高机器人的答案：
使用抽象compare方法使BinarySearchTree类抽象化。 然后两个内部静态混凝土类可以实现这两种方案。 而不是构造函数，提供两种构建方法，如：
public static <E> BinarySearchTree<E> create(Comparator<? super E> comp) {
return new ComparatorSearchTree(comp);
}
public static <E extends Comparable<E>> BinarySearchTree<E> create() {
return new ComparableSearchTree();
}
这样，类的其他部分就可以使用比较（one，other）方法，而不必关心结果是来自比较器还是自然元素顺序。
您可能已经注意到我将comp指定为Comparator<? super E> Comparator<? super E> 。 这意味着比较器是逆变的。 这使得您的搜索树更加灵活，因为这样您可以将任何比较器放入能够比较E对象的比较器中，即使比较器仅比较F是E的超类的F对象。
撇开将用于决定在哪里插入节点的实际逻辑，这是你可以做的：
public class BinarySearchTree<T> {
private Node root;
private Comparator<T> comparator;
public BinarySearchTree() {
}
public BinarySearchTree(Comparator<T> comparator) {
this.comparator = comparator;
}
public void insert(T obj) {
// binary search tree logic for deciding where to insert the node
// Create a Node
// ....
// comparison of two nodes
if (obj instanceof Comparable) {
// compare using Comparable
} else if (comparator != null) {
// compare using Comparator
} else {
//objects cannot be compared
}
}
/*Represents a node for the tree */
private class Node {
T obj;
Node left;
Node right;
public Node(T obj) {
super();
this.obj = obj;
}
}
}
还要注意，如果您的数据没有实现可比较性或比较性，您可以在构造函数本身中添加该检查，而不是对每个新插入检查instanceOf，并抛出异常。
链接地址: http://www.djcxy.com/p/91933.html