How would i compare two objects in custom tree set implementation?

Question

I need to compare two objects in insert method off the tree set. But i am unable to fathom out where and how to implement Comparable or Comparator. My code looks as follows:

This is my Node creation for the binary tree.

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

}

This is my MyBinaryTree class where i need to implement insert method:

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() ) ) {

i am stuck here! how would i compare these objects using Comparable?

            }
        }

    }

}

void inorder(Node root){

}

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


}

Answer 1

You need to be able to compare, not just nodes, but the data contained in those nodes. That means that your Node either needs to be limited to taking objects that are Comparable, or your tree needs to take a Comparator that it can use to compare them.

If you really want to support both, then when the time comes to do the comparison, if a Comparator has been provided, use its compare method, otherwise cast the data to Comparable<? super E> where E is the type of Node data (see below), and then use its compareTo method.

That brings me to the next point. Your Node class should probably not simply contain Object as its data, but instead be declared as Node<E> implements Comparable<Node<E>>, and then your tree can be declared as MyBinaryTree<E>. I would also change the constructor for Node to take the data as a parameter, rather than calling the setter immediately after creating one. There is no reason you would ever want to create a Node with no data.

I would strongly suggest looking through the source code for some of the generic collections in the java.util package, which comes with the JDK. In particular, I referred to the source of TreeMap.java to see how they handled both Comparable and non-Comparable elements, since the class isn't declared in such a way as to require the elements to be Comparable. (If they aren't, and there is no Comparator, a ClassCastException would occur where they try to cast the object to Comparable<? super K>.) Seeing how they have implemented similar code will be a great help to you. You may also want to review Java generics.