?
Solved

Generic tree help

Posted on 2007-04-01
7
Medium Priority
?
232 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

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

Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
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:
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses
Course of the Month14 days, 3 hours left to enroll

801 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