Howdy, Stranger!

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

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.