C ++ Двоичное дерево поиска сравнивает данные узлов и удаляет дубликаты
Я создал двоичное дерево поиска в C ++ и загрузил его двумя типами данных, строками и целыми числами. Я читаю текстовый файл и загружаю дерево в алфавитном порядке со словами, которые я вытягиваю, а также номер строки, в которой находится слово. Я могу печатать слова и цифры просто отлично. Что я хочу сделать сейчас, так это проверить, было ли слово уже напечатано, и если это так, то я буду печатать только номер строки, из которой найдено слово. Я думаю об этом, сравнивая предыдущие данные, когда дерево пересекается и печатается. Это моя функция печати.
void inOrderPrint(Node *rootPtr ) {
if ( rootPtr != NULL ) {
for (int i =0; rootPtr->data[i]; i++){
while(ispunct(rootPtr->data[i]))
rootPtr->data.erase(i,1);
}
rootPtr->data = rootPtr->data.substr(0,10);
inOrderPrint( rootPtr->left );
cout << (rootPtr->data)<<rootPtr->lineNum <<endl;
inOrderPrint( rootPtr->right );
}
}
Вот о чем я думал:
if (rootPtr->data == previous rootPtr->data)
cout<<setw(10)<<theCurrentNode lineNum;
else
do normal printing
Я думаю, что если бы эта функция выполнялась на первом узле и сравнивала его с несуществующим предыдущим узлом, она автоматически пыталась бы сравнить его с NULL, оператор if вернул бы false и перешел бы к другому.
Любые предложения о том, как сделать это с фактическим синтаксисом C ++? Или кто-нибудь видит изъян в моей логике?
Заранее спасибо!
Решение
В этом ответе будет описано, как заставить программу печатать уникальные записи и номер строки первого вхождения в файле. Если есть повторяющиеся экземпляры, будет напечатан только номер строки первого экземпляра для каждого дублированного экземпляра. Подход заключается в том, чтобы убедиться, что в дереве нет повторяющихся узлов, и подсчитать избыточные вхождения.
Для этого мы можем изменить структуру узла следующим образом:
struct Node{
string data;
int lineNum;
int count =1;
Node* left;
Node* right;
};
Функция Insert может быть отредактирована для подсчета дубликатов следующим образом:
Node* Insert(Node* rootPtr,string data,int lineNum){
if(rootPtr == NULL){
rootPtr = GetNewNode(data,lineNum);
for (int i =0; rootPtr->data[i]; i++){
while(ispunct(rootPtr->data[i]))
rootPtr->data.erase(i,1);
}
rootPtr->data = rootPtr->data.substr(0,10);
return rootPtr;
}
else if(data< rootPtr->data){
rootPtr->left = Insert(rootPtr->left,data,lineNum);
for (int i =0; rootPtr->data[i]; i++){
while(ispunct(rootPtr->data[i]))
rootPtr->data.erase(i,1);
}
rootPtr->data = rootPtr->data.substr(0,10);
}
else if(data > rootPtr->data) {
rootPtr->right = Insert(rootPtr->right,data,lineNum);
for (int i =0; rootPtr->data[i]; i++){
while(ispunct(rootPtr->data[i]))
rootPtr->data.erase(i,1);
}
rootPtr->data = rootPtr->data.substr(0,10);
}
else if(data == rootPtr->data)
++rootPtr->count;
return rootPtr;
}
Наконец, функция печати может быть изменена:
void inOrderPrint(Node *rootPtr ) {
//ofstream outputFile;
//outputFile.open("Output.txt");
if ( rootPtr != NULL ) {
inOrderPrint( rootPtr->left );
cout << (rootPtr->data)<<" " << rootPtr->lineNum <<endl;
int j =rootPtr->count;
while( --j )
cout << rootPtr->lineNum <<endl;
//outputFile << (rootPtr->data)<<rootPtr->lineNum <<endl;
inOrderPrint( rootPtr->right );
}
}
Теперь это должно быть намного ближе к тому, что вы хотите. Также было бы неплохо отделить обработку текста от обработки узла. (Этот ответ предполагает, что вы позаботитесь об этом.) В противном случае будут созданы дублирующие узлы, если предварительно обработанный текст не соответствует обработанному тексту.
Удачи!
Другие решения
Других решений пока нет …