Skip to main content

Increase frequency of string in Binary Tree

Please note these java.net forums are being decommissioned and use the new and improved forums at https://community.oracle.com/community/java.
No replies
libby
Offline
Joined: 2006-05-05

I have a binary tree, where a user is prompted to input a string. If the string already exists, the frequency of this string will increase by one, instead of adding a new node. If it doesnt the string will be placed in a new node. This is to be done using recursion.

The problem I am having is that frequency is continually adding. for example: I enter a, then b, then c, they are all inserted in as new strings, when I type in "a" again, the freq. increases by one, but when I type in "b" its increased from 1 to 3, and so on.....

Main class

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();
           
            compare = Tree.search(myTree.getRoot(), item);
          
            if(compare != null){
              
            System.out.println(item + " already exists. \nString frequency: " + compare.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();
           compare = Tree.search(myTree.root, searchItem);
           if(compare != null){                       
                System.out.println("FOUND - " + compare.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

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.left;
              }else{
                  search(root.right, item);
                  if(root.right != null && item.equals(root.right.item)){                     
                      return root.right;
                  }
              }
          }return null;
      }
    
      public TreeNode found(TreeNode root, String item){
          return search(root, item);         
      }
        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

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;
        }
}