3 Replies - 451 Views - Last Post: 02 April 2013 - 07:06 AM Rate Topic: -----

#1 derek3191  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 05-October 12

Binary Trees

Posted 01 April 2013 - 11:36 AM

I have an assignment that I need to create a frequency list of repeating words. We are supposed to use a binary tree for it that will store each word and counter in each node. I don't want to have someone give me the answer. I need to learn this stuff. I know that I need to make a struct then have some sort of recursion to keep checking for the next word.

Here is what I have so far for the tree (its not much):
struct node       
{
string word;
int counter;
node* left;
node* right;
};
node* root = NULL;



Assuming that is right above, I just need help creating a new node for each word (as long as it is a new word), if it's a repeated word, it'll add to the counter.
Any help is greatly appreciated..
Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Trees

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10826
  • View blog
  • Posts: 40,363
  • Joined: 27-December 08

Re: Binary Trees

Posted 01 April 2013 - 11:56 AM

I would start by learning about Binary Trees. There isn't much we can do until you start there.
Was This Post Helpful? 1
  • +
  • -

#3 derek3191  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 05-October 12

Re: Binary Trees

Posted 01 April 2013 - 09:10 PM

Ok, I read it. I have a better understanding of it now thanks. From what I understand, the key value for the node would be the words being counted. The second parameter in the insert function is "*leaf", what is that supposed to be? Also, I am dealing with strings in the node, not numbers. How would I sort the words so that the lower words are on the left and the upper words are on the right to get a balanced tree?
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10826
  • View blog
  • Posts: 40,363
  • Joined: 27-December 08

Re: Binary Trees

Posted 02 April 2013 - 07:06 AM

What you really want is a Binary Search Tree, specifically a balanced BST like an AVL Tree or a Red-Black Tree. You can create a struct to store the word and its count, and sort by count. Though you may want to wait until the words are all counted before inserting them into the tree.

You could also use a Heap, which would make it easier to update elements as you count additional instances of the words.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1