Как бы я сравнил два объекта в пользовательской реализации набора деревьев?

Мне нужно сравнить два объекта в методе вставки из набора дерева. Но я не могу понять, где и как реализовать Comparable или Comparator. Мой код выглядит следующим образом:

Это мое создание Node для бинарного дерева.

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;
}


}

java collections comparable comparator binary-search-tree
person Chiran    schedule 18.10.2013    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Вы должны иметь возможность сравнивать не только узлы, но и данные, содержащиеся в этих узлах. Это означает, что либо ваш Node должен быть ограничен тем, что он берет объекты, которые являются Comparable,, либо вашему дереву нужно брать Comparator, который он может использовать для их сравнения.

Если вы действительно хотите поддерживать и то, и другое, то, когда придет время для сравнения, если был предоставлен Comparator, используйте его метод сравнения, в противном случае приведите данные к Comparable<? super E>, где E — тип данных узла (см. ниже), и затем используйте его метод compareTo.

Это подводит меня к следующему пункту. Ваш класс Node, вероятно, должен не просто содержать Object в качестве своих данных, а вместо этого должен быть объявлен как Node<E> implements Comparable<Node<E>>,, а затем ваше дерево может быть объявлено как MyBinaryTree<E>.. Я бы также изменил конструктор для Node, чтобы он принимал данные в качестве параметра, а не сразу вызывал установщик после создания одного. Нет никаких причин, по которым вы когда-либо хотели бы создать Node без данных.

Я настоятельно рекомендую просмотреть исходный код некоторых универсальных коллекций в пакете java.util, который поставляется с JDK. В частности, я сослался на источник TreeMap.java, чтобы увидеть, как они обрабатывают как сопоставимые, так и несопоставимые элементы, поскольку класс не объявлен таким образом, чтобы требовать, чтобы элементы были сопоставимыми. (Если это не так, и нет Comparator,, произойдет ClassCastException, когда они попытаются привести объект к Comparable<? super K>.) Увидев, как они реализовали аналогичный код, вам очень поможет. Вы также можете ознакомиться с дженериками Java.

person David Conrad    schedule 18.10.2013

arrow_upward
0
arrow_downward

Пожалуйста, обратитесь к коду ниже

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;
    }
}
person Scientist    schedule 18.10.2013
comment
Вы должны описать проблему лучше, чем Пожалуйста, обратитесь к коду ниже - person Miserable Variable; 18.10.2013