使用 comparable 或 comparator 实现 BST

Question

我正在尝试创建一个通用 BinarySearchTree<T> class。我想提供两个选项（构造函数），

实现Comparable<T>的泛型class的空构造函数，即如果Dog是实现Comparable<Dog>的class，那么:

BinarySearchTree<Dog> bst = new BinarySearchTree<Dog>();
为不需要实现 Comparable<T> 的通用 class 传递 Comparator<T>，即如果 Dog 是class（未实现 Comparable<Dog>）和 DogComp 是实现 Comparator<Dog> 然后
的 class
BinarySearchTree<Dog> bst = new BinarySearchTree<Dog>(new DogComp());

我的 BinarySearchTree class 中有一个比较器字段。对于空的构造函数，我将创建新的比较器。如果通过比较器，我将简单地将其分配给那个比较器字段。

我应该如何声明 class 和构造函数？

Answer 1

撇开用于决定在何处插入节点的实际逻辑，这就是您可以执行的操作：

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 检查，如果您的数据未实现可比较或比较器，则抛出异常。

Answer 2

我想改进机器人的回答：

使BinarySearchTree class 抽象，使用抽象compare 方法。然后两个内部静态具体 classes 可以实现这两种方案。提供两种构造方法，而不是构造函数，例如：

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();
}

这样 class 的其余部分就可以只使用您的 compare(one, other) 方法，而不用关心结果是来自比较器还是自然元素顺序。

您可能已经注意到我将 comp 指定为 Comparator<? super E>。这意味着比较器是逆变。这使您的搜索树更加灵活，因为这样您就可以放入任何能够比较 E 对象的比较器，即使比较器仅比较 F 对象，其中 F 是 E.[=15= 的 superclass ]

使用 comparable 或 comparator 实现 BST

Implement BST using comparable or comparator

java

comparator

comparable