如何构建支持多类型元素存储与排序的Heterogeneous Binary Search Tree

问题原因分析 #

当前代码报错的核心原因有两点：

• 泛型约束Tree<T extends Comparable<T>>本身就限定了整棵树只能存储同一种可比较类型的元素，插入第一个Integer类型元素后，泛型实际类型就被确定为Integer，后续插入其他类型元素时调用compareTo会触发强制类型转换异常
• 不同类型的JDK默认Comparable实现仅支持同类型比较，不支持跨类型比对

解决方案思路 #

要实现异构BST，核心是自定义跨类型比较逻辑，代替元素自身的compareTo方法，同时去掉原代码中限制同类型的泛型约束。你可以根据业务需要选择比较规则，这里提供两种常见的规则实现：

1. 按类型优先级排序：给不同类型分配固定优先级，不同类型按优先级比对，同类型按自身规则比对
2. 统一转换为字符串比对：所有元素先转为字符串，再按字典序比对

完整修改代码 #

1. 节点类修改 #

去掉泛型，支持存储任意类型元素：

public class Node {
  Object data;
  Node left;
  Node right;

  Node(Object data) {
    this.data = data;
    left = null;
    right = null;
  }
}

2. 树类修改 #

• 移除泛型约束
• 新增自定义跨类型比较方法
• 修复原代码搜索逻辑写反的bug
• 修复中序遍历结果重复累加的问题

public class Tree {
  private Node root;
  StringBuilder result = new StringBuilder();

  public Tree() {
    root = null;
  }

  public Node getRoot() {
    return root;
  }

  // 自定义跨类型比较方法：按类型优先级+同类型自身规则比较
  private int compare(Object a, Object b) {
    Class<?> aClass = a.getClass();
    Class<?> bClass = b.getClass();

    int aPriority = getTypePriority(aClass);
    int bPriority = getTypePriority(bClass);

    if (aPriority != bPriority) {
      return Integer.compare(aPriority, bPriority);
    }

    if (a instanceof Comparable && b instanceof Comparable) {
      return ((Comparable) a).compareTo(b);
    }
    return 0;
  }

  // 定义类型优先级，数值越小排序越靠前
  private int getTypePriority(Class<?> clazz) {
    if (clazz == Integer.class) return 1;
    if (clazz == Double.class) return 2;
    if (clazz == Character.class) return 3;
    if (clazz == String.class) return 4;
    return 99;
  }

  private Node insertNode(Node root, Object dataBeingInserted) {
    if (root == null) {
      root = new Node(dataBeingInserted);
      return root;
    }

    int compareRes = compare(dataBeingInserted, root.data);
    if (compareRes < 0) {
      root.left = insertNode(root.left, dataBeingInserted);
    } else if (compareRes > 0) {
      root.right = insertNode(root.right, dataBeingInserted);
    }
    return root;
  }

  public void insertNode(Object dataBeingInserted) {
    root = insertNode(root, dataBeingInserted);
  }

  private Node searchTree(Node root, Object dataBeingSearched) {
    if (root == null || compare(dataBeingSearched, root.data) == 0) {
      return root;
    }
    if (compare(dataBeingSearched, root.data) > 0) {
      // 修复原代码逻辑错误：大于根节点的元素在右子树
      return searchTree(root.right, dataBeingSearched);
    }
    return searchTree(root.left, dataBeingSearched);
  }

  public Node searchTree(Object dataBeingSearched) {
    return searchTree(root, dataBeingSearched);
  }

  private void inorderTraversal(Node root) {
    if (root == null) {
      return;
    }
    inorderTraversal(root.left);
    result.append(root.data).append(" ");
    inorderTraversal(root.right);
  }

  public String inorderTraversal() {
    // 每次遍历前清空之前的结果，避免累加
    result.setLength(0);
    inorderTraversal(root);
    return result.toString();
  }

}

3. 测试Main方法 #

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class Main {
  private static final Logger LOGGER = LoggerFactory.getLogger(Main.class);

  public static void main(String[] args) {
    Tree tree = new Tree();
    tree.insertNode(50);
    tree.insertNode("30");
    tree.insertNode('b');
    tree.insertNode(69.3);
    tree.insertNode(20); // 新增同类型测试
    String sortRes = tree.inorderTraversal();
    LOGGER.info("排序结果：{}", sortRes);
  }
}

运行结果说明 #

按我们定义的优先级规则，输出结果为：

排序结果：20 50 69.3 b 30 

如果需要改成统一转字符串比较的规则，只需要修改compare方法即可：

private int compare(Object a, Object b) {
    return a.toString().compareTo(b.toString());
}

内容的提问来源于stack exchange，提问作者Jebvam Ust