The assignment is to complete the implementation of a group of files that create and test a binary search tree. It takes in 2 text files of integers, creates a tree with the first and uses the second to compare to the tree and tell whether of not each integer is in the tree. I am having an issue with the MySearchTree class. I do not know how to read in a file of integers and build a tree using them. Also the preOrder, postOrder, and inOrder methods have already been implemented in BinaryNode class so I do not know what to put in those methods in the MySearchTree class. Can anyone help? Here is each class to give you a better idea of what I am talking about:

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

// Implements a binary search tree.
public class MySearchTree implements BSearchTree{
	
	private BinaryNode root;
	private int size;
	
	// Create an empty binary search tree.
	public MySearchTree() 
	{
		root = null;
	}
	
	
	
	// Print this tree's elements in pre-order each separated by a space.
	public void preOrder() 
	{  
	
	}

	
	// Print this tree's elements in order each separated by a space.
	public void inOrder() 
	{  
		
	}

	 	
	// Print this tree's elements in post-order each separated by a space.
	public void postOrder() 
	{  
		
	}
	 	
	// buildTree - read integers from text file and build this search tree..
	public void buildTree(String fileName, String[] args)
	{
	
	}
	
	
	// Returns true if item is found in this tree else returns false.
	public boolean find(Comparable c) 
	{ 
		if(root != null) return root.find(c);
		return false;
	}
	
	// Returns number of nodes in this search tree.
	public int size() { return size; }

}
// Implements a binary node with three modes of depth-first search.
public class BinaryNode
{
   protected Comparable element;
   protected BinaryNode left;
   protected BinaryNode right;
   public BinaryNode(Comparable c) { this(c, null, null); }
   public BinaryNode(Comparable  c, BinaryNode aLeft, BinaryNode aRight)  
   {
		element = c;
		left = aLeft;
		right = aRight;
   }
   
   // getLeft - return left child.
   public BinaryNode getLeft() { return left; }
   
   // getRight - return right child.
   public BinaryNode getRight() { return right; }
   
   // getElement - return element.
   public Comparable getElement() { return element; }
   
     // getLeft - return left child.
   public void setLeft(BinaryNode n) { left = n; }
   
   // getRight - return right child.
   public void setRight(BinaryNode n) { right = n; }
   
   // getElement - return element.
   public void setElement(Comparable c) { element = c; }
   
   // Print this tree's elements in pre-order each separated by a space.
   void preOrder()
   {
	   System.out.print( element + " " );
	   if( left != null ) left.preOrder( );
	   if( right != null ) right.preOrder( );
   }
	
   // Print this tree's elements in order each separated by a space.
   void inOrder()
   {
	   if(left != null) left.inOrder( );
	   System.out.print(element + " ");
	   if(right != null) right.inOrder( );
   }
	 	
   // Print this tree's elements in post order each separated by a space.
   void postOrder()
   {
	   if( left != null ) left.postOrder( );
	   if( right != null ) right.postOrder( );
	   System.out.print( element + " " );
   }
   
   	// Returns true is item is foundin this tree else returns false.
	public boolean find(Comparable c)
	{
		if(c.compareTo(element) == 0)
		return true;
		else if(c.compareTo(element) < 0) {
		if(left == null) return false;
		else return left.find(c);
		}
		else {
		if(right == null) return false;
		else return right.find(c);
		}
	}
}
import java.util.Scanner;

import java.io.*;



public class ClientForSearchTree{
	
	// Builds a search tree with the integers in the first input file then 
	
// determines which integers in the second input file are in the search
	
// tree. Finally prints the search tree using all 3 depth-first traversals.
	

	public static void main(String args[]){
		
		if(args.length != 2){

			System.out.println("Usage: MySearchTree file1 file2");
			System.exit(1);
		
		}

		
		MySearchTree tree = new MySearchTree();
		
		try{
			
			Scanner sc = new Scanner(new File(args[1]));
			tree.buildTree(args[0]);
			while(sc.hasNextInt()){

				Integer iValue = new Integer(sc.nextInt());

			
				if(tree.find(iValue))

					System.out.println(iValue + " is in the tree.");
				
				else

					System.out.println(iValue + " is not in the tree.");


			}


			System.out.println("\nPre-order traversal:");
			
			tree.preOrder();
			
			System.out.println("\n\nIn-order traversal:");
			
			tree.inOrder();
			
			System.out.println("\n\nPost-order traversal:");
	
			tree.postOrder();
			
			System.out.println();
		
		}
		
		catch(Exception  e){
			
			System.err.println(e.getMessage());

			System.exit(1);
		
		}
	
	}

}
// Defines a public set of methods for a binary search tree.
public interface BSearchTree
{
		
	// Print this tree's elements in pre order each separated by a space.
	void preOrder();
	
	// Print this tree's elements in order each separated by a space.
	void inOrder();
	 	
	// Print this tree's elements in post order each separated by a space.
	void postOrder(); 
	 	
	// buildTree - read integers from text file and build this search tree.
	void buildTree(String fileName);
	
	// Returns true is item is found in this tree else returns false.
	boolean find(Comparable c);
}

Recommended Answers

All 7 Replies

how to read in a file of integers and build a tree using them

Start with the reading the file of integers.
When you can read them into a variable, add logic to add them to the tree.

Then read the other file and test each number is in the tree

I have this so far. It has the general idea behind it, but it's not working. Any clue?

public void buildTree(String fileName)
	{
	
		try {
			Scanner sc = new Scanner(new File("file1.txt"));
			Integer element = new Integer(sc.nextInt());
			Comparable c;
			
			if(root == null){
				root = new BinaryNode(element);
			}
			
			while(sc.hasNextInt()){
				
				if(c.compareTo(element) == 0){
					return;
				}
				
				if (c.compareTo(element) < 0) {

					if (left == null) {

	                        left = new BinaryNode(element);

	                  } else

	                        return left.buildTree(element);

	            } else if (c.compareTo(element) > 0) {

	                  if (right == null) {

	                        right = new BinaryNode(element);  

	                  } else

	                        return right.buildTree(element);

	            }

	      }
	
		} catch (FileNotFoundException e) {
			
			e.printStackTrace();
		}

		
	}

it's not working.

Please explain. What happens? Post the errors here or show the output and add comments describing what is wrong and what it should be.

Okay, so here is the MySearchTree class finished, when I run the client code, it prints out null and thats it. I dont understand what I have wrong.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

// Implements a binary search tree.
public class MySearchTree implements BSearchTree{
	
	private BinaryNode root;
	private int size;
	
	// Create an empty binary search tree.
	public MySearchTree(){
		root = null;
	}
	
	// Print this tree's elements in pre-order each separated by a space.
	public void preOrder(){
		
		root.preOrder();
	}
	
	// Print this tree's elements in order each separated by a space.
	public void inOrder(){
		
		root.inOrder();
	}
	 	
	// Print this tree's elements in post-order each separated by a space.
	public void postOrder(){
		
		root.postOrder();
	}

	// buildTree - read integers from text file and build this search tree..
	public void buildTree(String fileName){
	
		try{
			
			Scanner sc = new Scanner(new File(fileName));
			
			int element = 0;
			Comparable c = null;
			
			
			if(root == null)
				root = new BinaryNode(element);
			
			
			while(sc.hasNextInt()){
				
				BinaryNode temp = root;
				
				while(temp != null){
	
					element = Integer.parseInt(sc.next());
				
					if(c.compareTo(element) == 0){
						temp = null;
					}
				
					if (c.compareTo(element) < 0) {

						if (temp.left == null)
						
							temp.left = new BinaryNode(element);

						else if (temp.right == null)
	                	 
							temp.right = new BinaryNode(element);
					}
				
				}
			}
			
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}

	}
	
	
	// Returns true if item is found in this tree else returns false.
	public boolean find(Comparable c) 
	{ 
		if(root != null)
			return root.find(c);
		return false;
	}
	
	// Returns number of nodes in this search tree.
	public int size() { return size; }

}

when I run the client code, it prints out null and thats it

Could you copy the output from the program that shows its input and its output and paste it here. Add printlns to the code to show all of the input after it is read.

So the issue is reading file1.txt, which is:
30 10
20
50 40
5
60

file2.txt is:
5 10 11 20 21
30
31
40 41 50
51 60 61


I have revised MySearchTree class some more:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

// Implements a binary search tree.
public class MySearchTree implements BSearchTree{
	
	private BinaryNode root;
	private int size;
	
	// Create an empty binary search tree.
	public MySearchTree(){
		root = null;
		size = 0;
	}
	
	// Print this tree's elements in pre-order each separated by a space.
	public void preOrder(){
		root.preOrder();
	}
	
	// Print this tree's elements in order each separated by a space.
	public void inOrder(){
		root.inOrder();
	}
	 	
	// Print this tree's elements in post-order each separated by a space.
	public void postOrder(){
		root.postOrder();
	}

	// buildTree - read integers from text file and build this search tree..
	public void buildTree(String fileName){
		
		int element = 0;
		Comparable c = null;
	
		try{
			
			Scanner sc = new Scanner(new File(fileName));
		
			while(sc.hasNextInt()){
				
				BinaryNode tempRoot = root;
	
				element = Integer.parseInt(sc.next());
				
				if(root == null)
					root = new BinaryNode(element);
					
				while(tempRoot != null){
					if(c.compareTo(tempRoot.getElement()) == 0){
						tempRoot = null;
					}
				
					if (c.compareTo(tempRoot.getElement()) < 0) {

						if (tempRoot.getLeft() == null)
						
							tempRoot.setLeft(new BinaryNode(element));

						else if (tempRoot.getRight() == null)
	                	 
							tempRoot.setRight(new BinaryNode(element));
						else 
							tempRoot = tempRoot.getRight();
					}	
				}
			}	
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}
	
	
	// Returns true if item is found in this tree else returns false.
	public boolean find(Comparable c) 
	{ 
		if(root != null)
			return root.find(c);
		return false;
	}
	
	// Returns number of nodes in this search tree.
	public int size() { return size; }

}

and the output is:
java.io.FileNotFoundException: file1.txt; (The system cannot find the file specified)
at java.io.FileInputStream.open(Native Method)
at java.io.FileInputStream.<init>(Unknown Source)
at java.util.Scanner.<init>(Unknown Source)
at MySearchTree.buildTree(MySearchTree.java:40)
at ClientForSearchTree.main(ClientForSearchTree.java:31)
5 is not in the tree.
10 is not in the tree.
11 is not in the tree.
20 is not in the tree.
21 is not in the tree.
30 is not in the tree.
31 is not in the tree.
40 is not in the tree.
41 is not in the tree.
50 is not in the tree.
51 is not in the tree.
60 is not in the tree.
61 is not in the tree.

Pre-order traversal:
null

You should add ids to the values you print out to easily identify them:
println("var=" + var);

Your printout doesn't show what the program read in. You need to print it out to be sure it is reading all of the file.

While you are debugging the program, reduce the number of items you are working with to the bare minimum to test with. 3 or 4 should be enough.

No way to test your program without code that compiles and executes. Your one method is not testable.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.