我需要构建一个异构(具有不同类型的元素)BST并能够对元素进行排序,但我不知道如何解决这个问题。
我这里有二叉树代码。
This is the node class
public class Node<T> {
T data;
Node<T> left;
Node<T> right;
Node(T data) {
this.data = data;
left = null;
right = null;
}
}
这是树类。
public class Tree<T extends Comparable<T>> {
private Node<T> root;
StringBuilder result = new StringBuilder();
public Tree() {
root = null;
}
public Node<T> getRoot() {
return root;
}
/**
* Method that inserts nodes into the binary tree. If the tree is empty , a new root node is
* initialized.
*
* @param root A node object.
* @param dataBeingInserted The object to be inserted on the tree.
* @return The root node object
*/
private Node<T> insertNode(Node<T> root, T dataBeingInserted) {
if (root == null) {
root = new Node<>(dataBeingInserted);
return root;
}
if (dataBeingInserted.compareTo(root.data) < 0) {
root.left = insertNode(root.left, dataBeingInserted);
} else if (dataBeingInserted.compareTo(root.data) > 0) {
root.right = insertNode(root.right, dataBeingInserted);
}
return root;
}
public void insertNode(T dataBeingInserted) {
root = insertNode(root, dataBeingInserted);
}
/**
* Method that recursively searches for our element through the tree. If the value is present in
* the root node , or there aren't any nodes in the tree , the method returns the root node. If
* the value we're looking for is smaller than the root node's value , we search for our value in
* the left subtree , otherwise we search for it in the right subtree.
*
* @param root A node object.
* @param dataBeingSearched User's value.
* @return Recursive call of the method.
*/
private Node<T> searchTree(Node<T> root, T dataBeingSearched) {
if (root == null || dataBeingSearched.compareTo(root.data) == 0) {
return root;
}
if ((dataBeingSearched.compareTo(root.data) > 0)) {
return searchTree(root.left, dataBeingSearched);
}
return searchTree(root.right, dataBeingSearched);
}
public Node searchTree(T dataBeingSearched) {
return searchTree(root, dataBeingSearched);
}
/**
* An implementation of the In-order traversal. First the left subtree is visited and printed
* accordingly, then we visit and print the root and after that we visit and print the right
* subtree.
*
* @param root The root node object.
*/
private String inorderTraversal(Node root) {
if (root == null) {
return "";
}
inorderTraversal(root.left);
result.append(root.data).append(" ");
inorderTraversal(root.right);
return result.toString();
}
public void inorderTraversal() {
inorderTraversal(root);
}
}
我的树现在的问题是,每当任何元素与 root 不同时,我都会收到 ClassCastException ,因为发生的情况是 root 定义了树的类型,而我无法修复它。
附注 这是给我错误的代码片段(为了方便起见,我将发布整个主要方法。)
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.Scanner;
public class Main {
private static final Logger LOGGER = LoggerFactory.getLogger(Main.class);
private static final Scanner SCANNER = new Scanner(System.in);
public static void main(String[] args) {
Tree tree = new Tree<>();
tree.insertNode(50);
tree.insertNode("30");
tree.insertNode('b');
tree.insertNode(69.3);
tree.inorderTraversal();
LOGGER.info("{}", tree.result);
}
}
例如,第一个插入是一个 Integer ,之后我尝试插入一个 String ,然后它给了我 ClassCastException ,说 String 与 Integer 无法比较。
最佳答案
我认为,这些评论彻底阐述了比较任何两个对象是不可能的。但是,您仍然可以通过将比较与树逻辑解耦来实现这样的树。
相反,每个客户都会遇到与您现在面临的完全相同的问题,但有些客户可能有适合他们的特定解决方案。我们稍后会研究这个问题。
首先,Java 已经定义了一个与 Comparable
一起使用的 Comparator
接口(interface)。
package java.util;
public interface Comparator<T> {
int compare(T o1, T o2);
}
同时,让我们重新思考一下树形界面。基本上,要求规定它应该能够接受几乎任何对象,因此它必须具有类似的方法
public void add(Object data);
此时,没有理由使用泛型,因为我们实际上无法做出任何限制。即使树中还有其他对象,它仍然应该能够接受任何对象。
因此,我们可以做类似的事情
public class Tree {
private Comparator<Object> comparator;
private Node root;
public Tree(Comparator<Object> comparator) {
this.comparator = Objects.requireNonNull(comparator);
}
public void add(Object data) {
root = insertNode(root, data);
}
private void insertData(Node root, Object dataBeingInserted) {
// see below
}
}
对 Node
类没有重大更改,只是它不再是通用的。现在,当在 insertNode
方法中比较两个对象时,我们只需查阅 Comparator
实例,而不是自己进行比较。
if (comparator.compare(dataBeingInserted, root.data) < 0) {
root.left = insertNode(root.left, dataBeingInserted);
} else if (comparator.compare(dataBeingInserted, root.data) > 0) {
root.right = insertNode(root.right, dataBeingInserted);
}
客户端可以使用此Tree
实现与Comparator
,她/他限制她/他知道可能发生的类型。
public static void main(String[] args) {
Tree t = new Tree((o1, o2) -> {
if (o1 instanceof Number && o2 instanceof String) {
// numbers before strings
return -1;
}
if (o1 instanceof Integer && o2 instanceof Integer) {
return ((Integer) o1).compareTo((Integer) o2);
}
if (o1 instanceof String && o2 instanceof String) {
return ((String) o1).compareTo((String) o2);
}
throw new ClassCastException("incompatible types: " + o1.getClass().getCanonicalName()
+ ", " + o2.getClass().getCanonicalName());
});
t.add("Hello");
t.add(Integer.valueOf(1337));
}
正如 ClassCastException
所示,此解决方案仍然无法固有地处理任何可能的类型。但是,此Tree
实现可用于处理类型的每种异构组合(只要客户端定义适当的Comparator
)。 p>
关于java - 异构二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68998446/