异构二叉搜索树

Question

我需要构建一个异构(具有不同类型的元素)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);
}
}

现在我的树的问题是，每当任何元素与根不同时，我都会得到ClassCastException，因为那里发生的事情是根定义了树的类型，我无法修复。

p。年代下面是给出错误的代码片段(为了方便，我将发布整个main方法)

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是不可比较的。

Answer 1

我认为，评论充分阐述了比较任何两个对象是不明智的。但是，您仍然可以通过将比较与树逻辑解耦来实现这样的树。

相反，每个客户都会遇到与你现在面临的完全相同的问题，但有些客户可能有适合他们的特定解决方案。我们以后再研究。

首先，Java已经定义了一个与Comparable一起的Comparator接口。

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

Answer 2

我在java课程中也有类似的任务。我使用泛型来定义树。然后我创建了一个接口树，它由每个节点实现。然后在每个节点中实现接口的方法，这允许我对对象进行比较和排序。本主题有一个简单的例子:java中的简单异构k-ary树(用于创建网络模拟器)

我把这个问题想象成杂货店里的产品。每种产品都有id、品牌、名称和价格，但根据产品的类型，它们必须冷却或"最佳食用前"。或需要冷冻或不可食用。