c++ - 计算二叉搜索树中的唯一值

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;

我将不胜感激任何帮助。

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

Answer 1

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

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

只要确保在创建二叉树时，如果父数据相等，则在右边插入节点。