#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    2
    Rep Power
    0

    Binary Tree increase frequency of entered string


    I have a binary tree that prompts a user to enter a string, if the string already exists, the frequency of that string will be added +1, instead of creating a new node on the tree, if the string is unique, it will add a new node with that string.

    I have created my methods, but the problem is when I run the program:
    When I enter:
    a it says freq of 2,
    b it says insert b
    c it says insert c,
    when I add them again it says
    a freq of 4
    b freq of 5
    c freq of 6
    when they should all say 2
    I have searched all over and just dont know how to fix this>

    I will post all of my code below

    Main class
    Code:
    import java.util.*;
    
    
    public class TreeDriver {
     
        private static TreeNode compare;
        
        public static void main(String[] args) {
            
            Tree myTree = new Tree();        
            
            Scanner keyboard = new Scanner(System.in);
            int input;
            String item;
            
            
            
            
            while(true){
                System.out.println("\nSelect your option!");
                System.out.println("\t1 - Enter a new String");
                System.out.println("\t2 - Search for a String");
                System.out.println("\t3 - Display Tree");
                System.out.println("\t4 - Exit");
                
                input = keyboard.nextInt();
                Scanner scanner = new Scanner(System.in);            
                
                if(input == 1){
                System.out.println("Enter a new string: ");            
                item = scanner.nextLine();
                myTree.insert(item);
                TreeNode found = myTree.find(item);
               
                if(found != null){
                found.upFreq();   
                System.out.println(item + " already exists. \nString frequency: " + found.getFreq());
               }else{
               myTree.insert(item);            
               System.out.println("Inserted " +  "'" + item + "'" + " into tree");
                }
                }else if(input == 2){
                System.out.println("Enter a string to search: "); 
               String searchItem = scanner.nextLine();
                 TreeNode found = myTree.find(searchItem);
               if(found != null){                        
                    System.out.println("FOUND - " + found.getFreq() );
               }else{      
                    System.out.println("NOT FOUND.");
               }
               
                }else if(input == 3){
                System.out.println("Display Tree: ");
                myTree.preOrderPrint();
                
                }else if(input == 4){
                    System.exit(0);//exit program
                }
                System.out.println("\nEnter another option");
                }           
           }
        }
    Tree Class
    Code:
    public class Tree {
     
         TreeNode root;
        
        
    	public Tree(){
    		
    		root = null;
                    
    	}        
            
    	public boolean isEmpty(){
    		
    		return root == null;
    		
    	}
    	
    	public void insert(String item){
    		
    		if(isEmpty()){		
    			root = new TreeNode(item);                    
                    }else{		
                        root.add(item);
                   }
            }
            
          static TreeNode search(TreeNode root, String item){
              if(root == null){
                  return null;              
              }else if (root != null && item.equals(root.item)){ 
                 // root.upFreq();
                  return root;
              }else{
                  search(root.left, item);
                  if(root.left != null && item.equals(root.left.item)){                   
                      return root;
                  }else{
                      search(root.right, item);
                      if(root.right != null && item.equals(root.right.item)){                      
                          return root;
                      }
                  }
              }return null;
          }
          
          public TreeNode find(String item){
              TreeNode current = root;
              while(!current.item.equals(item)){
                  if(item.equals(current.item)){
                      current = current.left;
                  }else{
                      current = current.right;
                  if(current == null){
                      return null;
                  }
                  }
              }
              return current;
          }
          
            public TreeNode getRoot(){
                return root;
            }
             public void preOrderPrint() {
            preOrderPrint(root);
        }        
              
           public static void preOrderPrint(TreeNode root) {
             if (root != null) {            
      
           System.out.println(root.getItem());   // root
           preOrderPrint(root.getLeft());        // left
           preOrderPrint(root.getRight());       // right
    }
           }
    }
    TreeNode Class

    Code:
    public class TreeNode{
    
            
            String item; // data in node        
            TreeNode left;    // Pointer to left subtree.
            TreeNode right;   // Pointer to right subtree.
            private static int freq = 1;
            
            
           public TreeNode(String str){
    		item = str;
    		left = null;
    		right = null;
           }
            
    	public void add(String item) {
                    
    		if (left == null) {		
    			left = new TreeNode(item);		
    		} 
                    else if( right == null){		
    			right = new TreeNode(item);			
    		} else {		
    			if(countNodes(left) <= countNodes(right)){				
    				left.add(item);				
    			} else {		
    				right.add(item);
    				
    			}	
    		}
    	}
          
    	//Count the nodes in the binary tree to which root points, and
    	public static int countNodes( TreeNode root ) {
    		if ( root == null ){
    		
    			// The tree is empty.  It contains no nodes.
    			return 0;  
    			
                    }else{
    			// Start by counting the root.
    			int count = 1; 
    			// Add the number of nodes in the left subtree.
    			count += countNodes(root.left);
    			
    			// Add the number of nodes in the right subtree.
    			count += countNodes(root.right); 
                               
    			return count;  // Return the total.
    		}
    	}
            
            public TreeNode getLeft(){
    		return left;
    	}
    	
    	public TreeNode getRight(){
    		return right;
    	}
    	
    	public String getItem(){
    		return item;
    	} 
             public static void upFreq(){
               freq++;
            }
            
            public int getFreq(){
                return freq;
            }
    }
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2005
    Posts
    74
    Rep Power
    33
    At a very quick glance, I noticed you're looking for the next line ... Maybe it's picking up the character + the enter key & therefore it doesn't find 'a' again.

    Maybe??
    Code:
    char character = in.nextLine().charAt(0)
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    2
    Rep Power
    0
    I will try that again to see, I originally had word = scanner.next() technically words would be entered instead of letters. I was just testing it with letters. Would I still use charAt(0) in that case?
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2005
    Posts
    74
    Rep Power
    33
    The .charAt() method simply gets the very first character in any given string.

    Some examples....
    Code:
    String string = "This is a string of text";
    char c = string.charAt(0); // 'T';
    
    String string = "another string gjsapiogdasoidgsa";
    char c = string.charAt(0); // 'a'
    
    String string = "!£$£%^%$&^$^$£%£gfsaivj4t4ffw";
    char c = string .charAt(0); // '!'

IMN logo majestic logo threadwatch logo seochat tools logo