时间戳

首页 > 解决方案 > 异构二叉搜索树

java - 异构二叉搜索树

问题描述

我需要构建一个异构（具有不同类型的元素）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 定义了树的类型，而我无法解决这个问题。

PS这是给我错误的片段（为方便起见，我将发布整个主要方法。）

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 无法比较。

标签： javadata-structuresbinary-search-tree

解决方案

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

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

首先，Java 已经定义了一个Comparator与Comparable.

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这个解决方案仍然不能处理任何可能的类型。但是，此实现可用于处理各种类型的异构组合（只要客户端定义了适当的）。TreeComparator

推荐阅读