我正在尝试编写一个 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;
}
}
}
最佳答案
让你的二叉树变得通用
public class BinaryTree<T extends Comparable<T>>{
...
}
每当创建BinaryTree时实例，指定包含的类型:
new BinaryTree<MyClass>();
哪里MyClass必须实现Comparable<MyClass> ，即与同一类的对象具有可比性。
您的方法将读作(示例):
public Node lookup(T value) { ... }
这同样适用于您的 Node类(class)。以同样的方式使其通用。
关于Java 泛型 : compareTo and “capture#-of ?” ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28183045/