I have a binary tree, that user types in a string, if the string does not exist, it adds it to the tree, but if it does, it increases the frequency by 1 instead of adding it to the tree.
I have my search working(I think I do anyways), The problem is if I type in a, b , c, then I type in a, b, c again, a increases frequency by 1, b then increases by 2, and c increases by 3.
So it seems for every string I type in the frequency is going up by the last amount. How can I fix this? I am at a loss.

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){
                //compareNode.upFreq();
           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 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;
        }
}

i only looked at it for a moment , but :

            Scanner keyboard = new Scanner(System.in);
            .
            .
            input = keyboard.nextInt();
            Scanner scanner = new Scanner(System.in);            

            if(input == 1){
            System.out.println("Enter a new string: ");            
            item = scanner.nextLine(); 

i quite dont get use of having two different scanners, also having a nextLine() after nextInt() might lead to problems (i can only assume this as i cant run your code ). the problem that comes up with such a nextInt() - nextLine() code is that nextline picks up the stray newline character left by nextInt() . however , it can be that the use of different scanners is to work around this problem.... maybe you could provide a version of your code that can be run and tested , will be easier to spot the errors...

also , you haven't mentioned what you want to do with the code..

I have a binary tree, that user types in a string, if the string does not exist, it adds it to the tree, but if it does, it increases the frequency by 1 instead of adding it to the tree.

sounds like a counter implementation.. in that case, if your allowed to use external java library , take a look at TreeMap . its a red black BST implementation that does its stuff (insert , search , delete ) all in logN time. pretty fast.

Edited 3 Years Ago by somjit{}

The Scanner keyboard, takes in the option of integers 1-4.
1 being enter a string
2: search for string
3: display tree
4: exit

If option 1 or 2 is chosen, the user enters a string into Scanner scanner.
If its option 1, the string is searched to see if exists in the tree, if it does, rather than create a new node, the frequency of the string is increased by 1. if not, a new node is created containing that string.

if option 2 is chosen, the string is simply searched in the tree, if it exists, a print statement saying found, and the frequency number of that string, if not, it displays not found.

We have to use a balanced binary tree for this project. and use recursion

Edited 3 Years Ago by tricket_7

This article has been dead for over six months. Start a new discussion instead.