generic programming, generic data structures

Question

I am trying to implement a Binary Search Tree and if I use the generic programming in java then this tree should be able to store any kind of data e.g. int, Strings or basically any other object. But the problem with such a class is with coding the functions e.g. if I am coding the addToTree function, then "<" operator can be used to compare int and it would successfully insert int into the tree but it won't insert strings or other objects because comparing strings and other objects using "<" operator may not be allowed.

This problem is same for other data structures too.

Answer 1

You should limit the generic type for your BinarySearchTree,

class BinarySearchTree<T extends Comparable<? super T>>

The element should implement Comparable interface, otherwise you are not able to order the elements.

Edit: As @JB Nizet suggests, don't use raw Comparable

Answer 2

I think I get what you're saying. Typically, well-designed classes (likely all the standard ones you'll ever use in the JDK) implement Comparable and override the built-in compareTo method which defines how the <, >, and == operations work. compareTo returns 1 if greater, 0 if equal, -1 if less.

If you wish to create your own class to put in the binary tree, then yes, you will have to implement Comparable.

Edit: Answer below me makes a very important point: if you intend on using comparisons, you should restrict the possible class types to ones that extend Comparable!

Answer 3

To accomplish the other answers:

Implementing the Comparable interface only makes sense for classes who really have a natural ordering. Additionally, this ordering should be consistent with the equals method. Implementing the equals and the compareTo methods sounds easier, than it sometimes really is. This should be well-designed.

Often enough, there is no real natural ordering on the objects of a class. But you will have tasks to order them on a specific property, nevertheless. For this kind of tasks, you can implement another interface: Comparator. A comparator then can be used to order your objects as you need.

Take a look at TreeSet, which is such a search tree. This Set implementation provides two constructors: One is designed for being used with objects that are comparable. The other takes a comparator for that task, and is designed for being used with non-comparable objects.