Input issues in a binary search tree

Having problems reading in user input into a binary search tree

Page 1 of 1

2 Replies - 3665 Views - Last Post: 22 November 2009 - 01:30 PM Rate Topic: -----

#1 brucezepplin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 41
  • Joined: 11-November 09

Input issues in a binary search tree

Posted 19 November 2009 - 02:38 PM

Hi guys, I've written a code that intends to take the user input from a command line, and then insert it into to a binary search tree. Input has always confused me in java! Just need a few pointers! Here is my code:

import java.io.*;
import java.io.FileReader;
import java.io.IOException;

public class SearchTree {


   static class TreeNode {
		   // An object of type TreeNode represents one node
		   // in a binary tree of strings.
	  String item;	  // The data in this node.
	  TreeNode left;	// Pointer to left subtree.
	  TreeNode right;   // Pointer to right subtree.
	  TreeNode(String str) {
			 // Constructor.  Make a node containing the specified string.
		 item = str;
	  }
   }  // end nested class TreeNode

   
   static TreeNode root;  // Pointer to the root node in a binary tree.  This
						  // tree is used in this program as a binary sort tree.
						  // The tree is not allowed to contain duplicate
						  // items.  When the tree is empty, root is null.
   
   

   public static void main(String[] args) {
	  
	  System.out.println("This programs stores strings that you enter in a binary sort");
	  System.out.println("tree.  After each items is inserted, the contents of the tree");
	  System.out.println("are displayed.  The number of nodes in the tree is also output.");	  
	  System.out.println("Duplicate entries are ignored.");

	  while (true) {
			  // Get one string from the user, insert it into the tree,
			  // and print some information about the tree.  Exit if the
			  // user enters an empty string.  Note that all strings are
			  // converted to lower case.
		  System.out.println("\n\nEnter a string to be inserted, or press return to end.");
		  System.out.print("?  ");
		  
		  String item = StdIn.readString();
		  int c;
		  if ((c = item.read()) == 0)
			 break;
		  if (treeContains(root,item)) {
				 // Don't insert a second copy of an item that is already
				 // in the tree.
			 System.out.println("\nThat item is already in the tree.");
		  }
		  else {
			 treeInsert(item);  // Add user's string to the tree.
			 System.out.println("\nThe tree contains " + countNodes(root) + " items.");
			 System.out.println("\nContents of tree:\n");
			 treeList(root);
		  }
	  }  // end while
	  
	  System.out.println("\n\nExiting program.");
	  
   }  // end main()
   
   
   static void treeInsert(String newItem) {
		  // Add the item to the binary sort tree to which the global
		  // variable "root" refers.  (Note that root can't be passed as
		  // a parameter to this routine because the value of root might
		  // change, and a change in the value of a formal parameter does
		  // not change the actual parameter.)
	  if ( root == null ) {
			 // The tree is empty.  Set root to point to a new node containing
			 // the new item.  This becomes the only node in the tree.
		 root = new TreeNode( newItem );
		 return;
	  }
	  TreeNode runner;  // Runs down the tree to find a place for newItem.
	  runner = root;   // Start at the root.
	  while (true) {
		 if ( newItem.compareTo(runner.item) < 0 ) {
				  // Since the new item is less than the item in runner,
				  // it belongs in the left subtree of runner.  If there
				  // is an open space at runner.left, add a new node there.
				  // Otherwise, advance runner down one level to the left.
			if ( runner.left == null ) {
			   runner.left = new TreeNode( newItem );
			   return;  // New item has been added to the tree.
			}
			else
			   runner = runner.left;
		 }
		 else {
				  // Since the new item is greater than or equal to the item in
				  // runner it belongs in the right subtree of runner.  If there
				  // is an open space at runner.right, add a new node there.
				  // Otherwise, advance runner down one level to the right.
			if ( runner.right == null ) {
			   runner.right = new TreeNode( newItem );
			   return;  // New item has been added to the tree.
			}
			else
			   runner = runner.right;
		  }
	  } // end while
   }  // end treeInsert()
   
   
   static boolean treeContains( TreeNode root, String item ) {
		  // Return true if item is one of the items in the binary
		  // sort tree to which root points.   Return false if not.
	  if ( root == null ) {
			// Tree is empty, so it certainly doesn't contain item.
		 return false;
	  }
	  else if ( item.equals(root.item) ) {
			// Yes, the item has been found in the root node.
		 return true;
	  }
	  else if ( item.compareTo(root.item) < 0 ) {
			// If the item occurs, it must be in the left subtree.
		 return treeContains( root.left, item );
	  }
	  else {
			// If the item occurs, it must be in the right subtree.
		 return treeContains( root.right, item );
	  }
   }  // end treeContains()
   

   static void treeList(TreeNode node) {
		  // Print the items in the tree in postorder, one item
		  // to a line.  Since the tree is a sort tree, the output
		  // will be in increasing order.
	  if ( node != null ) {
		  treeList(node.left);			 // Print items in left subtree.
		  System.out.println("  " + node.item);  // Print item in the node.
		  treeList(node.right);			// Print items in the right subtree.
	  }
   } // end treeList()
   

   static int countNodes(TreeNode node) {
		 // Count the nodes in the binary tree to which node 
		 // points.  Return the answer.
	  if ( node == null ) {
			  // Tree is empty, so it contains no nodes.
		 return 0;
	  }
	  else {
			 // Add up the root node and the nodes in its two subtrees.
		 int leftCount = countNodes( node.left );
		 int rightCount = countNodes( node.right );
		 return  1 + leftCount + rightCount;  
	  }
   } // end countNodes()
   

}


And when I complile the programme I get:


arron@arron-laptop:~/University$ javac SearchTree.java
SearchTree.java:44: cannot find symbol
symbol : variable StdIn
location: class SearchTree
String item = StdIn.readString();
^
SearchTree.java:46: cannot find symbol
symbol : method read()
location: class java.lang.String
if ((c = item.read()) == 0)
^
2 errors


I've been mulling this over and am pretty much getting anywhere. Oh btw I'm sorting names into alphabetical order.....

Thanks in advance for any help.

Is This A Good Question/Topic? 0
  • +

Replies To: Input issues in a binary search tree

#2 japanir  Icon User is offline

  • jaVanir
  • member icon

Reputation: 1010
  • View blog
  • Posts: 3,025
  • Joined: 20-August 09

Re: Input issues in a binary search tree

Posted 20 November 2009 - 11:33 AM

item i a String object as you declared it:
String item = = StdIn.readString();
there is no method read() in String class:
if ((c = item.read()) == 0)

the first error occurs since your comiler doesnt recognize what is StdIn.readString();
neigher do i...
is that an object? a class you created?
what value will be passed to item?
Was This Post Helpful? 0
  • +
  • -

#3 brucezepplin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 41
  • Joined: 11-November 09

Re: Input issues in a binary search tree

Posted 22 November 2009 - 01:30 PM

I would like to ideally input a .txt file that contains names and birthdays, split up all of the strings and put them into a binary tree. but for the time being i am making do with entering names at the user input and sorting them alphabetically in a binary tree. So Im guessing I need to add something like:

String item = Str.parseString( args[0]);

and then read the user input with:

item = parse_suit(StdIn.readString()).

at least i think so........



View Postjapanir, on 20 Nov, 2009 - 10:33 AM, said:

item i a String object as you declared it:
String item = = StdIn.readString();
there is no method read() in String class:
if ((c = item.read()) == 0)

the first error occurs since your comiler doesnt recognize what is StdIn.readString();
neigher do i...
is that an object? a class you created?
what value will be passed to item?



*ahem*

parse_item(StdIn.readString())

even
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1