Tree Implementation with Generic Types in Java

Question

Firstly I ve searched about usage of Generic Types in java, however answers I ve found was way too simple or complicated. So here is my exact question.

I have three classes respectively PerfectTreeControl, Tree and Entry.

Tree has

public class Tree<K> {
  public Entry <K> root;

Entry has

public class Entry<K> {
    public K element;
    public Entry<K> parent, left_child, right_child;


    public Entry(K element) {
        this.element = element;
    }
    public Entry(K element, Entry<K> left, Entry<K> right) {
        left_child = left;
        right_child = right;
        this.element = element;
    }

I am trying to understand what is the difference between Entry parent and Entry <K> parent? I know that K element can be used as integer, String or whatever I want, but does the same thing goes for the object? I tried to use Entry variables without parameter and it only said that Entry is a raw type and should be parameterized and it still working without error.

My second question is about checking out a tree whether its perfect or not. Here are the some codes I ve tried so far:

public class PerfectTreeControl {

    public static boolean isPerfect(Tree<String> tree) {
        Tree t1 = new Tree();
        if( t1.isFull( tree.root ) ) {  
            int depth = t1.height(tree.root);
            return t1.everyLeafHasSameDepth(tree.root, depth);
        } 
        else 
            return false;
    }   
    }





public class Tree<K> {
    public Entry <K> root;

    public boolean isLeaf(Entry e) {
        return e.left_child == null &&
                e.right_child == null;
    }

    public int height(Entry  e) {
        if( e == null ||
                e.left_child == null &&
                e.right_child == null ) 
            return  0;
        int left = height( e.left_child );
        int right = height( e.right_child );

        return 1 + Math.max(left, right);
    }

    public boolean isFull(Entry base) {
        if( isLeaf(base) )
            return true;
        else
            if( base.left_child != null && base.right_child != null ) {
                return isFull(base.left_child) &&
                        isFull(base.right_child);
            } else {
                return false;
            }
    }


    public  int depth(Entry e) {
        if( e == root ) {
            return 0;
        } else {
            return 1 + depth(e.parent);
        }
    }

    public  boolean everyLeafHasSameDepth(Entry base, int depth) {
        if( base == null ) 
            return false;
        else if(isLeaf(base) ) 
            return depth( base ) == depth;
        else {
            return 
                    everyLeafHasSameDepth(base.left_child, depth) &&
                    everyLeafHasSameDepth(base.right_child, depth);
        }
    }

entry class(I wrote it at the top of the page) As you can see, isPerfect method in the PerfectTreeControl class uses Tree -String- tree as a paramater and I have no idea what it is. In the Tree class, I tried Entry with and and again no difference. The code won't work properly, and I am totally confused.

You shouldn't really worry about raw types. They're only there for backwards compatibility and you should never use the raw version of a generic type. (I.e. in your code, use Entry<Something> everywhere.) — millimoose
– millimoose, Commented Jun 30, 2012 at 22:31
What's the point of defining generic object? More clearly, what advantages do I get with defining an object as a generic instead of normal? Objects already can take anything you define in the class as a variable, string, int etc. Am I missing something? — nihirus
– nihirus, Commented Jun 30, 2012 at 22:40
@nihirus: If you use plain Objects everywhere you need to cast the values to the required type every time you want to do something. — Tudor
– Tudor, Commented Jun 30, 2012 at 22:43
@nihirus Mainly, type safety. I strongly recommend reading at least the starting parts of the notorious Angelika Langer FAQ — millimoose
– millimoose, Commented Jun 30, 2012 at 22:44

cheeken · Accepted Answer · 2012-06-30 22:43:21Z

Generics in Java are, fundamentally, a way to name a particular class within an object with knowing which class until that object is declared. This is useful because it allows the compiler to enforce consistency among references to that class.

More concretely, in your class Entry<K>, any time you reference K, the Java compiler will enforce that all references of type K are, in fact, treated as type K. For instance, if you create an object of type Entry<String>, the element member of that object must be of type String, the parent member must be of type Entry<String>, etc. If you had a method that returned a K, the compiler would recognize that the return value is String. If the compiler sees an inconsistency here - say, if you try to set member's value to an Integer - it will complain.

Keep in mind that qualities I describe in the example above is all in reference to the particular Entry<String> object that you've defined. If you instead define an Entry<Integer>, without updating your Entry class, the consistency is enforced within that new object - except this time with K meaning Integer.

If you create an object without specifying a type argument for K, you are using a "raw type". This prevents the compiler from enforcing consistency rules and it will assume that the type of K is Object. This means you'll have to start worrying about casting, which can be tedious to do properly.

To check if a tree is full (or "perfect"), the most intuitive approach is a recursive one. The recursive rule to use in this scenario is "if a tree's children are perfect and have the same depth, the tree is perfect."

Collectives™ on Stack Overflow

Tree Implementation with Generic Types in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related