Solved

Generic tree help

Posted on 2007-04-01
7
230 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
MS Dynamics Made Instantly Simpler

Make Your Microsoft Dynamics Investment Count  & Drastically Decrease Training Time by Providing Intuitive Step-By-Step WalkThru Tutorials.

 
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 125 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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Java Restore security prompts not working 10 140
how to debug htl and js pages 8 58
Notify sent to other threads in Java 9 43
running on tomcat not jboss eap 7.0 3 33
After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
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 …

726 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