7 Replies - 1213 Views - Last Post: 16 April 2013 - 04:44 PM Rate Topic: -----

#1 ccb77  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 24-March 13

count frequency of strings in java binary tree

Posted 16 April 2013 - 12:14 PM

How do I implement a frequency counter in a treenode that increases when the user enters an existing word?

I have a program where the user is asked to choose: enter string, search for string

My frequency counter is not working properly. How do I keep track of the frequencies for the left and right nodes? My frequency counter only gives for root:

public void insert(String item){

		if(isEmpty()){		
			root = new TreeNode(item); 
                        System.out.println("inserted " + "'" + item + "'" + " into tree. Frequency: " + root.getFreq());
                }
               // If string item already exists, do not insert another node, increase the frequency of the node containing the string
                        else if(searchTree(root,item) == true){
                            root.upFreq();
                            
                            System.out.println( "'" + item + "'" + " already exists! Frequency: " + root.getFreq());
                 //if the string does not already exists, enters string item into new node       
                        } else{                           
                    root.add(item); 
                    System.out.println("inserted " + "'" + item + "'" + " into tree! Frequency: " + root.getFreq());
                    
        }  
                
        }





 static boolean searchTree(TreeNode root, String item){
            if(root == null){
                return false;
            }
            if(root.item.equals(item)){ 
               //root.upFreq();
                
                return true;            
            }
            return searchTree(root.left, item) || searchTree(root.right, item);
            }



Is This A Good Question/Topic? 0
  • +

Replies To: count frequency of strings in java binary tree

#2 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5796
  • View blog
  • Posts: 12,631
  • Joined: 16-October 07

Re: count frequency of strings in java binary tree

Posted 16 April 2013 - 12:32 PM

Dude! How in the hell can your searchTree be static?!? Tell me TreeNode isn't public...

Your searchTree is, um, disturbing. You should be going left or right, not returning left || right. You call it and seem to expect that root has meaning. It doesn't.

Implement a find item. Go from there:
private TreeNode findNode(TreeNode parent, String item) { /* your code here */ }

private TreeNode insert(TreeNode parent, String item) { /* your code here */ }

private boolean searchTree(String item) { return findNode(this.root, item)!=null; }

public void insert(String item){
	if(isEmpty()){
		this.root = new TreeNode(item); 
		System.out.println("inserted " + "'" + item + "'" + " into tree. Frequency: " + root.getFreq());
	} else {
		TreeNode node = findNode(this.root, item);
		if(node!=null) {
			node.upFreq();
			System.out.print( "'" + item + "'" + " already exists!");
		} else {
			node = insert(this.root, item);
			System.out.print("inserted " + "'" + item + "'" + " into tree!");
		}  
		System.out.println(" Frequency: " + node.getFreq());
	}
}



Hope this helps.
Was This Post Helpful? 1
  • +
  • -

#3 ccb77  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 24-March 13

Re: count frequency of strings in java binary tree

Posted 16 April 2013 - 12:50 PM

Thanks, no the treenode was not public, and the static was a typo.....
Was This Post Helpful? 0
  • +
  • -

#4 ccb77  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 24-March 13

Re: count frequency of strings in java binary tree

Posted 16 April 2013 - 01:00 PM

We were told to work from this:

http://math.hws.edu/...otes/c9/s4.html
Was This Post Helpful? 0
  • +
  • -

#5 ccb77  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 24-March 13

Re: count frequency of strings in java binary tree

Posted 16 April 2013 - 02:45 PM

View Postbaavgai, on 16 April 2013 - 12:32 PM, said:

Dude! How in the hell can your searchTree be static?!? Tell me TreeNode isn't public...

Your searchTree is, um, disturbing. You should be going left or right, not returning left || right. You call it and seem to expect that root has meaning. It doesn't.

Implement a find item. Go from there:
private TreeNode findNode(TreeNode parent, String item) { /* your code here */ }

private TreeNode insert(TreeNode parent, String item) { /* your code here */ }

private boolean searchTree(String item) { return findNode(this.root, item)!=null; }

public void insert(String item){
	if(isEmpty()){
		this.root = new TreeNode(item); 
		System.out.println("inserted " + "'" + item + "'" + " into tree. Frequency: " + root.getFreq());
	} else {
		TreeNode node = findNode(this.root, item);
		if(node!=null) {
			node.upFreq();
			System.out.print( "'" + item + "'" + " already exists!");
		} else {
			node = insert(this.root, item);
			System.out.print("inserted " + "'" + item + "'" + " into tree!");
		}  
		System.out.println(" Frequency: " + node.getFreq());
	}
}



Hope this helps.


I am not quite sure what to do with the second insert method.... since one already exists
private TreeNode insert(TreeNode parent, String item){ 
}



View Postbaavgai, on 16 April 2013 - 12:32 PM, said:

Dude! How in the hell can your searchTree be static?!? Tell me TreeNode isn't public...

Your searchTree is, um, disturbing. You should be going left or right, not returning left || right. You call it and seem to expect that root has meaning. It doesn't.

Implement a find item. Go from there:
private TreeNode findNode(TreeNode parent, String item) { /* your code here */ }

private TreeNode insert(TreeNode parent, String item) { /* your code here */ }

private boolean searchTree(String item) { return findNode(this.root, item)!=null; }

public void insert(String item){
	if(isEmpty()){
		this.root = new TreeNode(item); 
		System.out.println("inserted " + "'" + item + "'" + " into tree. Frequency: " + root.getFreq());
	} else {
		TreeNode node = findNode(this.root, item);
		if(node!=null) {
			node.upFreq();
			System.out.print( "'" + item + "'" + " already exists!");
		} else {
			node = insert(this.root, item);
			System.out.print("inserted " + "'" + item + "'" + " into tree!");
		}  
		System.out.println(" Frequency: " + node.getFreq());
	}
}



Hope this helps.


I am not quite sure what to do with the second insert method.... since one already exists
private TreeNode insert(TreeNode parent, String item){ 
}


Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5796
  • View blog
  • Posts: 12,631
  • Joined: 16-October 07

Re: count frequency of strings in java binary tree

Posted 16 April 2013 - 03:50 PM

View Postccb77, on 16 April 2013 - 05:45 PM, said:

I am not quite sure what to do with the second insert method.... since one already exists


Quite, but it's not really inserting anything. Binary trees are often an exercise in recursion, so you'd pass the head. Must like you did with your searchTree?

Let's revisit your insert:
public void insert(String item){
	if (isEmpty()) {
		// good, you create a root, presumably this.root
		root = new TreeNode(item); 
	} else if(searchTree(root,item)){
		// you have now confirmed that item exists
		
		// however, this is pointless
		root.upFreq();
		// you're always calling this on the root
		// don't you thing you'd want to call it on the node that contains item?
	} else {
		// without knowing what TreeNode looks like
		// this may not work either
		root.add(item); 
	}



If you're going by the code you linked to, your TreeNode should be simply data. Your insert should be walking the tree.
Was This Post Helpful? 0
  • +
  • -

#7 ccb77  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 24-March 13

Re: count frequency of strings in java binary tree

Posted 16 April 2013 - 04:33 PM

Its not a binary search Tree, its a balanced binary tree. We were told specifically not to use it as a search tree
Was This Post Helpful? 0
  • +
  • -

#8 ccb77  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 24-March 13

Re: count frequency of strings in java binary tree

Posted 16 April 2013 - 04:44 PM

I suppose that is my question.

I cant always call on the root, so how do I call this for left and right?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1