Чтение файла для каждого слова и сортировка этих слов с помощью бинарного дерева поиска (лексикографически)
Привет коллеги программисты,
Я работаю над заданием, которое требует от нас прочитать файл, взять каждое слово из этого файла и отсортировать его в таблице, которая отображает слово и номер строки, в которой оно существует.
пример:
Файл, который нужно прочитать, содержит:
this is a
text file isРешение
Я думаю, что вы усложняете проблему. Если бы я был тобой, я бы определил структуру как
struct Whatever
{
string word;
vector<int> line;
};
и объявить vector<Whatever> text
После этого вы можете использовать алгоритм sort с пользовательской функцией сравнения, которая будет сортировать ваши text вектор в лексикографическом порядке.
Если вам действительно нужно использовать двоичные деревья поиска для назначения, найдите время и проведите некоторое исследование. Основная идея заключается в том, что каждый раз, когда вы хотите вставить узел в дерево, вы сравниваете его с текущим узлом (который в начале будет корневым) и смотрите, будет ли он больше или меньше по значению (в вашем случае, лексикографическое сравнение) и двигайтесь в указанном направлении (слева на меньшее, справа на большее), пока не дойдете до узла NULL и там не добавите его. После этого вы можете создать лексикографический порядок, выполнив left-root-right Разбор дерева. Опять же, я бы использовал это struct для простоты.
Другие решения
Вот структура, которую вы должны использовать вместе с функцией вставки для реализации проблемы с использованием бинарного дерева:
struct TreeNode{
string word; //word will store the word from text file
vector<int>lines; //for keeping record of lines in which it was found
TreeNode*left; //pointer to left subtree
TreeNode*right; //pointer to right subtree
};
В вашем случае вы включили эту структуру в class LexTree который не сильно помогает, а усложняет вещи.
Вот как вы должны реализовать функцию вставки
TreeNode* insert(TreeNode *root,string word,int lineNumber)
{
//Tree is NULL
if(root==NULL){
root=new TreeNode();
root->word=word;
root->lines.push_back(lineNUmber);
}
//words match
else if(root->word==word)
root->lines.push_back(linenumber);
//check(a,b)is funtion that returns 1 if 'string a' is bigger than 'string b' lexographically
else if(check(root->word,word)){//present word is lexographically bigger than root's word
if(root->right) //if right node to root is not null we insert word recursively
root->right=insert(root->right,word,lineNumber);
else{ //if right node is NULL a new node is created
Node*temp=new TreeNode();
temp->word=word;
temp->lines.push_back(lineNumber);
root->right=temp;
}
}
else{ //present word is lexographically smaller than root's word
if(root->left)
root->left=insert(root->left,word,lineNumber);
else{
Node*temp=new TreeNode();
temp->word=word;
temp->lines.push_back(lineNumber);
root->left=temp;
}
}
}
РЕДАКТИРОВАТЬ-
Вот ваша функция проверки
bool check(string a,string b)
{
if(a>b)
return false;
return true;
}
Использовать insert просто пройдите root node of your BST вместе с вашим word в качестве аргументов insert
Некоторые твики в InOrder и главное, что должно решить проблему
//Print tree in In-Order traversal
void InOrder(TreeNode* node)
{
if(!node) //end if pointing to null
return;
InOrder(node->left); //display the left subtree
cout << node->word << " "; //display current nodefor(int i=0;i<node->lines.length();i++) //vector lines contains all the line numbers where we had the word node->word
cout<<nodes->lines[i]<<" ";
cout<<endl;}//end InOrder
int main() { //main
//int lineNumber = 0; //number of linesTreeNode *root=NULL; //you need to declare root to make a BSTifstream file("text.txt"); //takes input stream from designated file
if(file) { //if file is there
string line, word ; //setting line and word strings
while(getline(file, line)) { //getting the lines from the file
//++lineNumber; //incrementing number of lines when a new line is read
istringstream is(line); //checking for a line
while(is >> word) { //while a word existsroot=insert(root,word); // insert word in your BST}//end word while
}//end getline whileInorder(root); //gives required output}//end file if
file.close();
file.clear();
return 0;
}//end main