Generic tree help

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(){
            
      }      
}
LVL 2
toymachiner62Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

ADSLMarkCommented:
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
toymachiner62Author Commented:
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
ADSLMarkCommented:
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
Cloud Class® Course: MCSA MCSE Windows Server 2012

This course teaches how to install and configure Windows Server 2012 R2.  It is the first step on your path to becoming a Microsoft Certified Solutions Expert (MCSE).

toymachiner62Author Commented:
So do you know how i would do an insert for a generic tree?
0
toymachiner62Author Commented:
just out of curiousity what does the question mark do here?


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

is short hand for:

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

Mark
0
ADSLMarkCommented:
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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.