计算二进制搜索树中的唯一值

Question

我有一个二叉搜索树。到目前为止，我已经能够使用有序遍历对树进行排序。我的树是一棵从文件中读取的字符串树，我想计算树中的所有唯一值（我需要在代码的另一部分中使用重复项，所以我不能创建没有它的新树复制并计数）。我需要遍历树以计算这些唯一值。

我认为，如果所有内容都经过排序，则计算唯一值会很容易，我不确定为什么会遇到问题。

此代码有效：

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;

我将不胜感激。

编辑：到目前为止，本学期，我们所学习的数据结构是堆栈，队列，列表，现在是二进制树。因此，对于本项目，只允许我使用这些数据结构。我将不允许使用哈希表，地图或集合等。

Answer 1

如果您唯一要考虑的是计算文本中的唯一出现次数，请尝试以下操作：

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。

Answer 2

如果要计数二进制树的唯一内容，请尝试使用此格式的代码

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==node->data)
    count--;
    else
    count++;
    uniquecount(node->right); 
}

如果父数据相等，请确保在创建二叉树时将节点插入到右边

Answer 3

如果要计数二进制树的唯一内容，请尝试使用此格式的代码

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->data==node->data)
    count--;
    else
    count++;
    uniquecount(node->right); 
}

如果父数据相等，请确保在创建二叉树时将节点插入到右边