?
Solved

Generic tree help

Posted on 2007-04-01
7
Medium Priority
?
234 Views
Last Modified: 2010-04-16
Ok so i'm supposed to write a java class to implement a generic tree with methods
find and insert on the tree.
return height of the tree.
methods to output the values of pre, post, and level order traversal.
store the tree to a file.

I think i have the return height and pre and post order traversal. but i'm not sure how to do a level order traversal or a find and insert on the tree. If any of my code is wrong let me know also.

This is the code i have so far.

package treeProgram;
public class GTree<T> {

      private T data;
      private GTree<T> left;
      private GTree<T> right;
      private GTree<T> root;
      
      public GTree(){
            this(null);
      }
      
      public GTree(T dataPortion){
            this(dataPortion, null, null);
      }
      
      public GTree(T dataPortion, GTree<T>leftChild, GTree<T>rightChild){
            data = dataPortion;
            left = leftChild;
            right = rightChild;
      }
      
      public T getData(){
            return data;
      }
      
      public void setData(T newData){
            data = newData;
      }
      
      public GTree<T> getRightChild(){
            return right;
      }
      
      public GTree<T> getLeftChild(){
            return left;
      }
      
      public void setLeftChild(GTree<T> leftChild){
            left = leftChild;
      }
      
      public void setRightChild(GTree<T> rightChild){
            right = rightChild;
      }
      
      public int getHeight(){
            return getHeight(this);
      }
      
      public int getHeight(GTree<T> node){
            int height = 0;
            
            if(node != null){
                  height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
            }
            return height;
      }
      
      public void preOrderTraverse(){
            preOrderTraverse(root);
      }
      
      public void preOrderTraverse(GTree<T> node){
            if(node != null){
                  System.out.println(node.getData());
                  preOrderTraverse(node.getLeftChild());
                  preOrderTraverse(node.getRightChild());
            }
      }
      
      public void postOrderTraverse(){
            postOrderTraverse(root);
      }
      
      public void postOrderTraverse(GTree<T> node){
            if(node != null){
                  postOrderTraverse(node.getRightChild());
                  postOrderTraverse(node.getLeftChild());
                  System.out.println(node.getData());
            }
      }
      
      public void levelOrderTraverse(GTree<T> node){
            
      }
      
      public void find(){
            
      }      
}
0
Comment
Question by:toymachiner62
  • 4
  • 3
7 Comments
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18838591
Ok, i need to know more before I can help you with the insert. Do you want a binary search tree or what kind of other tree? ANyway,, here is the code for a pretty generic tree, (not a binary search tree), just a binary tree and find traverses all the nodes until it finds the node.
If you want a binary search tree, well I guess you need to extend your class with (node,key)-pairs, instead of a T data.

Mark
------------------
import java.util.LinkedList;

public class GTree<T extends Comparable<? super T>>
{
    private T data;

    private GTree<T> left;
    private GTree<T> right;

    public GTree()
    {
        this(null);
    }

    public GTree(T data)
    {
        this(data, null, null);
    }

    public GTree(T data, GTree<T> left, GTree<T> right)
    {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public T getData()
    {
        return this.data;
    }

    public void setData(T data)
    {
        this.data = data;
    }

    public GTree<T> getLeft()
    {
        return this.left;
    }

    public void setLeft(GTree<T> left)
    {
        this.left = left;
    }

    public GTree<T> getRight()
    {
        return this.right;
    }

    public void setRight(GTree<T> right)
    {
        this.right = right;
    }

    public int getHeight()
    {
        int heightLeft = this.left.getHeight();
        int heightRight = this.right.getHeight();

        return (1 + ((heightRight > heightLeft) ? heightRight : heightLeft));
    }

    public void preOrderTraverse()
    {
        System.out.println(this.getData());

        if(this.left != null)
            this.left.preOrderTraverse();

        if(this.right != null)
            this.right.preOrderTraverse();
    }

    public void postOrderTraverse()
    {
        if(this.left != null)
            this.left.postOrderTraverse();

        if(this.right != null)
            this.right.postOrderTraverse();

        System.out.println(this.data);
    }

    public void inOrderTraverse()
    {
        if(this.left != null)
            this.left.inOrderTraverse();

        System.out.println(this.data);

        if(this.right != null)
            this.right.inOrderTraverse();
    }

    public void levelOrderTraverse()
    {
        this.levelOrderTraverse(this);
    }

    public void levelOrderTraverse(GTree<T> root)
    {
        LinkedList<GTree<T>> queue = new LinkedList<GTree<T>>();
        queue.addLast(this);

        while (queue.size() > 0)
        {
            GTree<T> node = queue.removeFirst();
            System.out.println(node.getData());
            if (node.getLeft() != null)
                queue.addLast(node.getLeft());
            if (node.getRight() != null)
                queue.addLast(node.getRight());
        }
    }

    public GTree<T> find(T data)
    {
        if(this.getData() == data)
            return this;

        if(this.left != null)
        {
            GTree<T> leftFind = this.left.find(data);
            if(leftFind != null)
                return leftFind;
        }

        if(this.right != null)
        {
            GTree<T> rightFind = this.right.find(data);
            if(rightFind != null)
                return rightFind;
        }

        return null;
    }

    public void insert(T data)
    {

    }

    public static void main(String[] args)
    {
        GTree<Character> tree = mk('F',mk('B',mk('A'),mk('D',mk('C'),mk('E'))),mk('G',null,mk('I',mk('H'),null)));

        tree.levelOrderTraverse();
    }

    public static GTree<Character> mk(char c)
    {
        return mk(c,null,null);
    }

    public static GTree<Character> mk(char c, GTree<Character> l, GTree<Character> r)
    {
        return new GTree<Character>(c,l,r);
    }
}
0
 
LVL 2

Author Comment

by:toymachiner62
ID: 18839420
No not a binary search tree, just a generic tree. I think the insert is just supposed to insert a node in the next open leaf but i'm going to email my teach to find out. And what is your main supposed to do? print out a level order traversal of the tree??? could you explain this lines of code to me please

public static void main(String[] args)
    {
        GTree<Character> tree = mk('F',mk('B',mk('A'),mk('D',mk('C'),mk('E'))),mk('G',null,mk('I',mk('H'),null)));

        tree.levelOrderTraverse();
    }

    public static GTree<Character> mk(char c)
    {
        return mk(c,null,null);
    }

    public static GTree<Character> mk(char c, GTree<Character> l, GTree<Character> r)
    {
        return new GTree<Character>(c,l,r);
    }
}
0
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18839446
Oh, it was just for testing purposes, it quickly builds a tree with characters so i could test the traversals. I added the inorder and level order traversal, and i wanted to make sure i got it right. You can safely remove these three methods.

Mark
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 2

Author Comment

by:toymachiner62
ID: 18841012
So do you know how i would do an insert for a generic tree?
0
 
LVL 2

Author Comment

by:toymachiner62
ID: 18841043
just out of curiousity what does the question mark do here?


return (1 + ((heightRight > heightLeft) ? heightRight : heightLeft));
0
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18841665
return (1 + ((heightRight > heightLeft) ? heightRight : heightLeft));

is short hand for:

if(heightRight > heightLeft)
{
  return heightRight+1;
}
else
{
  return heightLeft+1;
}

Mark
0
 
LVL 10

Accepted Solution

by:
ADSLMark earned 500 total points
ID: 18841850
Solution for insert:

import java.util.LinkedList;
import java.io.*;

public class GTree<T extends Comparable<? super T>>
{
    private T data;

    private GTree<T> left;
    private GTree<T> right;

    public GTree()
    {
        this(null);
    }

    public GTree(T data)
    {
        this(data, null, null);
    }

    public GTree(T data, GTree<T> left, GTree<T> right)
    {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public T getData()
    {
        return this.data;
    }

    public void setData(T data)
    {
        this.data = data;
    }

    public GTree<T> getLeft()
    {
        return this.left;
    }

    public void setLeft(GTree<T> left)
    {
        this.left = left;
    }

    public GTree<T> getRight()
    {
        return this.right;
    }

    public void setRight(GTree<T> right)
    {
        this.right = right;
    }

    public int getHeight()
    {
        int heightLeft = (this.left != null) ? this.left.getHeight() : 0;
        int heightRight = (this.right != null) ? this.right.getHeight() : 0;

        return (1 + ((heightRight > heightLeft) ? heightRight : heightLeft));
    }

    public int getMinHeight()
    {
        if(this.left == null)
            return 1;

        if(this.right == null)
            return 1;

        int heightLeft = this.left.getMinHeight();
        int heightRight = this.right.getMinHeight();

        return (1 + ((heightRight < heightLeft) ? heightRight : heightLeft));
    }

    public void preOrderTraverse()
    {
        System.out.println(this.getData());

        if(this.left != null)
            this.left.preOrderTraverse();

        if(this.right != null)
            this.right.preOrderTraverse();
    }

    public void postOrderTraverse()
    {
        if(this.left != null)
            this.left.postOrderTraverse();

        if(this.right != null)
            this.right.postOrderTraverse();

        System.out.println(this.data);
    }

    public void inOrderTraverse()
    {
        if(this.left != null)
            this.left.inOrderTraverse();

        System.out.println(this.data);

        if(this.right != null)
            this.right.inOrderTraverse();
    }

    public void levelOrderTraverse()
    {
        this.levelOrderTraverse(this);
    }

    public void levelOrderTraverse(GTree<T> root)
    {
        LinkedList<GTree<T>> queue = new LinkedList<GTree<T>>();
        queue.addLast(this);

        while (queue.size() > 0)
        {
            GTree<T> node = queue.removeFirst();
            System.out.println(node.getData());
            if (node.getLeft() != null)
                queue.addLast(node.getLeft());
            if (node.getRight() != null)
                queue.addLast(node.getRight());
        }
    }

    public GTree<T> find(T data)
    {
        if(this.getData() == data)
            return this;

        if(this.left != null)
        {
            GTree<T> leftFind = this.left.find(data);
            if(leftFind != null)
                return leftFind;
        }

        if(this.right != null)
        {
            GTree<T> rightFind = this.right.find(data);
            if(rightFind != null)
                return rightFind;
        }

        return null;
    }

    public void insert(T data)
    {
        if(this.left == null)
        {
            this.left = new GTree<T>(data);
        }
        else if(this.right == null)
        {
            this.right = new GTree<T>(data);
        }
        else
        {
            int leftHeight = this.left.getMinHeight();
            int rightHeight = this.right.getMinHeight();

            if(leftHeight > rightHeight)
            {
                this.right.insert(data);
            }
            else
            {
                this.left.insert(data);
            }
        }
    }

    public static void main(String[] args)
    {
        GTree<Character> tree = new GTree<Character>('F');
        tree.insert('E');
        tree.insert('D');
        tree.insert('B');
        tree.insert('C');
        tree.insert('A');
        tree.insert('Z');

        //visualize(tree, "out.dot"); //only when graphviz is installed
        //see http://www.graphviz.org/
    }

    public static void visualize(GTree<Character> tree, String filename)
    {
        PrintWriter pw = null;
        try
        {
            pw = new PrintWriter(new File(filename));
            pw.println("digraph G {");
            pw.println(tree.toString());
            pw.println("}");
            pw.close();
            Runtime.getRuntime().exec("dot -Tps -oout.ps "+filename);
        }
        catch(IOException ioe)
        {
            System.err.println(ioe);
        }
        finally
        {
            if(pw!=null) pw.close();
        }
    }

    public String toString()
    {
        String sleft = (this.left!=null) ? ""+this.left.data : "null"+this.data;
        String sright = (this.right!=null) ? ""+this.right.data : "null"+this.data;
        String res = "";
        res += this.data+" -> "+sleft+"\n";
        res += this.data+" -> "+sright+";\n";

        if(this.left!=null) res += this.left.toString();
        if(this.right!=null) res += this.right.toString();

        return res;
    }
}

I also added some visualization mechanism. You need graphviz for that: http://www.graphviz.org/
It's an easy way to check the behaviour of the methods, but it's not foolproof, i just quickly add it, for debugging purposes.

Mark
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
The viewer will learn how to implement Singleton Design Pattern in Java.
Suggested Courses
Course of the Month15 days, 3 hours left to enroll

840 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question