1

我需要比较树集中插入方法中的两个对象。但我无法弄清楚在哪里以及如何实现 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;
}


}
4

2 回答 2

2

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

如果你真的想同时支持，那么到了做比较的时候，如果Comparator已经提供了a，就使用它的 compare 方法，否则将数据转换为Comparable<? super E>其中 E 是 Node 数据的类型（见下文），然后使用它的compareTo方法。

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

我强烈建议查看java.utilJDK 附带的包中一些通用集合的源代码。特别是，我提到了TreeMap.java查看它们如何处理 Comparable 和 non-Comparable 元素的来源，因为该类没有以要求元素是 Comparable 的方式声明。（如果不是，并且在他们尝试将对象转换为 时不会发生Comparator,a 。）查看他们如何实现类似的代码将对您有很大帮助。您可能还想查看 Java 泛型。ClassCastExceptionComparable<? super K>

于 2013-10-18T17:17:56.413 回答
0

请参考以下代码

package com.example.treeset;

import java.util.Comparator;
import java.util.TreeSet;

public class MyCompUser {

    public static void main(String a[]){
        //By using name comparator (String comparison)
        TreeSet<Empl> nameComp = new TreeSet<Empl>(new MyNameComp());
        nameComp.add(new Empl("Ram",3000));
        nameComp.add(new Empl("John",6000));
        nameComp.add(new Empl("Crish",2000));
        nameComp.add(new Empl("Tom",2400));
        for(Empl e:nameComp){
            System.out.println(e);
        }
        System.out.println("===========================");
        //By using salary comparator (int comparison)
        TreeSet<Empl> salComp = new TreeSet<Empl>(new MySalaryComp());
        salComp.add(new Empl("Ram",3000));
        salComp.add(new Empl("John",6000));
        salComp.add(new Empl("Crish",2000));
        salComp.add(new Empl("Tom",2400));
        for(Empl e:salComp){
            System.out.println(e);
        }
    }
}

class MyNameComp implements Comparator<Empl>{

    @Override
    public int compare(Empl e1, Empl e2) {
        return e1.getName().compareTo(e2.getName());
    }
}   

class MySalaryComp implements Comparator<Empl>{

    @Override
    public int compare(Empl e1, Empl e2) {
        if(e1.getSalary() > e2.getSalary()){
            return 1;
        } else {
            return -1;
        }
    }
}

class Empl{

    private String name;
    private int salary;

    public Empl(String n, int s){
        this.name = n;
        this.salary = s;
    }

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getSalary() {
        return salary;
    }
    public void setSalary(int salary) {
        this.salary = salary;
    }
    public String toString(){
        return "Name: "+this.name+"-- Salary: "+this.salary;
    }
}
于 2013-10-18T16:43:43.610 回答