java - 我如何比较自定义树集实现中的两个对象？

Question

我需要比较树集中的插入方法中的两个对象。但我无法弄清楚在哪里以及如何实现 Comparable 或 Comparator。我的代码如下所示:

这是我为二叉树创建的节点。

Node.java

public class Node {

private Object data;
private Node left, right;

//initial case when a Node of a binary tree gets created. both left and right subtrees point to   null
public Node (){

    left = right = null;
}

public Object getData() {
    return data;
}

public void setData(Object data) {
    this.data = data;
}

public Node getLeft() {
    return left;
}

public void setLeft(Node left) {
    this.left = left;
}

public Node getRight() {
    return right;
}

public void setRight(Node right) {
    this.right = right;
}

}

这是我的 MyBinaryTree 类，我需要在其中实现插入方法:

MyBinaryTree.java

public class MyBinaryTree implements Comparable<Node> {

Node root;

public MyBinaryTree(){
    root = null;
}

void insert(Object x){

    Node newrec = new Node();  //Node constructor gets called and sets up a root node with empty
    //subtrees
    newrec.setData(x);

    if(root == null){
        root = newrec;
    }
    else{
        Node a,b;
        a = b = root;
        while(a!=null){
            b=a;   
            if( ( newrec.getData() ).compareTo( a.getData() ) ) {

我被困在这里了!我如何使用 Comparable 来比较这些对象？

            }
        }

    }

}

void inorder(Node root){

}

@Override
public int compareTo(Node o) {
    // TODO Auto-generated method stub
    int i = (o.)
    return 0;
}


}

Answer 1

您不仅需要能够比较节点，还需要能够比较这些节点中包含的数据。这意味着您的 Node要么需要限制为获取 Comparable, 的对象或者你的树需要采取 Comparator它可以用来比较它们。

如果你真的想同时支持两者，那么到时候进行比较时，如果 Comparator已提供，请使用其比较方法，否则将数据转换为 Comparable<? super E>其中E是Node数据的类型(见下文)，然后使用其compareTo方法。

这让我想到了下一点。您的Node类可能不应该简单地包含 Object作为其数据，但声明为 Node<E> implements Comparable<Node<E>>,然后你的树可以声明为 MyBinaryTree<E>.我还会更改 Node 的构造函数将数据作为参数，而不是在创建数据后立即调用 setter。您没有理由想要创建 Node没有数据。

我强烈建议查看 java.util 中一些通用集合的源代码包，是JDK自带的。我特别提到了TreeMap.java的来源了解它们如何处理可比较和不可比较元素，因为该类的声明方式并未要求元素可比较。 (如果不是，并且没有 Comparator, ，则在尝试将对象强制转换为 ClassCastException 时会出现 Comparable<? super K> 。)了解他们如何实现类似的代码将对您有很大帮助。您可能还想查看 Java 泛型。