Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / First Aid / October 2007

Tip: Looking for answers? Try searching our database.

Print a binary search tree

Thread view: 
kaltizer - 24 Oct 2007 16:54 GMT
Greetings, here is my code:

import java.util.*;

class BinarySearchTreeSet
{

// Inner class defining a binary tree node

  private class TreeNode
  {
     private TreeNode left;
     private Comparable key;
     private TreeNode right;
  }

// instance variables

  private TreeNode root, parent, child;

// Constructor

  public BinarySearchTreeSet()
  {
     root = null;
  }

// Inserts a key into the set

  public void insert(Comparable key) throws DuplicateKey
  {
     TreeNode newNode;
     if (search(key))
        throw new DuplicateKey();
     newNode = new TreeNode();
     newNode.key = key;
     newNode.left = null;
     newNode.right = null;
     if (parent == null)
        root = newNode;
     else if (parent.key.compareTo(key) > 0)
        parent.left = newNode;
     else
        parent.right = newNode;
            System.out.println("The name " + key + " was added");
  }

// Removes a key from the set

  public void remove(Comparable key) throws NotFound
  {
     if (!search(key))
        throw new NotFound();
     if (child == root)
        root = deleteNode(root);
     else if (parent.left == child)
        parent.left = deleteNode(parent.left);
     else
        parent.right = deleteNode(parent.right);

        System.out.println("The name " + key + " was deleted");
  }

// Determines whether a key is in the set

  public boolean contains(Comparable key)
  {
     if (!search(key))
        return false;
     return true;
        }

// Private method that searches for a key

  private boolean search(Comparable key)
  {
     parent = null;
     child = root;
     while (child != null)
     {
        if (child.key.equals(key))
           return true;
        parent = child;
        if (child.key.compareTo(key) > 0)
           child = child.left;
        else
           child = child.right;
     }
     return false;
  }

// Private method that deletes a node

  private TreeNode deleteNode(TreeNode node)
  {
     TreeNode inorderSuccessor, successorsParent;

     if (node.right == null)
        return node.left;   // 0-1 Child
     else if (node.left == null)
        return node.right;   // 1 Child
     else
     {                  // 2 Children
        successorsParent = node.left;
        inorderSuccessor = successorsParent.right;
        if (inorderSuccessor == null)
        {
           node.left = successorsParent.left;
           node.key = successorsParent.key;
        }
          else
        {
           while (inorderSuccessor.right != null)
           {
              successorsParent = inorderSuccessor;
              inorderSuccessor = inorderSuccessor.right;
           }
           successorsParent.right = inorderSuccessor.left;
           node.key = inorderSuccessor.key;
        }
     }
  return node;
  }

    // begin print code
    // here is where I'm having problems
   public void printTree() {
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       queue.offer(root);
         System.out.println(root);
       while(!queue.isEmpty()) {
           TreeNode n = queue.poll();
           System.out.println(n.left + " <- " + n + " -> " +
n.right);
           if(n.left != null) queue.offer(n.left);
           if(n.right != null) queue.offer(n.right);
       }
   }
   // end print code
}

I get the following output when I call the printTree() method from my
driver:

BinarySearchTreeSet$TreeNode@1b67f74
// the following all on one line
BinarySearchTreeSet$TreeNode@69b332 <- BinarySearchTreeSet
$TreeNode@1b67f74 -> BinarySearchTreeSet$TreeNode@173a10f
// end of all on one line
null <- BinarySearchTreeSet$TreeNode@69b332 -> null
null <- BinarySearchTreeSet$TreeNode@173a10f -> null

This output is after adding "kevin", "billy", and "timmy" to the
tree.  The add, contains,  and remove methods all work fine.  I just
need to get the tree printing to the console, and then I have to work
on file i/o.

Thanks in advance for any help...
Roedy Green - 24 Oct 2007 18:29 GMT
>null <- BinarySearchTreeSet$TreeNode@69b332 -> null

You may have other problems, but I think you want to implement a
toString method for your nodes that prints out something entertaining.
Instead you are just getting the default toString which is designed
purely for debugging.
Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

kaltizer - 26 Oct 2007 07:48 GMT
On Oct 24, 7:29 pm, Roedy Green <see_webs...@mindprod.com.invalid>
wrote:

> >null <- BinarySearchTreeSet$TreeNode@69b332 -> null
>
[quoted text clipped - 5 lines]
> Roedy Green Canadian Mind Products
> The Java Glossaryhttp://mindprod.com

I have fixed the print to console problem.  Now I am having problems
printing to the text file.  I've commented in the file where the
problem is.  Any help is greatly appreciated.

// Kevin Altizer 23 October 2007
// PURPOSE: File for a binary search tree class
// COMPILER: Java JDK 1.5, with jGRASP 1.8.6_04 as the IDE
// LIMITATIONS: Limited error checking

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

class AltizerProject4 implements Serializable {

  // Inner class defining a binary tree node
  private class TreeNode {
     private TreeNode left;
     private Comparable key;
     private TreeNode right;
  }

  // Instance variables
  private TreeNode root, parent, child;
    private String sourceName = null;

  // Constructor
  public AltizerProject4() {
     root = null;
  }

  // Inserts a key into the set
  public void insert(Comparable key) {
     TreeNode newNode;
     if (search(key)) {
            System.out.println("Duplicates are not allowed");
        }

        else {
        newNode = new TreeNode();
        newNode.key = key;
        newNode.left = null;
        newNode.right = null;
           if (parent == null)
              root = newNode;
           else if (parent.key.compareTo(key) > 0)
              parent.left = newNode;
           else
              parent.right = newNode;
              }
     }

  // Removes a key from the set
  public void remove(Comparable key) {
     if (!search(key)) {
            System.out.println(key + " is not in the database");
        }

        else {
        if (child == root)
           root = deleteNode(root);
        else if (parent.left == child)
           parent.left = deleteNode(parent.left);
        else
           parent.right = deleteNode(parent.right);

        System.out.println("The name " + key + " was deleted");
     }
  }
  // Determines whether a key is in the set
  public boolean contains(Comparable key) {
     if (!search(key))
        return false;
     return true;
        }

  // Private method that searches for a key
  private boolean search(Comparable key) {
     parent = null;
     child = root;
     while (child != null)
     {
        if (child.key.equals(key))
           return true;
        parent = child;
        if (child.key.compareTo(key) > 0)
           child = child.left;
        else
           child = child.right;
     }
     return false;
  }

  // Private method that deletes a node
  private TreeNode deleteNode(TreeNode node) {
     TreeNode inorderSuccessor, successorsParent;

     if (node.right == null)
        return node.left;   // 0-1 Child
     else if (node.left == null)
        return node.right;   // 1 Child
     else {                  // 2 Children
        successorsParent = node.left;
        inorderSuccessor = successorsParent.right;
        if (inorderSuccessor == null) {
           node.left = successorsParent.left;
           node.key = successorsParent.key;
        }
          else {
           while (inorderSuccessor.right != null) {
              successorsParent = inorderSuccessor;
              inorderSuccessor = inorderSuccessor.right;
           }
           successorsParent.right = inorderSuccessor.left;
           node.key = inorderSuccessor.key;
        }
     }
  return node;
  }

    // print tree in order
  public void print() {
  recprint(root);
  System.out.println();
  }
  private void recprint(TreeNode p) { // recursively print the tree
values in sorted order
  if (p == null)
  return;
  recprint (p.left);
  System.out.print(p.key + "\n");
  recprint (p.right);
  }

    // load data from text file
    public void loadData(String sourceName) {
   // Remember the source name.
   this.sourceName = sourceName;
   try {
     // Create a BufferedReader for the file.
     BufferedReader in = new BufferedReader(
         new FileReader(sourceName));
     String name;

     // Read each name and number and add the entry to the list.
     while ( (name = in.readLine()) != null) {
       // Add an entry for this name and number.
       insert(name);
     }

     // Close the file.
     in.close();
   }
   catch (FileNotFoundException ex) {
     // Do nothing - no data to load.
     return;
   }
   catch (IOException ex) {
     System.err.println("Load of directory failed.");
     ex.printStackTrace();
     System.exit(1);
   }
 }

 // begin save method
       /** Method to save the directory.
     pre:  The directory has been loaded with data.
     post: Contents of directory written back to the file in the
           form of name-number pairs on adjacent lines.
           modified is reset to false.
     */
   public void save(String sourceName) {
     try {
       // Create PrintWriter for the file.
       PrintWriter out = new PrintWriter(
           new FileWriter(sourceName));

         // Write the name(s) to the text file.
            // The next line is where the problem is.
            // For some reason I get a 'cannot fine symbol' error at
            // the selection period before print();
            out.print();

       // Close the file.
       out.close();
     }
     catch (Exception ex) {
       System.err.println("Save of directory failed");
       ex.printStackTrace();
       System.exit(1);
     }
   }

} // end class
Andrew Thompson - 26 Oct 2007 08:16 GMT
...
>        // Create PrintWriter for the file.
>        PrintWriter out = new PrintWriter(
[quoted text clipped - 5 lines]
>            // the selection period before print();
>            out.print();

Please refrain from posting 'tabs' to usenet.  That text
quoted above is indented to slightly beyond the start of
the word 'to' in the first sentence, here.

A tool for helping to format code for usenet is here..
<http://www.physci.org/twc.jnlp>
It includes a button to replace tabs with chars.

<hint>
Now, as far as the comiler error message goes.
Do you see any single 'print()' method in the
PrintWriter class that accepts no arguments?
</hint>

The final comment I have is that you can help encourage
people to assist you by providing an SSCCE*.  That example
you posted might have fit most of the requirements of
an SSCCE, but could have been made *much* shorter,
while still displaying the exact error message you are
seeing.

* <http://www.physci.org/codes/sscce.html>

Signature

Andrew Thompson
http://www.athompson.info/andrew/

kaltizer - 26 Oct 2007 12:31 GMT
> ..
>
[quoted text clipped - 35 lines]
>
> Message posted viahttp://www.javakb.com

Please forgive the mistakes in my posting format.  I will look into
the information for posting code before I post again.  I did copy/
paste the code into Notepad, which I thought would remove all
formatting.  Obviously,I was wrong about that!

Now, about the problem at hand.  I was using the out.print() in hopes
of calling my internal print() method.  It prints to the console just
fine, and I had used it before for printing lists, queues, and stacks
to a text file.  But, I see what you are saying about the the
PrintWriter class.  I just have to figure out a way to get the tree
into one of those methods.  That's what I'm having problems
understanding about trees.  I don't have a tree object to perform one
of the PrintWriter methods on.  I guess I need to create a method
along with a binary tree object, and then insert each node into this
tree instance, then call one of the PrintWriter methods to be
performed on this object.  Does that sound like a good plan?
TIA
Andrew Thompson - 26 Oct 2007 12:54 GMT
...
>Please forgive the mistakes in my posting format.  

Please forgive anything I said, that made you feel you
owed me an apology.  It was simply technical advice.  
( Or another way to put that might be..
"I'll forgive you - if you'll forgive me" ;)

For the record, there were no 'mistakes' in your post, I was
just suggesting things that might help get other people 'up
and running' with the problem - faster and more easily.

>...I will look into
>the information for posting code before I post again.  

That is a good strategy!  Not everyone sees the benefit
of preparing an SSCCE, but I am hoping you will.

>..I did copy/
>paste the code into Notepad, which I thought would remove all
>formatting.  Obviously,I was wrong about that!

Yep.  Notepad will retain 'tabs'.

>Now, about the problem at hand.  I was using the out.print() in hopes
>of calling my internal print() method.  It prints to the console just
>fine, and I had used it before for printing lists, queues, and stacks
>to a text file.  But, I see what you are saying about the the
>PrintWriter class.  I just have to figure out a way to get the tree
>into one of those methods.  

There are a number of options for print()ing.  All of them
expect some data.

>...That's what I'm having problems
>understanding about trees.  I don't have a tree object to perform one
>of the PrintWriter methods on.  I guess I need to create a method
>along with a binary tree object, and then insert each node into this
>tree instance, then call one of the PrintWriter methods to be
>performed on this object.  Does that sound like a good plan?

..hmm.  I am probably not the best one to answer that
question.

(Having said that..)
I would probably implement a 'toString()' method on the
'tree structure' being created, and print(theTreeObject).

But I think Roedy has already covered that 'toString()'
aspect better than I could.

Certainly, creating 'an object' that represents this tree
structure would be the way *I'd* go, but I am no 'design guru',
so I will cede to the advice of others - who are.

Signature

Andrew Thompson
http://www.athompson.info/andrew/

Roedy Green - 26 Oct 2007 12:01 GMT
> out.print();

this won't do anything. See http://mindprod.com/applet/fileio.html
for how to write chars to a file with a PrintWriter.
Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com



Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.