Подсчет уникальных значений в бинарном дереве поиска - PullRequest
Новая
       48

Подсчет уникальных значений в бинарном дереве поиска

1 голос
/ 04 мая 2020

У меня есть двоичное дерево поиска. До сих пор я был в состоянии сортировать дерево, используя обход по порядку. Мое дерево - это дерево строк, считываемых из файла, и я хочу подсчитать все уникальные значения в дереве (мне нужно использовать дубликаты для другой части кода, поэтому я не могу создать новое дерево без дубликаты и считайте это). Мне нужно пройти по дереву, чтобы посчитать эти уникальные значения.

Я думал, что было бы легко посчитать уникальные значения, если все отсортировано, я не уверен, почему у меня проблемы.

Этот код работает: 

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

Но он подсчитывает все узлы, включая дубликаты, которые мне не нужны.

Итак, я написал это: 

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

Но теперь мой код ничего не печатает.

Вот мой основной код: 

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;

Я бы ценю любую помощь.

РЕДАКТИРОВАТЬ: До сих пор этот семестр, структуры данных, которые мы изучили, были стеки, очереди, списки, а теперь и двоичные деревья. Так что для этого проекта мне будет разрешено использовать только эти структуры данных. Мне не разрешили бы использовать ha sh таблицы, или карты, или наборы и т. Д. c.

Ответы [ 2 ]

1 голос
/ 04 мая 2020

Если вы хотите подсчитать количество уникального содержимого двоичного дерева, попробуйте этот код в следующем формате 

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

Просто убедитесь, что при создании двоичного дерева вставьте узел вправо, если родительские данные равны.

1 голос
/ 04 мая 2020

Если ваша единственная задача заключается в подсчете уникальных вхождений в вашем тексте, попробуйте следующее: 

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

Идея заключается в том, что контейнер set реализует двоичное дерево. Но дубликаты не допускаются. Поскольку набор содержит только уникальные значения, то количество уникальных элементов не меньше, чем размер набора. Если вы действительно хотите сохранить дубликат, используйте multiset.

...