Java 泛型 : compareTo and “capture#-of ?”

Question

我正在尝试编写一个 BinaryTree 的实现，其对象可以是实现 Comparable 的任何类型。 。但是，我意识到这不会完全起作用。例如，字符串和 double 无法插入到同一棵树中，即使它们都实现 Comparable 。

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

这是我到目前为止的代码:

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

你可以看到我实现了一些不同的BinaryTree此类的方法，但需要应用相同的规则:传递到 lookup() 的任何值或insert()还需要共享根的父类(super class)型。我有一种感觉，这就是 <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> ，即与同一类的对象具有可比性。

您的方法将读作(示例):

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

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