Binary Tree - increase frequency of string - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Binary Tree - increase frequency of string

tricket_7tricket_7 Posts: 3Member
I have a binary tree where the user is prompted to enter a string, if the string already exists, the frequency of the string is to be added plus 1 instead of creating a new node, but if the string is unique, a new node should be added with that string.

I have all of my methods, the problem is when I run the program when I enter the following I get the following errors:

Enter a ---> a exists, freq of 2
Enter b ---> insert b
Enter c ---> insert c

Enter a again ---> a exists, freq of 4
Enter b again ---> b exists, freq of 5
Enter c again --->c exists, freq of 6

as you can see my counter is not working properly, they should all output a freq of 2.

I have looked all over, I really need help fixing this. I will post my whole 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("
Select your option!");
System.out.println(" 1 - Enter a new String");
System.out.println(" 2 - Search for a String");
System.out.println(" 3 - Display Tree");
System.out.println(" 4 - 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.
String 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("
Enter another option");
}
}
}

[/code]

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

[/code]

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

[/code]

Comments

Sign In or Register to comment.