CODEWITHSUNDEEP
c++binary-search-tree
Chichi
Chichi

Reputation: 25

Counting the unique values in a binary search tree

I have a binary search tree. So far, I've been able to sort the tree using in-order traversal. My tree is a tree of strings being read from a file, and I want to count all the unique values within the tree (I need to use the duplicates for another part of the code, so I can't make a new tree with no duplicates and count that). I need to traverse the tree to count these unique values.

I thought it would be easy to count the unique values if everything is sorted, I'm not sure why I am having problems.

This code works: 

int uniqueCount(node* root, string c){
  int count = 0;
  if(root == NULL)
    return 0;

  else

  if (root->word == c)
  count++;

  return 1 + uniqueCount(root->left, c) + uniqueCount(root->right, c);
}

But it counts all the nodes, including the duplicates, which I don't want.

So, I wrote this: 

int uniqueCount(node* root, string c){
  int counter = 0;
  string found, temp = " ";

  if (root == NULL){
    counter = 0;
  }
    else{
    if (c == root->word){
      temp = c;
    }
      if(found != temp){
        counter++;
        found = temp;
      }
  }

return 1 + uniqueCount(root->left, c) + uniqueCount(root->right, c);
}

But now my code prints nothing.

Here's my main code: 

int main()
{
  node *T;
  ifstream fin;
  string c;
  int counter;

  fin.open("C:\\Users\\owner\\Documents\\mytest.txt");
  if(fin.fail())
  {
    cout << "Could not find your file. Shutting down.";
    exit(1);
  }

  else{
  T = NULL;

  while(!fin.eof()){
    if (c != " ")
    bInsert (c, &T);
    counter = uniqueCount(T, c);
    fin >> c;
  }
}


cout << "Number of distint words are: " << counter << endl;
  cout << "In-order\n";
  inOrder(T); cout << endl;

I would appreciate any help.

EDIT: So far this semester, the data structures we've learned are stacks, queues, lists, and now, binary trees. So for this project, I would only be allowed to use these data structures. I would not be allowed to use hash tables, or maps, or sets, etc.

Upvotes: 0

Views: 2999

Answers (2)

user11747064
user11747064

Reputation:

If you want to count unique content of binary tree then try this code this format

void uniquecount(struct Node* node) 
{ 
    int count=0;//make this global to bring value out of function
    if (node == NULL) 
        return; 
    uniquecount(node->left); 
    if(node->right!=NULL && node->right==node->data)
    count--;
    else
    count++;
    uniquecount(node->right); 
}

Just make sure that while creating binary tree insert the node to right if parent data is equal.

Upvotes: 2

wydadman
wydadman

Reputation: 36

If your only concern is to count the unique occurrences in your text, try this:

int main()
{
  string c;
  ifstream fin;
  set<string> unique_words;

  fin.open("C:\\Users\\owner\\Documents\\mytest.txt");
  if(fin.fail())
  {
    cout << "Could not find your file. Shutting down.";
    exit(1);
  }

  else{

  while(!fin.eof()){
    fin>>c;
    unique_words.insert(c);
  }
  int counter=unique_words.size();
  cout << "Number of distint words are: " << counter << endl;
  cout << "In-order\n";
  for(auto a:unique_words)
    cout<<a<<' '; //Use whatever separator you want
  return 0;
}

The idea here is that the set container implements a binary tree. But no duplicate are allowed. As the set contains only unique values, then the number of unique elements is nothing less than the size of the set. If you really want to keep the duplicate then use multiset.

Upvotes: 1

Related Questions