Results 1 to 14 of 14
  1. #1
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Turning text file into Binary Search Tree

    I was given a file and told to turn it into a Binary Tree. It's not a BST as I implied in the title, that was a mistake. I have gotten it read into my program, extracted the information from it and am left with this.
    Java Code:
    (8(2()())(13()(4)))
    That is what I have to turn into the tree.

    I am having a hard time developing a procedure that will turn it into a tree. The above tree is supposed to look like:
    Turning text file into Binary Search Tree-tree.jpg

    with each leaf defined as (Integer () () )

    Here is the code I have so far, using Stacks to try and move things around.
    Java Code:
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.Scanner;
    import java.util.Stack;
    /**
     * 
     * 	What Works: I can strip the number from the beginning of the String, and put it into a variable.
     * 
     * 	What doesn't work: I cannot make the actual tree itself.
     * 
     * 
     * 
     *
     */
    
    public class Tree {
    	
    	static Node<Integer> head = null; 
    	
    	static int Operand,SubStringIndex,SIndex = 0,numItems; //Used with the Separator method. 
    	static int Index = 0,secondIndex = Index+1;  //Used with the stack
    	static Stack<Integer> holder= new Stack<Integer>(); 
    	
    	 
    	 
    	
    
    	
    	public static void main(String[] args) throws FileNotFoundException
    	{
    		Scanner FileReader = new Scanner(new File("simpletree.txt"));
    		String input = FileReader.nextLine();
    		
    		String treeText = Separator(input); 
    		
    		System.out.println("The String stripped of its operand " + treeText);
    		System.out.println("The Operand to search for " + Operand);
    		Insert(treeText); 
    		 
    	 
    		
    	
    
    		
    		
    		 
    	}
    	
    	//Strips out the number to test, and returns the string to be inserted into the tree. 
    	public static String Separator(String input)
    	{
    		while(input.charAt(SIndex) != '(')
    		{
    			SubStringIndex++;
    			SIndex++; 
    		}
    		//System.out.println(SubStringIndex); 
    		Operand = Integer.parseInt(input.substring(0,SubStringIndex)); 
    		return input.substring(SubStringIndex); 
    	}
    	
    	@SuppressWarnings({ "unchecked", "rawtypes" })
    	
    	
    	
    	public static void Insert(String input)
    	{
    
    		
    		for(int i = 0; i < input.length(); i++)
    		{
    		while(secondIndex < input.length())
    		{
    			if(input.charAt(Index) == '(')
    			{
    				if(input.charAt(secondIndex) == '0' || input.charAt(secondIndex) == '1' || input.charAt(secondIndex) == '2' || input.charAt(secondIndex) == '3' || input.charAt(secondIndex) == '4' || input.charAt(secondIndex) == '5' || input.charAt(secondIndex) == '6'
    						|| input.charAt(secondIndex) == '7' || input.charAt(secondIndex) == '8' || input.charAt(secondIndex) == '9')
    				{
    					
    					Character charNumTBI = input.charAt(secondIndex); 
    					String numTobeInserted = charNumTBI.toString(); 
    					secondIndex ++;  
    					Index++; 
    					while(input.charAt(secondIndex) != '(' && input.charAt(secondIndex) != ')' )
    					{
    						numTobeInserted += input.toString().charAt(secondIndex); 
    						secondIndex++; 
    						Index++; 
    					}
    					
    					
    					
    					 
    					System.out.println("Number to be inserted " + numTobeInserted); 
    					holder.push(Integer.parseInt(numTobeInserted)); 
    					 
    					
    				}
    				
    				else if(input.charAt(secondIndex) == ')')
    				{
    					Index++; 
    					secondIndex++; 
    				}
    				
    				 
    			}
    			
    			if(input.charAt(Index) != '(' && input.charAt(Index) != ')' )
    			{
    				Index++; 
    				secondIndex++; 
    			}
    			
    			
    			
    			if(input.charAt(Index) == ')')
    			{
    				 
    				
    				if(head == null)
    				{
    					head = new Node<Integer>(holder.pop(),null,null);
    					
    				}
    				
    				else if(head.returnLeft() == null)
    				{
    					
    					
    					Node alpha = new Node<Integer>(holder.pop(),null,null);
    					head.setLeft(alpha); 
    				}
    				
    				else if (head.returnRight() == null)
    				{
    					
    					Node alpha = new Node<Integer>(holder.pop(),null,null); 
    					head.setRight(alpha);
    
    				}
    				 
    				Index++;
    				secondIndex++; 
    				 
    			}
    			
    			 
    			
    			
    			
    		} // end of while loop. 
    			
    		} 
    		 
    	}
    	
    	
    	
    	
    	
    	
    
    }
    To save you the headache of going through the code, I can tell you where the code goes awry based on me tracing through it manually. It eventually throws an empty stack exception, even though the tree is properly formatted in the text. This means there is something wrong with my code, and I believe the problem lies here

    Java Code:
    	else if(input.charAt(secondIndex) == ')')
    				{
    					Index++; 
    					secondIndex++; 
    				}
    This checks to see if the character following a '(' is a ')'. I am unsure of what to do with it if it is.

    Another problem is that because the input string has two leaves after the 2, represented by () and then it is followed by another ), it tries top pop a value of the stack that is not there.


    I fear since I only have one class left that I will not be able to get suitable help from my professor. I was hoping someone here could give me some advice on how to approach this. Thanks for any help.
    Last edited by Wnt2bsleepin; 05-06-2012 at 11:36 PM.

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,812
    Rep Power
    25

    Default Re: Turning text file into Binary Search Tree

    Need the Node class to compile and test.
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Turning text file into Binary Search Tree

    Sorry about that.

    Java Code:
    
    public class Node<E> {
    	
    	private E data;
    	 
    	private Node<E> left;
    	private Node<E> right; 
    	
    	
    	
    	/******************************************************************************
    	*  
    	*   Constructor for Nosw Class
    	*   
    	*   @param
    	*   	Inital data. The link to the next node and the link to the previous node. 
    	*   
    	*   
    	******************************************************************************/
    	//Constructor
    	public Node(E data, Node<E> left, Node<E> right)
    	{
    		this.data=data; 
    		this.left=left; 
    		this.right=right; 
    		
    	}
    	
    	/******************************************************************************
    	*  
    	*   Returns the data of the Node
    	*   
    	*   @return
    	*   	The data of the node
    	*   
    	******************************************************************************/
    	public E returnData()
    	{
    		return data; 
    	}
    	
    	
    	/******************************************************************************
    	*  
    	*   Returns the link to the next node
    	*   
    	*   @return
    	*   	The pointer to the next node
    	*   
    	*   
    	******************************************************************************/
    	public Node<E> returnLeft()
    	{
    		return left; 
    	}
    	
    	/******************************************************************************
    	*  
    	*   Returns the link to the previous node
    	*   
    	*   @return
    	*   	returns the previous pointer. 
    	*   
    	******************************************************************************/
    	public Node<E> returnRight()
    	{
    		return right; 
    	}
    	
    	
    	/******************************************************************************
    	*  
    	*   Sets the link to the next Node
    	*   
    	*   @param
    	*   	The node that is next in line
    	*   
    	*   
    	******************************************************************************/
    	public void setRight(Node<E> node)
    	{
    		right = node; 
    	}
    	
    	/******************************************************************************
    	*  
    	*   Sets the link to the previous Node
    	*   
    	*   @param
    	*   	The node that is previous. 
    	*   
    	******************************************************************************/
    	public void setLeft (Node<E> node)
    	{
    		left = node; 
    	}
    	
    	
    	public E getLeftMostData()
    	{
    		if(left == null)
    			return data; 
    		else
    			return left.getLeftMostData();
    	}
    	
    	
    	public E getRightMostData()
    	{
    		if(right == null)
    			return data;
    		else
    			return right.getRightMostData(); 
    	}
    	
    	public Node<E> getLeftMost()
    	{
    		if(left == null)
    			return left; 
    		else
    			return left.getLeftMost(); 
    	}
    	
    	
    	
    	public void setData(E data)
    	{
    		this.data = data; 
    	}
    	
    	
    	public boolean isLeaf()
    	{
    		return (left == null) && (right == null); 
    	}
    	
    	
    	public void inorderPrint()
    	{
    		if(left != null)
    			left.inorderPrint();
    		System.out.println(data); 
    		if( right != null)
    			right.inorderPrint(); 
    	}
    	
    	
    
    	
    	
    	
    }

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,812
    Rep Power
    25

    Default Re: Turning text file into Binary Search Tree

    With this line:

    String input = "(8(2()())(13()(4)))"; //FileReader.nextLine();

    I get this error: java.lang.NumberFormatException: For input string: ""
    in Separator()
    If you don't understand my response, don't ignore it, ask a question.

  5. #5
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Turning text file into Binary Search Tree

    I also forgot to give you the file, in its entirety.
    Java Code:
    5(8(2()())(13()(4)))
    I am not sure where you will need to put it to be read, but for me it's (Using Eclipse) in the Project Folder. It doesn't go inside the src or bin directory.
    The 5 at the front of the file is just another part of the project, but that is stripped out when you run the program and only the Tree part of the string is sent to
    be turned into a Tree.

    It's throwing that error because it can't find anything, or it can't find the 5 at the beginning. Name the above file simpletree.txt.

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,812
    Rep Power
    25

    Default Re: Turning text file into Binary Search Tree

    put it to be read
    I assign it to the String in the program. See post#4

    I don't see and printlns for debugging. How are you tracing what the code is doing and the state of the variables?
    Last edited by Norm; 05-07-2012 at 12:00 AM.
    If you don't understand my response, don't ignore it, ask a question.

  7. #7
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Turning text file into Binary Search Tree

    I removed most of my print statements to make it easier for you to read. Also, it's not working because it doesn't have the 5 in front. Just change the input string to 5(8(2()())(13()(4))).
    I am aware of why it's throwing the empty stack exception, but don't know how to turn this into a tree. Should I try recursive reasoning?

  8. #8
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,812
    Rep Power
    25

    Default Re: Turning text file into Binary Search Tree

    I'm having to add println statements to trace what the code does. I have no idea what the logic for the code is because there are no comments describing why it is doing anything.

    One technique for tracing linked lists is a toString method in the Node class. A sample of the trace print out:

    Running: java Tree

    SSI=1
    The String stripped of its operand (8(2()())(13()(4)))
    The operand to search for 5
    char=(, index=0
    Number to be inserted 8
    holder=[8]
    char=(, index=2
    Number to be inserted 2
    holder=[8, 2]
    char=(, index=4
    holder=[8, 2]
    head= created=[Node: data=2 left=null, right=null]
    char=(, index=6
    holder=[8]
    created=[Node: data=8 left=null, right=null]
    head left= [Node: data=2 left=[Node: data=8 left=null, right=null], right=null]
    char=), index=8
    holder=[]
    Exception in thread "main" java.util.EmptyStackException
    at java.util.Stack.peek(Unknown Source)
    at java.util.Stack.pop(Unknown Source)
    at Tree.insert(Tree.java:133)
    at Tree.main(Tree.java:41)

    0 error(s)
    If you don't understand my response, don't ignore it, ask a question.

  9. #9
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Turning text file into Binary Search Tree

    I can explain my logic for the code. I have two indexes, the main Index which starts at 0, and a second Index which i always Index + 1. I go through the String character by character and do something to them depending on what they are.

    Java Code:
            //Index is the first Index. secondIndex is always Index + 1. 
    	if(input.charAt(Index) == '(')
    			{
    				if(input.charAt(secondIndex) == '0' || input.charAt(secondIndex) == '1' || input.charAt(secondIndex) == '2' || input.charAt(secondIndex) == '3' || input.charAt(secondIndex) == '4' || input.charAt(secondIndex) == '5' || input.charAt(secondIndex) == '6'
    						|| input.charAt(secondIndex) == '7' || input.charAt(secondIndex) == '8' || input.charAt(secondIndex) == '9')
    				{
    					
    					Character charNumTBI = input.charAt(secondIndex); 
    					String numTobeInserted = charNumTBI.toString(); 
    					secondIndex ++;  
    					Index++; 
    					while(input.charAt(secondIndex) != '(' && input.charAt(secondIndex) != ')' )
    					{
    						numTobeInserted += input.toString().charAt(secondIndex); 
    						secondIndex++; 
    						Index++; 
    					}
    					
    					
    					
    					 
    					System.out.println("Number to be inserted " + numTobeInserted); 
    					holder.push(Integer.parseInt(numTobeInserted)); 
    					 
    					
    				}
    				
    				else if(input.charAt(secondIndex) == ')')
    				{
    					
    					Index++; 
    					secondIndex++; 
    				}
    				
    				 
    			}
    This piece of code checks to see if Index is equal to (, it if is, it checks to see if the character following it is a number or a ). If it's a number, it puts that number into the stack. If it's a ), it increases the Indexes by 1.

    Java Code:
    if(input.charAt(Index) != '(' && input.charAt(Index) != ')' )
    			{
    				Index++; 
    				secondIndex++; 
    			}
    If the Index is not equal to ( or a ), it is a number. For this case, all it does is increase both Indices by 1.

    Java Code:
    			if(input.charAt(Index) == ')')
    			{
    				 
    				
    				if(root == null)
    				{
    					root = new Node<Integer>(holder.pop(),null,null);
    					
    				}
    				
    				else if(root.returnLeft() == null)
    				{
    					
    					
    					Node<Integer> alpha = new Node<Integer>(holder.pop(),null,null);
    					root.setLeft(alpha); 
    				}
    				
    				else if (root.returnRight() == null)
    				{
    					
    					Node<Integer> alpha = new Node<Integer>(holder.pop(),null,null); 
    					root.setRight(alpha);
    
    				}
    				 
    				Index++;
    				secondIndex++; 
    				 
    			}
    The last if statement of the loop, this one happens if the Index value is ). This is the part that attempts to make the tree. Sorry for not commenting on it more, I usually add those after I am done. I have an in order traversal that I plan on using to see how the tree turns out.
    Last edited by Wnt2bsleepin; 05-07-2012 at 12:30 AM.

  10. #10
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,812
    Rep Power
    25

    Default Re: Turning text file into Binary Search Tree

    Its going to be hard to read the code and keep coming back here to read the logic.

    Add some more printlns to the code so you can see what it is doing. If you know what it is supposed to do, then the print out will show you what it is doing and you should be able to fix it.
    If you don't understand my response, don't ignore it, ask a question.

  11. #11
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Turning text file into Binary Search Tree

    I will do that. I think I will also stalk my professor around campus, see if I can sit in with him and have him go over this with me. I will post more questions here is I run into any trouble. Thanks!

  12. #12
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Turning text file into Binary Search Tree

    I asked my professor about it, and he gave me a hint.

    If the first character is a # or a ), and the second character is a ): Pop off the stack

    If the first character is a ( and the second Character is a number: if the top of the stack's left pointer is null, make a new node and point the top of the stack's left pointer to that new Node. Then push the new Node onto the stack. Same thing if the right pointer is null

    If the first character is ( and the second character is a ): Look at the stack, if the left and right pointers are not null, make them null
    I have worked on it, and it works for some trees but others don't seem to generate properly.

    Java Code:
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.Scanner;
    import java.util.Stack;
    /**
     * 
     * 	What Works: I can strip the number from the beginning of the String, and put it into a variable.
     * 
     * 	What doesn't work: I cannot make the actual tree itself.
     * 
     * 
     * 
     *
     */
    
    public class Tree {
    	
    	
    	static int Operand,SubStringIndex,SIndex = 0,numItems; //Used with the Separator method. 
    	static int Index = 0,secondIndex = Index+1;  //Used with the stack
    	static BTNode<Integer> root; //Used to keep reference to the root of the tree. 
    	static Stack<BTNode<Integer>> superStack = new Stack<BTNode<Integer>>();  
    	
    	
    	 
    	 
    	
    
    	
    	public static void main(String[] args) throws FileNotFoundException
    	{
    		Scanner FileReader = new Scanner(new File("simpletree.txt"));
    		String input = FileReader.nextLine();
    		
    		String treeText = Separator(input); 
    		
    		System.out.println("The String stripped of its operand " + treeText);
    		System.out.println("The Operand to search for " + Operand);
    		Insert(treeText); 
    		 
    		//PathTester(root); 
    		
    		System.out.print("Pre Order:\n"); root.preorderPrint(); 
    		System.out.print("In Order:\n"); root.inorderPrint(); 
    		System.out.print("Post Order:\n"); root.postorderPrint(); 
    		root.print((int)BTNode.treeSize(root)); 
    		//System.out.println(root.getData()); 
    		
    		 
    
    		
    		 
    	}
    	
    	//Strips out the number to test, and returns the string to be inserted into the tree. 
    	public static String Separator(String input)
    	{
    		while(input.charAt(SIndex) != '(')
    		{
    			SubStringIndex++;
    			SIndex++; 
    		}
    		//System.out.println(SubStringIndex); 
    		Operand = Integer.parseInt(input.substring(0,SubStringIndex)); 
    		return input.substring(SubStringIndex); 
    	}
    	
    	
    	
    	
    	public static void Insert(String input)
    	{
    		while(secondIndex < input.length())
    		{
    			
    			//Covers (# and () 
    			if(input.charAt(Index) == '(') //First character is a (
    			{
    				if(input.charAt(secondIndex) == '0' || input.charAt(secondIndex) == '1' || input.charAt(secondIndex) == '2' || input.charAt(secondIndex) == '3' || input.charAt(secondIndex) == '4' || input.charAt(secondIndex) == '5' || input.charAt(secondIndex) == '6'
    					|| input.charAt(secondIndex) == '7' || input.charAt(secondIndex) == '8' || input.charAt(secondIndex) == '9')
    				{
    				
    					Character charNumTBI = input.charAt(secondIndex); 
    					String numTobeInserted = charNumTBI.toString(); 
    					secondIndex ++;  
    					Index++; 
    					while(input.charAt(secondIndex) != '(' && input.charAt(secondIndex) != ')' )//If the second Index is a number, add that number to the insertion string. 
    					{
    						numTobeInserted += input.toString().charAt(secondIndex); 
    						secondIndex++; 
    						Index++; 
    					}
    				
    				
    				
    				 
    					System.out.println("Number to be inserted " + numTobeInserted); 
    					int numberForm = Integer.parseInt(numTobeInserted); 
    					if(superStack.isEmpty())
    					{
    						BTNode<Integer> alpha = new BTNode<Integer>(numberForm,null,null); 
    						superStack.push(alpha); //If the stack is empty, make a new Node, and push it to the top of the stack.
    						root = alpha; 
    					}
    				
    					else if(superStack.peek().getLeft() == null)
    					{
    						BTNode<Integer> set = new BTNode<Integer>(numberForm,null,null); //Make a new node with the data and left and right null. 
    						superStack.peek().setLeft(set); //Set the left pointer of the top node in the stack to the newly created Node.
    						superStack.push(set); //Push the newly created Node to the to of the stack. 
    					}
    				
    					else if (superStack.peek().getRight() == null)
    					{
    						BTNode<Integer> set = new BTNode<Integer>(numberForm,null,null); 
    						superStack.peek().setRight(set); 
    						superStack.push(set); 
    					}
    					
    					else System.err.println("There was en error"); 
    				
    				}
    			
    				else if(input.charAt(secondIndex) == ')') //Left Parenthesis followed by a right parenthesis 
    				{
    					if(superStack.peek().getLeft() != null)
    					{
    						superStack.peek().setLeft(null); 
    					}
    				
    					else if(superStack.peek().getRight() != null)
    					{
    						superStack.peek().setRight(null); 
    					}
    					Index++; 
    					secondIndex++; 
    				}
    				Index++; 
    				secondIndex++;
    				
    			}
    		
    			else if(input.charAt(Index) != '(' && input.charAt(Index) != ')' || input.charAt(Index) == ')') //If the first character is a number or a ) 
    			{
    			
    				if(input.charAt(secondIndex) == ')') //followed by a ) 
    				{
    					superStack.pop(); 
    				}
    			
    			
    				Index++; 
    				secondIndex++; 
    			}
    		
    		
    			
    			
    			
    		
    		
    		
    		
    		} // end of while loop. 
    		
    
    		
    	}
    	
    	
    	public static void PathTester(BTNode<Integer> root)
    	{
    		if(root.isPath(Operand)) System.out.println("It's true");
    		
    		else System.out.println("It's false"); 
    		
    		
    	}
    	
    	
    	
    	
    	
    	
    
    }

    BTNode:

    Java Code:
    // File: BTNode.java from the package edu.colorado.nodes
    // Complete documentation is available from the BTNode link in:
    //   http://www.cs.colorado.edu/~main/docs/
    
    
    
    /******************************************************************************
    * A <CODE>BTNode&lt;<E&gt;</CODE> provides a node for a binary tree. Each node 
    * contains a piece of data (which is a reference to an E object) and references
    * to a left and right child. The references to children may be null to indicate
    * that there is no child. The reference stored in a node can also be null.
    *
    * <dl><dt><b>Limitations:</b> <dd>
    *   Beyond <CODE>Int.MAX_VALUE</CODE> elements, <CODE>treeSize</CODE>, is
    *   wrong.
    *
    * <dt><b>Java Source Code for this class:</b><dd>
    *   <A HREF="../../../../edu/colorado/nodes/BTNode.java">
    *   http://www.cs.colorado.edu/~main/edu/colorado/nodes/BTNode.java </A>
    *
    * @author Michael Main 
    *   <A HREF="mailto:main@colorado.edu"> (main@colorado.edu) </A>
    *
    * @version
    *   Jul 22, 2005
    ******************************************************************************/
    public class BTNode<E>
    {
       // Invariant of the BTNode<E> class:
       //   1. Each node has one reference to an E Object, stored in the instance
       //      variable data.
       //   2. The instance variables left and right are references to the node's
       //      left and right children.
       private E data;
       private BTNode<E> left, right;  
       private int sum = 0; 
    
       /**
       * Initialize a <CODE>BTNode</CODE> with a specified initial data and links
       * children. Note that a child link may be the null reference, 
       * which indicates that the new node does not have that child.
       * @param <CODE>initialData</CODE>
       *   the initial data of this new node
       * @param <CODE>initialLeft</CODE>
       *   a reference to the left child of this new node--this reference may be null
       *   to indicate that there is no node after this new node.
       * @param <CODE>initialRight</CODE>
       *   a reference to the right child of this new node--this reference may be null
       *   to indicate that there is no node after this new node.
       * <dt><b>Postcondition:</b><dd>
       *   This node contains the specified data and links to its children.
       **/   
       public BTNode(E initialData, BTNode<E> initialLeft, BTNode<E> initialRight)
       {
          data = initialData;
          left = initialLeft;
          right = initialRight;
       }       
       
       
       /**
       * Accessor method to get the data from this node.   
       * @param - none
       * @return
       *   the data from this node
       **/
       public E getData( )   
       {
          return data;
       }
       
       
       /**
       * Accessor method to get a reference to the left child of this node. 
       * @param - none
       * @return
       *   a reference to the left child of this node (or the null reference if there
       *   is no left child)
       **/
       public BTNode<E> getLeft( )
       {
          return left;                                               
       } 
       
       
       /**
       * Accessor method to get the data from the leftmost node of the tree below 
       * this node.
       * @param - none
       * @return
       *   the data from the deepest node that can be reached from this node by
       *   following left links.
       **/
       public E getLeftmostData( )
       {
          if (left == null)
             return data;
          else
             return left.getLeftmostData( );
       }
          
       
       /**
       * Accessor method to get a reference to the right child of this node. 
       * @param - none
       * @return
       *   a reference to the right child of this node (or the null reference if there
       *   is no right child)
       **/
       public BTNode<E> getRight( )
       {
          return right;                                               
       } 
    
    
       /**
       * Accessor method to get the data from the rightmost node of the tree below 
       * this node.
       * @param - none
       * @return
       *   the data from the deepest node that can be reached from this node by
       *   following right links.
       **/
       public E getRightmostData( )
       {
          if (left == null)
             return data;
          else
             return left.getRightmostData( );
       }
       
       
       /**
       * Uses an inorder traversal to print the data from each node at or below
       * this node of the binary tree.
       * @param - none
       * <dt><b>Postcondition:</b><dd>
       *   The data of this node and all its descendants have been writeen by
       *   <CODE>System.out.println( )</CODE> using an inorder traversal.
       **/
       public void inorderPrint( )
       {
          if (left != null)
             left.inorderPrint( );
          System.out.println(data);
          if (right != null)
             right.inorderPrint( );
       }  
    
       
       /**
       * Accessor method to determine whether a node is a leaf. 
       * @param - none
       * @return
       *   <CODE>true</CODE> (if this node is a leaf) or 
       *   <CODE>false</CODE> (if this node is not a leaf.
       **/
       public boolean isLeaf( )
       {
          return (left == null) && (right == null);                                               
       } 
    
    
       /**
       * Uses a preorder traversal to print the data from each node at or below
       * this node of the binary tree.
       * @param - none
       * <dt><b>Postcondition:</b><dd>
       *   The data of this node and all its descendants have been writeen by
       *   <CODE>System.out.println( )</CODE> using a preorder traversal.
       **/
       public void preorderPrint( )
       {
          System.out.println(data);
          if (left != null)
             left.preorderPrint( );
          if (right != null)
             right.preorderPrint( );
       } 
       
          
       /**
       * Uses a postorder traversal to print the data from each node at or below
       * this node of the binary tree.
       * @param - none
       * <dt><b>Postcondition:</b><dd>
       *   The data of this node and all its descendants have been writeen by
       *   <CODE>System.out.println( )</CODE> using a postorder traversal.
       **/
       public void postorderPrint( )
       {
          if (left != null)
             left.postorderPrint( );
          if (right != null)
             right.postorderPrint( );
          System.out.println(data);
       }
       
       
       
       public Boolean isPath(int target)
       {
    	   if(left != null){
    		   sum += (Integer)left.data; 
    		   if(target == sum) return true; 
    		   left.isPath(target);
    	   } 
    	   if(right != null){
    		   sum += (Integer) right.data; 
    		   if(target == sum) return true; 
    		   right.isPath(target); 
    	   } 
    	   return false; 
       }
    
    
       /**
       * Uses an inorder traversal to print the data from each node at or below
       * this node of the binary tree, with indentations to indicate the depth
       * of each node.
       * @param <CODE>depth</CODE>
       *   the depth of this node (with 0 for root, 1 for the root's
       *   children, and so on)(
       * <dt><b>Precondition:</b><dd>
       *   <CODE>depth</CODE> is the depth of this node.
       * <dt><b>Postcondition:</b><dd>
       *   The data of this node and all its descendants have been writeen by
       *   <CODE>System.out.println( )</CODE> using an inorder traversal.
       *   The indentation of each line of data is four times its depth in the
       *   tree. A dash "--" is printed at any place where a child has no
       *   sibling.
       **/
       public void print(int depth)
       {
          int i;
       
          // Print the indentation and the data from the current node:
          for (i = 1; i <= depth; i++)
             System.out.print("    ");
          System.out.println(data);
    
          // Print the left subtree (or a dash if there is a right child and no left child)   
          if (left != null)
             left.print(depth+1);
          else if (right != null)
          {
             for (i = 1; i <= depth+1; i++)
                System.out.print("    ");
             System.out.println("--");
          }
    
          // Print the right subtree (or a dash if there is a left child and no left child)  
          if (right != null)
             right.print(depth+1);
          else if (left != null)
          {
             for (i = 1; i <= depth+1; i++)
                System.out.print("    ");
             System.out.println("--");
          }
       }
       
    
       /**
       * Remove the leftmost most node of the tree with this node as its root.
       * @param - none
       * <dt><b>Postcondition:</b><dd>
       *   The tree starting at this node has had its leftmost node removed (i.e.,
       *   the deepest node that can be reached by following left links). The
       *   return value is a reference to the root of the new (smaller) tree.
       *   This return value could be null if the original tree had only one
       *   node (since that one node has now been removed).
       **/
       public BTNode<E> removeLeftmost( )
       {
          if (left == null)
             return right;
          else
          {
             left = left.removeLeftmost( );
             return this;
          }
       }
    
    
       /**
       * Remove the rightmost most node of the tree with this node as its root.
       * @param - none
       * <dt><b>Postcondition:</b><dd>
       *   The tree starting at this node has had its rightmost node removed (i.e.,
       *   the deepest node that can be reached by following right links). The
       *   return value is a reference to the root of the new (smaller) tree.
       *   This return value could be null if the original tree had only one
       *   node (since that one node has now been removed).
       **/
       public BTNode<E> removeRightmost( )
       {
          if (right == null)
             return left;
          else
          {
             right = right.removeRightmost( );
             return this;
          }
       }
           
       /**
       * Modification method to set the data in this node.   
       * @param <CODE>newData</CODE>
       *   the new data to place in this node
       * <dt><b>Postcondition:</b><dd>
       *   The data of this node has been set to <CODE>newData</CODE>.
       **/
       public void setData(E newData)   
       {
          data = newData;
       }                                                               
       
       
       /**
       * Modification method to set the link to the left child of this node.
       * @param <CODE>newLeft</CODE>
       *   a reference to the node that should appear as the left child of this node
       *  (or the null reference if there is no left child for this node)
       * <dt><b>Postcondition:</b><dd>
       *   The link to the left child of this node has been set to <CODE>newLeft</CODE>.
       *   Any other node (that used to be the left child) is no longer connected to
       *   this node.
       **/
       public void setLeft(BTNode<E> newLeft)
       {                    
          left = newLeft;
       }
        
        
       /**
       * Modification method to set the link to the right child of this node.
       * @param <CODE>newLeft</CODE>
       *   a reference to the node that should appear as the right child of this node
       *  (or the null reference if there is no right child for this node)
       * <dt><b>Postcondition:</b><dd>
       *   The link to the right child of this node has been set to <CODE>newRight</CODE>.
       *   Any other node (that used to be the right child) is no longer connected to
       *   this node.
       **/
       public void setRight(BTNode<E> newRight)
       {                    
          right = newRight;
       }  
        
        
       /**
       * Copy a binary tree.
       * @param <CODE>source</CODE>
       *   a reference to the root of a binary tree that will be copied (which may be
       *   an empty tree where <CODE>source</CODE> is null)
       * @return
       *   The method has made a copy of the binary tree starting at 
       *   <CODE>source</CODE>. The return value is a reference to the root of the copy. 
       * @exception OutOfMemoryError
       *   Indicates that there is insufficient memory for the new tree.   
       **/ 
       public static <E> BTNode<E> treeCopy(BTNode<E> source)
       {
          BTNode<E> leftCopy, rightCopy;
    
          if (source == null)
             return null;
          else
          {
             leftCopy = treeCopy(source.left);
             rightCopy = treeCopy(source.right);
             return new BTNode<E>(source.data, leftCopy, rightCopy);
          }
       }
       
    
       /**
       * Count the number of nodes in a binary tree.
       * @param <CODE>root</CODE>
       *   a reference to the root of a binary tree (which may be
       *   an empty tree where <CODE>source</CODE> is null)
       * @return
       *   the number of nodes in the binary tree  
       * <dt><b>Note:</b><dd>
       *   A wrong answer occurs for trees larger than 
       *   <CODE>INT.MAX_VALUE</CODE>.    
       **/ 
       public static <E> long treeSize(BTNode<E> root)
       {
          if (root == null)
             return 0;
          else
             return 1 + treeSize(root.left) + treeSize(root.right);
       }   
    
    }
    An example of input that seems to work
    Java Code:
    20(10(8(6)(4))(3()(5(2)(1))))
    and the output:
    Java Code:
    The String stripped of its operand (10(8(6)(4))(3()(5(2)(1)))) 
    The Operand to search for 20
    Number to be inserted 10
    Number to be inserted 8
    Number to be inserted 6
    Number to be inserted 4
    Number to be inserted 3
    Number to be inserted 5
    Number to be inserted 2
    Number to be inserted 1
    Pre Order:
    10
    8
    6
    4
    3
    5
    2
    1
    In Order:
    4
    6
    1
    2
    5
    3
    8
    10
    Post Order:
    4
    1
    2
    5
    3
    6
    8
    10
                                    10
                                        8
                                            6
                                                4
                                                3
                                                    5
                                                        2
                                                            1
                                                            --
                                                        --
                                                    --
                                            --
                                        --

  13. #13
    brynpttrsn is offline Member
    Join Date
    Sep 2011
    Posts
    59
    Rep Power
    0

    Default Re: Turning text file into Binary Search Tree

    Cant this be made much simpler by looking at the list of rules to parse the string into a tree and going from there?

    Couldn't you just populate a queue with the string and handle the different cases from there?
    Java Code:
    	    while(queue has elements)
    	    {
    	        if(first element in queue isnt "(" or ")" )
    	        {
    	            pop it off and set this as data
    	        }
    	        else if(first element is "(" )
    	        {
    	            pop it off and make a child node.(handle "()" here)
    	        }
    	        else (only thing left is ")" )
    	        {
    	            return back to previous node;
    	        }
    	    }
    	}
    I dont know if you're good with recursion, but it would solve this fairly quickly.

  14. #14
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Turning text file into Binary Search Tree

    Recursion isn't my strongest area, but I can figure it out.

Similar Threads

  1. Replies: 2
    Last Post: 04-20-2011, 06:39 PM
  2. Replies: 0
    Last Post: 04-04-2010, 08:40 AM
  3. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 02:42 AM
  4. Binary Search Tree
    By anmadie in forum New To Java
    Replies: 5
    Last Post: 11-17-2009, 03:39 AM
  5. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 03:03 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •