Binary search tree to read from file not doing its job why ?

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 3122 Views - Last Post: 08 August 2011 - 03:56 PM Rate Topic: -----

#1 daonlyillwiz  Icon User is offline

  • D.I.C Head

Reputation: -10
  • View blog
  • Posts: 150
  • Joined: 14-March 11

Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 01:34 PM

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;


public class BinarySearchTree {
	/**
	* Construct the tree.
	*/
	public BinarySearchTree( ) {
		root = null;
	}

	/**
	* Insert into the tree.
	* @param x the item to insert.
	* @throws DuplicateItemException if x is already present.
	*/
	public void insert( Comparable x ) {
		try {
			root = insert( x, root );
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	* Remove from the tree..
	* @param x the item to remove.
	* @throws ItemNotFoundException if x is not found.
	*/
	public void remove( Comparable x ) {
		try {
			root = remove( x, root );
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	* Remove minimum item from the tree.
	* @throws ItemNotFoundException if tree is empty.
	*/
	public void removeMin( ) {
		try {
			root = removeMin( root );
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	* Find the smallest item in the tree.
	* @return smallest item or null if empty.
	*/
	public Comparable findMin( ) {
		return elementAt( findMin( root ) );
	}

	/**
	* Find the largest item in the tree.
	* @return the largest item or null if empty.
	*/
	public Comparable findMax( ) {
		return elementAt( findMax( root ) );
	}

	/**
	* Find an item in the tree.
	* @param x the item to search for.
	* @return the matching item or null if not found.
	*/
	public Comparable find( Comparable x ) {
		return elementAt( find( x, root ) );
	}

	/**
	* Make the tree logically empty.
	*/
	public void makeEmpty( ) {
		root = null;
	}

	/**
	* Test if the tree is logically empty.
	* @return true if empty, false otherwise.
	*/
	public boolean isEmpty( ) {
		return root == null;
	}

	/**
	* Internal method to get element field.
	* @param t the node.
	* @return the element field or null if t is null.
	*/
	private Comparable elementAt( BinaryNode t ) {
		return t == null ? null : t.element;
	}

	/**
	* Internal method to insert into a subtree.
	* @param x the item to insert.
	* @param t the node that roots the tree.
	* @return the new root.
	* @throws DuplicateItemException if x is already present.
	*/
	protected BinaryNode insert( Comparable x, BinaryNode t ) throws Exception {
		if( t == null )
			t = new BinaryNode( x );
		else if( x.compareTo( t.element ) < 0 )
			t.left = insert( x, t.left );
		else if( x.compareTo( t.element ) > 0 )
			t.right = insert( x, t.right );
		else
			throw new Exception( x.toString( ) );  // Duplicate
		return t;
	}


	/**
	* Internal method to remove from a subtree.
	* @param x the item to remove.
	* @param t the node that roots the tree.
	* @return the new root.
	* @throws ItemNotFoundException if x is not found.
	*/
	protected BinaryNode remove( Comparable x, BinaryNode t )  throws Exception {
		if( t == null )
			throw new Exception( x.toString( ) );
		if( x.compareTo( t.element ) < 0 )
			t.left = remove( x, t.left );
		else if( x.compareTo( t.element ) > 0 )
			t.right = remove( x, t.right );
		else if( t.left != null && t.right != null ) // Two children
		{
			t.element = findMin( t.right ).element;
			t.right = removeMin( t.right );
		} else
			t = ( t.left != null ) ? t.left : t.right;
		return t;
	}

	/**
	* Internal method to remove minimum item from a subtree.
	* @param t the node that roots the tree.
	* @return the new root.
	* @throws ItemNotFoundException if x is not found.
	*/
	protected BinaryNode removeMin( BinaryNode t )  throws Exception  {
		if( t == null )
			throw new Exception( );
		else if( t.left != null ) {
			t.left = removeMin( t.left );
			return t;
		} else
			return t.right;
	}

	/**
	* Internal method to find the smallest item in a subtree.
	* @param t the node that roots the tree.
	* @return node containing the smallest item.
	*/
	protected BinaryNode findMin( BinaryNode t ) {
		if( t != null )
			while( t.left != null )
				t = t.left;

		return t;
	}

	/**
	* Internal method to find the largest item in a subtree.
	* @param t the node that roots the tree.
	* @return node containing the largest item.
	*/
	private BinaryNode findMax( BinaryNode t ) {
		if( t != null )
			while( t.right != null )
				t = t.right;
		return t;
	}

	/**
	* Internal method to find an item in a subtree.
	* @param x is item to search for.
	* @param t the node that roots the tree.
	* @return node containing the matched item.
	*/
	private BinaryNode find( Comparable x, BinaryNode t ) {
		while( t != null ) {
			if( x.compareTo( t.element ) < 0 )
				t = t.left;
			else if( x.compareTo( t.element ) > 0 )
				t = t.right;
			else
				return t;    // Match
		}
		return null;         // Not found
	}

	/** The tree root. */
	protected BinaryNode root;
	class BinaryNode {
		// Constructors
		BinaryNode( Comparable theElement ) {
			element = theElement;
			left = right = null;
		}

		// Friendly data; accessible by other package routines
		Comparable element;      // The data in the node
		BinaryNode left;         // Left child
		BinaryNode right;        // Right child
		public Object getValue() {
			// TODO Auto-generated method stub
			return null;
		}
		public Object getChildren() {
			// TODO Auto-generated method stub
			return null;
		}
	}
	public boolean contains(BinaryNode n, E value){
		if(n.getValue().equals(value))
			return true;
		for(int i = 0; i < n.getChildren().size; i++){
			if(contains(n.getChildren().get(i)))
				return true;
		}
		return false;
	}
	// Test program
	public static void main(String args[]){
		BinarySearchTree tree=new BinarySearchTree();
		try{
			FileInputStream fstream = new FileInputStream("textfile.txt");
			DataInputStream in = new DataInputStream(fstream);
			BufferedReader br = new BufferedReader(new InputStreamReader(in));
			String line=null;	
			while ((line = br.readLine()) != null){	//Read File Line By Line
				String[] valueStrs = line.split(" ");
				int[] values = new int[valueStrs.length];
				for(int i = 0; i < values.length; i++)
					values[i] = Integer.parseInt(valueStrs[i]);
				for(int i = 0; i < values.length; i++)
					tree.insert(values[i]);
			}
			in.close();	//Close the input stream
		}
		catch (Exception e){	//Catch exception if any
			System.err.println("Error: " + e.getMessage());
		}
	}

	//when you first call the method feed the root node as a parameter

}





Well the purpose of this program is to read a file called textfile.txt and read the numbers in that file line by line and differentiate each number by the space between them, then it should put those numbers into the tree and output them in order from smallest to biggest or PLOT a tree. Whats wrong. i get no error messages but nothing occurs.

Is This A Good Question/Topic? 0
  • +

Replies To: Binary search tree to read from file not doing its job why ?

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,273
  • Joined: 27-December 08

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 01:36 PM

I don't see where you try and output the Tree.
Was This Post Helpful? 0
  • +
  • -

#3 daonlyillwiz  Icon User is offline

  • D.I.C Head

Reputation: -10
  • View blog
  • Posts: 150
  • Joined: 14-March 11

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 01:38 PM

How would i go about doing so?
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,273
  • Joined: 27-December 08

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 01:44 PM

You could override the toString() method for your BinaryTree and BinaryNode classes and define it to output based on the Nodes. I used a helper method to build the String recursively.

BinaryTree toString()
-Simply return root.toString()

BinaryNode toString()
-Call the helper method, passing this and 0

BinaryNode helpAssembleString(BinaryNode root, int numTabs)
-Create a String displaying the value for root
-Recurse left, adding 1 to numTabs
-Recurse right, adding 1 to numTabs
-Return the String



Also, the Comparable interface is generic. I would recommend making your BinaryTree and BinaryNode classes generic. This is much cleaner, and assures that all the elements will be mutually Comparable, so there is no chance of comparing apples and oranges, so to speak.
class BinaryTree<T extends Comparable<? super T>>{

     class BinaryNode<T>{}

     public T find(T value){}
}


Was This Post Helpful? 0
  • +
  • -

#5 daonlyillwiz  Icon User is offline

  • D.I.C Head

Reputation: -10
  • View blog
  • Posts: 150
  • Joined: 14-March 11

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 01:49 PM

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

public class BinarySearchTree {
	/**
	* Construct the tree.
	*/
	public BinarySearchTree( ) {
		root = null;
	}

	/**
	* Insert into the tree.
	* @param x the item to insert.
	* @throws DuplicateItemException if x is already present.
	*/
	public void insert( Comparable x ) {
		try {
			root = insert( x, root );
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	* Remove from the tree..
	* @param x the item to remove.
	* @throws ItemNotFoundException if x is not found.
	*/
	public void remove( Comparable x ) {
		try {
			root = remove( x, root );
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	* Remove minimum item from the tree.
	* @throws ItemNotFoundException if tree is empty.
	*/
	public void removeMin( ) {
		try {
			root = removeMin( root );
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	/**
	* Find the smallest item in the tree.
	* @return smallest item or null if empty.
	*/
	public Comparable findMin( ) {
		return elementAt( findMin( root ) );
	}

	/**
	* Find the largest item in the tree.
	* @return the largest item or null if empty.
	*/
	public Comparable findMax( ) {
		return elementAt( findMax( root ) );
	}

	/**
	* Find an item in the tree.
	* @param x the item to search for.
	* @return the matching item or null if not found.
	*/
	public Comparable find( Comparable x ) {
		return elementAt( find( x, root ) );
	}

	/**
	* Make the tree logically empty.
	*/
	public void makeEmpty( ) {
		root = null;
	}

	/**
	* Test if the tree is logically empty.
	* @return true if empty, false otherwise.
	*/
	public boolean isEmpty( ) {
		return root == null;
	}
	/**
	* Internal method to get element field.
	* @param t the node.
	* @return the element field or null if t is null.
	*/
	private Comparable elementAt( BinaryNode t ) {
		return t == null ? null : t.element;
	}
	/**
	* Internal method to insert into a subtree.
	* @param x the item to insert.
	* @param t the node that roots the tree.
	* @return the new root.
	* @throws DuplicateItemException if x is already present.
	*/
	protected BinaryNode insert( Comparable x, BinaryNode t ) throws Exception {
		if( t == null )
			t = new BinaryNode( x );
		else if( x.compareTo( t.element ) < 0 )
			t.left = insert( x, t.left );
		else if( x.compareTo( t.element ) > 0 )
			t.right = insert( x, t.right );
		else
			throw new Exception( x.toString( ) );  // Duplicate
		return t;
	}
	/**
	* Internal method to remove from a subtree.
	* @param x the item to remove.
	* @param t the node that roots the tree.
	* @return the new root.
	* @throws ItemNotFoundException if x is not found.
	*/
	protected BinaryNode remove( Comparable x, BinaryNode t )  throws Exception {
		if( t == null )
			throw new Exception( x.toString( ) );
		if( x.compareTo( t.element ) < 0 )
			t.left = remove( x, t.left );
		else if( x.compareTo( t.element ) > 0 )
			t.right = remove( x, t.right );
		else if( t.left != null && t.right != null ){	//two childeren
			t.element = findMin( t.right ).element;
			t.right = removeMin( t.right );
		} else
			t = ( t.left != null ) ? t.left : t.right;
		return t;
	}
	/**
	* Internal method to remove minimum item from a subtree.
	* @param t the node that roots the tree.
	* @return the new root.
	* @throws ItemNotFoundException if x is not found.
	*/
	protected BinaryNode removeMin( BinaryNode t )  throws Exception  {
		if( t == null )
			throw new Exception( );
		else if( t.left != null ) {
			t.left = removeMin( t.left );
			return t;
		} else
			return t.right;
	}
	/**
	* Internal method to find the smallest item in a subtree.
	* @param t the node that roots the tree.
	* @return node containing the smallest item.
	*/
	protected BinaryNode findMin( BinaryNode t ) {
		if( t != null )
			while( t.left != null )
				t = t.left;

		return t;
	}
	/**
	* Internal method to find the largest item in a subtree.
	* @param t the node that roots the tree.
	* @return node containing the largest item.
	*/
	private BinaryNode findMax( BinaryNode t ) {
		if( t != null )
			while( t.right != null )
				t = t.right;
		return t;
	}
	/**
	* Internal method to find an item in a subtree.
	* @param x is item to search for.
	* @param t the node that roots the tree.
	* @return node containing the matched item.
	*/
	private BinaryNode find( Comparable x, BinaryNode t ) {
		while( t != null ) {
			if( x.compareTo( t.element ) < 0 )
				t = t.left;
			else if( x.compareTo( t.element ) > 0 )
				t = t.right;
			else
				return t;    // Match
		}
		return null;         // Not found
	}
	/** The tree root. */
	protected BinaryNode root;
	// Test program
	public static void main(String args[]){
		BinarySearchTree tree=new BinarySearchTree();
		try{
			FileInputStream fstream = new FileInputStream("textfile.txt");
			DataInputStream in = new DataInputStream(fstream);
			BufferedReader br = new BufferedReader(new InputStreamReader(in));
			String line=null;	
			while ((line = br.readLine()) != null){	//Read File Line By Line
				String[] valueStrs = line.split(" ");
				int[] values = new int[valueStrs.length];
				for(int i = 0; i < values.length; i++)
					values[i] = Integer.parseInt(valueStrs[i]);
				printAscending(values); //prints here
				for(int i = 0; i < values.length; i++)
					tree.insert(values[i]);
			}
			in.close();	//Close the input stream
		}
		catch (Exception e){	//Catch exception if any
			System.err.println("Error: " + e.getMessage());
		}
	}

	public static void printAscending(int[] values){
		//just doing bubble sort because it's easy
		int i, j,t=0;
		for(i = 0; i < n; i++){
			for(j = 1; j < (n-i); j++){
				if(values[j-1] > values[j]){
					t = values[j-1];
					values[j-1]=values[j];
					values[j]=t;
				}
			}
		}
		String output = "";
		for(i = 0; i < values.length; i++)
			output += values[i]+" ";
		System.out.println(output);
	}
}
class BinaryNode {
	// Constructors
	BinaryNode( Comparable theElement ) {
		element = theElement;
		left = right = null;
	}
	// Friendly data; accessible by other package routines
	Comparable element;      // The data in the node
	BinaryNode left;         // Left child
	BinaryNode right;        // Right child
	public Object getValue() {
		// TODO Auto-generated method stub
		return null;
	}
	public Object getChildren() {
		// TODO Auto-generated method stub
		return null;
	}
}





ERror:

Exception in thread "main" java.lang.Error: Unresolved compilation problems:
n cannot be resolved to a variable
n cannot be resolved to a variable

at BinarySearchTree.printAscending(BinarySearchTree.java:223)
at BinarySearchTree.main(BinarySearchTree.java:209)
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,273
  • Joined: 27-December 08

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 01:52 PM

You don't define the variable n. Why not just use values.length instead?

You might also consider using the Arrays.sort() method instead of bubble sort. It uses an optimized Quicksort, and it's already written so you don't have to deal with writing additional code.
Was This Post Helpful? 0
  • +
  • -

#7 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8346
  • View blog
  • Posts: 31,908
  • Joined: 06-March 08

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 01:56 PM

In your bubble sort what is that n ?

for(i = 0; i < n; i++){

you probably want

int n = values.length;
Was This Post Helpful? 0
  • +
  • -

#8 daonlyillwiz  Icon User is offline

  • D.I.C Head

Reputation: -10
  • View blog
  • Posts: 150
  • Joined: 14-March 11

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 02:01 PM

pbl, thank you so much i so overlooked that lol.

Problem fixed

How would it be possible to plot this info on a tree now and out put it to look like a tree ? That is something ive never done before lol.
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,273
  • Joined: 27-December 08

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 02:30 PM

Use my suggestion about indentations. It will look more like a File Tree, but it is easier than playing around with spacing.
Was This Post Helpful? 0
  • +
  • -

#10 daonlyillwiz  Icon User is offline

  • D.I.C Head

Reputation: -10
  • View blog
  • Posts: 150
  • Joined: 14-March 11

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 03:06 PM

How does one indent in java and how would i be able to indent first value then second third etc depending on how many numbers in the textfile accordingly?
Was This Post Helpful? 0
  • +
  • -

#11 daonlyillwiz  Icon User is offline

  • D.I.C Head

Reputation: -10
  • View blog
  • Posts: 150
  • Joined: 14-March 11

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 03:16 PM

I had an idea suppose my textfile had the following numbers:
11 18 1 3 4 2

right now my program will print it as
1 2 3 4 11 18

how would i be able to print it as
1
2 3
4 11 18

??
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,273
  • Joined: 27-December 08

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 03:20 PM

You would probably do best to store a Map<Integer, String>, with the Integer representing the row/depth/level. When you go down a row, increment the counter and get the corresponding String. Append the data to that String, and put() it back in the Map. Then when you go up a level, subtract one from the counter. You can use breadth or depth first traversals here.
Was This Post Helpful? 0
  • +
  • -

#13 daonlyillwiz  Icon User is offline

  • D.I.C Head

Reputation: -10
  • View blog
  • Posts: 150
  • Joined: 14-March 11

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 03:44 PM

How do i go about applying that to my code im a little confused ?
Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,273
  • Joined: 27-December 08

Re: Binary search tree to read from file not doing its job why ?

Posted 04 August 2011 - 06:04 PM

What you need is a HashMap<Integer, String> instance variable as I described above, as well as overriding the toString() method for your BinaryTree class and a helper method for toString(). The helper method should recursively traverse the Tree. Are you familiar with the breadth-first and depth-first traversal algorithms? If not, you should look them up and choose one of them. The basic logic of the helper method is as follows:
public void buildStrings(BinaryNode node, int count){
   //get() the String from the Map passing count as the param
   //append the node's element to the String
   //put the String back in the Map
   //recurse for node.left and node.right, incrementing count
}


Was This Post Helpful? 0
  • +
  • -

#15 daonlyillwiz  Icon User is offline

  • D.I.C Head

Reputation: -10
  • View blog
  • Posts: 150
  • Joined: 14-March 11

Re: Binary search tree to read from file not doing its job why ?

Posted 08 August 2011 - 03:49 PM

Got it thanks alot for all your help guys
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2