Solved

Generic tree help

Posted on 2007-04-01
7
222 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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 
LVL 2

Author Comment

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

Author Comment

by:toymachiner62
Comment Utility
just out of curiousity what does the question mark do here?


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

Expert Comment

by:ADSLMark
Comment Utility
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 125 total points
Comment Utility
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:

763 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

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now