implementing compareTo (Comparable<T>) for a Binary Tree(Generic)

NhatNienne

I'm generating a Binary Tree with key - value nodes.

It works like this: example Binary Tree(those numbers are the keys)

The ordering is as followed: If you implement a new node you give a key and a value(not important) it will check if there is a node already if not it will create it as the first node. now it checks if the key is smaller then the key of the first node, if so it will put it as the left node if there isn't already one, if there is one it will iterate to that and check it again. Same for the bigger key/right node. If the key is equal to the key of the current node it will override the node.

This method is working if I use something like int. Now I want to do it as a generic so I want to add compareTo from the Comparable interface, because I could check if the key is smaller, equal or greater than the key of the current node. I know I have to use the keys but I can't code any compareTo method myself. I'm not sure how to get it to work.

@Override
public int compareTo(TreeNode<Type> node) {
    //method
}

Attributes I'm currently using in my program are: Nodes(first,previous,left,right), key, value Type key, value Node myNodes(previous,...)

classdefinitions:

public class Tree<Type> {
    ...
    public class TreeNode<Type extends Comparable<Type>>{
        ...
    }
    public int compareTo(TreeNode<Type> Node){
        //method
    }
}
midor

Right now what your code says is:

There is a tree of type type, which can be compared to other trees of type type.

What you seemingly want to say is:

There is a tree, built from elements of type type, which are comparable to their own type.

In that case, you should define tree like this:

public class Tree<T extends Comparable<T>> {
     private class TreeNode<F extends<Comparable<F>> implements Comparable<TreeNode<F>>{
           private F f;
           ...
           public F getF(){return this.f;}
           @Override
           public int compareTo(TreeNode<F> node){
               return this.f.compareTo(node.getF());
           }
     }
     //Use TreeNode<T> here
     ...
}

Short summary: you have a Tree of type T, which is a type that can be compared to other objects of type T. Elements in the tree are represented by TreeNode<T>, which can be compared to other TreeNode<T>. The comparison of a TreeNode<T> to a TreeNode<T> can be done by comparing the Elements stored inside the TreeNode. There is a reason, why I have deviated from your original design in the last point (by name at least). If you think of T as the stored item, it is easier to think about how to extend the tree to support an item of type TreeItem, which enables you to build an associative data-structure on top of the tree.

Edit (in direct response, since OP requested clarification):

OP's code was something like this at the time of answer:

public class Tree<T> implements Comparable<Tree<T>>{
    ...
    TreeNode<???>{...}

}

Think of the TreeNode having a fixed member int key; for a second. You want to build a Tree: So you need TreeNodes, which can be compared to each other (i.e. TreeNode implements Comparable<TreeNode>)to build a Tree. You implement compareTo with int-comparisons. You now have a non-generic Tree.

To be able to make Tree generic, you need a generic TreeNode. So you make TreeNode generic and replace the formerly fixed field int key; by F f;. Now you can no longer implement comparison based on int-comparisons, so TreeNode has to be comparable to other instances of TreeNode somehow. It would be cool, if we could delegate that to F's comparison function. To make sure that works, the type has to be TreeNode<F extends Comparable<F>>. Of course we still need the basic hypothesis of comparable TreeNodes to hold so you end up with

class TreeNode<F extends<Comparable<F>> implements Comparable<TreeNode<F>>.

You now have a generic TreeNode<F>, that can be compared to other instances of TreeNode<F>.

Now you can build a generic Tree<T> from these nodes, as long as T is something that can be compared to other Ts, so Tree<T extends Comparable<T>>. Since you don't want to shadow the type of the inner class you differentiate between T and F and instantiate TreeNode<T>s when you use them inside the tree's functions. The existence of F is not seen from the outside.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

Comparable<T> and compareTo

From Dev

JAXB 2.1 implementing Comparable<T> for the generated Class

From Dev

Issue implementing the java Comparable<T> class

From Dev

java8 - annotating compareTo <T> of Comparable<T> adds annotations to compareTo(Object o)

From Dev

Generic Comparable type for compareTo

From Dev

Overiding compareTo in Comparable for sorting

From Dev

The method compareTo(Comparable) is undefined for the type Comparable

From Dev

Extending comparable interface and override compareTo

From Dev

Problems with overriding compareTo() in interface Comparable

From Dev

Extending comparable interface and override compareTo

From Dev

Implementing custom compareTo

From Dev

Implementing Comparable for a Node in Java

From Dev

Implementing comparable for Tree class

From Dev

Implementing Comparable with a generic class

From Dev

Java 8: implementing Comparable

From Dev

Binary Search CompareTo Java

From Dev

Why use compareTo() from Comparable Interface when overriding the compareTo() method?

From Dev

adding comparable interface and adding a compareTo() method

From Dev

Contracts of the compare and compareTo method from Comparator and Comparable

From Dev

Why do we use `this` in CompareTo in Comparable implementations?

From Dev

Java Comparable interface: compareTo int attributes

From Dev

Java: Problems implementing the Comparable interface

From Dev

Sort implementing Comparable not working on Android

From Dev

Comparable<T> vs Raw Comparable

From Dev

Overriding compareTo(T t)

From Dev

comparable used as structure in a binary tree

From Dev

Comparable<? super T> vs. Comparable<T>

From Dev

Is acceptable use static object for implementing comparable in java?

From Dev

Implementing comparable interface to rational class(java)

Related Related

  1. 1

    Comparable<T> and compareTo

  2. 2

    JAXB 2.1 implementing Comparable<T> for the generated Class

  3. 3

    Issue implementing the java Comparable<T> class

  4. 4

    java8 - annotating compareTo <T> of Comparable<T> adds annotations to compareTo(Object o)

  5. 5

    Generic Comparable type for compareTo

  6. 6

    Overiding compareTo in Comparable for sorting

  7. 7

    The method compareTo(Comparable) is undefined for the type Comparable

  8. 8

    Extending comparable interface and override compareTo

  9. 9

    Problems with overriding compareTo() in interface Comparable

  10. 10

    Extending comparable interface and override compareTo

  11. 11

    Implementing custom compareTo

  12. 12

    Implementing Comparable for a Node in Java

  13. 13

    Implementing comparable for Tree class

  14. 14

    Implementing Comparable with a generic class

  15. 15

    Java 8: implementing Comparable

  16. 16

    Binary Search CompareTo Java

  17. 17

    Why use compareTo() from Comparable Interface when overriding the compareTo() method?

  18. 18

    adding comparable interface and adding a compareTo() method

  19. 19

    Contracts of the compare and compareTo method from Comparator and Comparable

  20. 20

    Why do we use `this` in CompareTo in Comparable implementations?

  21. 21

    Java Comparable interface: compareTo int attributes

  22. 22

    Java: Problems implementing the Comparable interface

  23. 23

    Sort implementing Comparable not working on Android

  24. 24

    Comparable<T> vs Raw Comparable

  25. 25

    Overriding compareTo(T t)

  26. 26

    comparable used as structure in a binary tree

  27. 27

    Comparable<? super T> vs. Comparable<T>

  28. 28

    Is acceptable use static object for implementing comparable in java?

  29. 29

    Implementing comparable interface to rational class(java)

HotTag

Archive