Java 泛型：compareTo 和“capture#-of ?”

Question

我正在尝试编写 BinaryTree 的实现，其对象可以是实现 Comparable 的任何类型。但是，我意识到这不会完全奏效。例如，A String 和 Double 不能插入到同一棵树中，即使它们都实现了 Comparable。

所以，我想知道是否可以编写代码，使 BinaryTree 可以用任何类型实现 Comparable 的值实例化，但是添加到树中的任何后续元素都必须共享与根的值相同的超类型。

这是我目前的代码：

public class BinaryTree {

    private Node root;

    public BinaryTree() {

        this.root = null;
    }

    public Node lookup(Comparable<Object> value) {

        return lookup(this.root, value);
    }

    private Node lookup(Node node, Comparable<Object> value) {

        Node match = null;

        if (match != node) {

            if (value == node.value) {
                match = node;
            } else if (value.compareTo(node.value) < 0) {
                return lookup(node.left, value);
            } else {
                return lookup(node.right, value);
            }
        }

        return match;
    }

    public Node lookupNonRecursively(Comparable<Object> value) {

        return lookupNonRecursively(this.root, value);
    }

    private Node lookupNonRecursively(Node node, Comparable<Object> value) {

        Node match = null;

        if (match != node) {

            if (value == node.value) {
                match = node;
            } else {

                Node root = node;
                boolean found = false;

                while (!found && root != null) {

                    if (root.value.compareTo(value) < 0) {

                        if (root.left == null) {

                            root.left = match = new Node(value);
                            found = true;
                        } else {
                            root = root.left;
                        }
                    } else {
                        if (root.right == null) {

                            root.right = match = new Node(value);
                            found = true;
                        } else {
                            root = root.right;
                        }
                    }
                }
            }
        }

        return match;
    }

    public Node insert(Comparable<Object> value) {

        return insert(this.root, value);
    }

    private Node insert(Node node, Comparable<Object> value) {

        if (node == null) {
            node = new Node(value);
        } else {
            if (node.value.compareTo(value) <= 0) {
                insert(node.left, value);
            } else {
                insert(node.right, value);
            }
        }

        return node;
    }

    public Node insertNonRecursively(Comparable<Object> value) {

        return insertNonRecursively(this.root, value);
    }

    private Node insertNonRecursively(Node node, Comparable<Object> value) {

        if (node == null) {
            node = new Node(value);
        } else {

            Node root = node;
            boolean inserted = false;

            while (!inserted) {

                if (node.value.compareTo(root.value) < 0) {

                    if (root.left == null) {
                        root.left = node = new Node(value);
                        inserted = true;
                    } else {
                        root = root.left;
                    }
                } else {
                    if (root.right == null) {
                        root.right = node = new Node(value);
                        inserted = true;
                    } else {
                        root = root.right;
                    }
                }
            }
        }

        return node;
    }

    public static class Node {

        private Node left;
        private Node right;
        private Comparable<Object> value;

        public Node(Comparable<Object> value) {

            this.left = null;
            this.right = null;
            this.value = value;
        }
    }
}

作为测试，如果我尝试运行代码如下，这将抛出错误 The method insert(Comparable<Object>) in the type BinaryTree is not applicable for the arguments (Integer)：

BinaryTree tree = new BinaryTree();
tree.insert(new Integer(1));

您可以看到我为此 class 实现了一些不同的 BinaryTree 方法，但需要应用相同的规则：传递给 lookup() 或 [=20 的任何值=] 还需要共享根的超类型。我有一种感觉，这就是 <T extends Comparable<? super T>> 的某些变体将发挥作用的地方，但我只是想不出这个。

关于如何实现此目标的任何想法？

如@jp-jee 所述，这是我的解决方案（还修复了未经测试的第一次尝试的逻辑和其他错误），效果很好：

public class BinaryTree<T extends Comparable<T>> {

    private Node<T> root;

    public BinaryTree() {

        this.root = null;
    }

    public Node<T> lookup(T value) {

        return lookup(this.root, value);
    }

    private Node<T> lookup(Node<T> node, T value) {

        Node<T> match = null;

        if (match != node) {

            if (value.equals(node.value)) {
                match = node;
            } else if (value.compareTo(node.value) < 0) {
                return lookup(node.left, value);
            } else {
                return lookup(node.right, value);
            }
        }

        return match;
    }

    public Node<T> lookupNonRecursively(T value) {

        return lookupNonRecursively(this.root, value);
    }

    private Node<T> lookupNonRecursively(Node<T> node, T value) {

        Node<T> match = null;

        if (match != node && value != null) {

            if (value.equals(node.value)) {
                match = node;
            } else {

                Node<T> searchRoot = node;
                boolean found = false;

                while (!found && searchRoot != null) {

                    if (value.equals(searchRoot.value)) {
                        match = searchRoot;
                        found = true;
                    } else if (value.compareTo(searchRoot.value) < 0) {
                        searchRoot = searchRoot.left;
                    } else {
                        searchRoot = searchRoot.right;
                    }
                }
            }
        }

        return match;
    }

    public void insert(T value) {

        this.root = insert(this.root, value);
    }

    private Node<T> insert(Node<T> node, T value) {

        if (node == null) {
            node = new Node<T>(value);
        } else {
            if (value.compareTo(node.value) <= 0) {
                node.left = insert(node.left, value);
            } else {
                node.right = insert(node.right, value);
            }
        }

        return node;
    }

    public void insertNonRecursively(T value) {

        this.root = insertNonRecursively(this.root, value);
    }

    private Node<T> insertNonRecursively(Node<T> node, T value) {

        if (node == null) {
            node = new Node<T>(value);
        } else {

            Node<T> runner = node;
            boolean inserted = false;

            while (!inserted) {

                if (value.compareTo(runner.value) < 0) {

                    if (runner.left == null) {
                        runner.left = new Node<T>(value);
                        inserted = true;
                    } else {
                        runner = runner.left;
                    }
                } else {
                    if (runner.right == null) {
                        runner.right = new Node<T>(value);
                        inserted = true;
                    } else {
                        runner = runner.right;
                    }
                }
            }
        }

        return node;
    }

    public static class Node<T extends Comparable<T>> {

        private Node<T> left;
        private Node<T> right;
        private T value;

        public Node(T value) {

            this.left = null;
            this.right = null;
            this.value = value;
        }

        public Node<T> getLeft() {
            return left;
        }

        public Node<T> getRight() {
            return right;
        }

        public T getValue() {
            return value;
        }
    }
}

Answer 1

让你的二叉树像

一样通用

public class BinaryTree<T extends Comparable<T>>{
   ...
}

每当创建一个 BinaryTree 实例时，指定包含的类型：

new BinaryTree<MyClass>();

其中 MyClass 必须实现 Comparable<MyClass>，即与相同 class 的对象相当。

您的方法将读作（示例）：

 public Node lookup(T value) { ... }

这同样适用于您的 Node class。以相同的方式使其通用。

Java 泛型：compareTo 和“capture#-of ?”

Java Generics: compareTo and “capture#-of ?”

java

generics

binary-tree

comparable