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