Распечатать все слова в алфавитном порядке от trie

Question

Я довольно новичок в попытках. Я нашел некоторые решения в сети, но попытки определяются совершенно по-другому. Мне нужно решение для этого типа trie.

Мне нужна функция печати всех слов из trie в алфавитном порядке. Как видите, выполняются функции «Вставка» и «Поиск». Вот два файла заголовков, необходимых для основного кода.

EntryType.h

#include <iostream> 
using namespace std; 

const int MAXLENGTH = 10; 
class EntryType 
{ 
public: 
    EntryType(); 
    EntryType(char * key); 
    EntryType(EntryType & entry); 
    ~EntryType(); 
    bool operator== (const EntryType& item) const; 
    bool operator!= (const EntryType& item) const; 
    friend istream& operator>> (istream& is, EntryType& item); 
    friend ostream& operator<< (ostream& os, EntryType item); 
    void EntryKey(char word[]); 
    void PrintWord(); 

private: 
    char entryKey[MAXLENGTH]; 
}; 

ostream& operator<< (ostream& os, EntryType item) 
{ 
    os << item.entryKey; 
    return os; 
} 

EntryType::EntryType() 
{ 
    // empty instance constructor 
} 
EntryType::~EntryType() 
{ 
    // destructor 
} 

void EntryType::EntryKey(char word[]) 
{ 
    for (int i = 0; i < 10; i++) 
    { 
     entryKey[i] = word[i]; 
    } 
} 

void EntryType::PrintWord() 
{ 
    cout << entryKey << endl; 
} 

TrieType.h

#include <iostream> 
#include <string> 
#include "EntryType.h" 


const int LETTERS = 26; 
typedef char Key[MAXLENGTH]; 
struct Trienode 
{ 
    Trienode *branch[LETTERS]; 
    EntryType *ref; 
}; 

class TrieType 
{ 

private: 
    Trienode * root; 

public: 
    TrieType(); 
    ~TrieType(); 
    TrieType(TrieType &originalTree); 
    void operator=(TrieType & originalTree); 
    void MakeEmpty(); 
    void InsertTrie(Key newkey, EntryType *newentry); 
    EntryType * TrieSearch(Key target); 
    bool DeleteTrie(Key delkey); 
    void PrintTrie(); 
}; 

TrieType::TrieType() 
{ 
    root = NULL; 
} 


TrieType::~TrieType() 
{ 
    // destructor 
} 
TrieType::TrieType(TrieType &originalTree) 
{ 
    // constructor 
} 

EntryType *TrieType::TrieSearch(Key target) 
{ 
    int i; 
    Trienode * current = root; 
    for (i = 0; i < MAXLENGTH && current; i++) 
    if (target[i] == '\0') 
     break; 
    else 
     current = 
     current->branch[target[i] - 'a']; 
    if (!current) 
     return NULL; 
    else 
    if (!current->ref) 
     return NULL; 

    return current->ref; 
} 


Trienode *CreateNode() 
{ 
    int ch; 
    Trienode *newnode = new Trienode; 
    for (ch = 0; ch < LETTERS; ch++) 
     newnode->branch[ch] = NULL; 

    newnode->ref = NULL; 

    return newnode; 
} 

void TrieType::InsertTrie(Key newkey, EntryType *newentry) 
{ 
    int i; 
    Trienode *current; 
    if (!root) 
     root = CreateNode(); 
    current = root; 
    for (i = 0; i < MAXLENGTH; i++) 
    if (newkey[i] == '\0') 
     break; 
    else 
    { 
     if (!current->branch[newkey[i] - 'a']) 
      current->branch[newkey[i] - 'a'] = CreateNode(); 
     current = current->branch[newkey[i] - 'a']; 
    } 
    if (current->ref != NULL) 
     cout << "\nTried to insert a duplicate key." << endl; 
    else 
     current->ref = newentry; 
} 

Answer 1

Я знаю, что почти год прошел после того, как я отправляю этот вопрос, но в конце концов я нашел решение. Здесь ....

TrieType.h

#include <iostream> 
#include <string> 
//added:############################################### 
#include<algorithm> 
#include<vector> 
//##################################################### 
#include "EntryType.h" 


const int LETTERS = 26; 
typedef char Key[MAXLENGTH]; 
struct Trienode 
{ 
    Trienode *branch[LETTERS]; 
    EntryType *ref; 
}; 

class TrieType 
{ 

private: 
    Trienode * root; 

public: 
    TrieType(); 
    ~TrieType(); 
    TrieType(TrieType &originalTree); 
    void operator=(TrieType & originalTree); 
    void MakeEmpty(); 
    void InsertTrie(Key newkey, EntryType *newentry); 
    EntryType * TrieSearch(Key target); 
    bool DeleteTrie(Key delkey); 
    void PrintTrie(); 
}; 

TrieType::TrieType() 
{ 
    root = NULL; 
} 


TrieType::~TrieType() 
{ 
    // destructor 
} 
TrieType::TrieType(TrieType &originalTree) 
{ 
    // constructor 
} 

EntryType *TrieType::TrieSearch(Key target) 
{ 
    int i; 
    Trienode * current = root; 
    for (i = 0; i < MAXLENGTH && current; i++) 
    if (target[i] == '\0') 
     break; 
    else 
     current = 
     current->branch[target[i] - 'a']; 
    if (!current) 
     return NULL; 
    else 
    if (!current->ref) 
     return NULL; 

    return current->ref; 
} 


Trienode *CreateNode() 
{ 
    int ch; 
    Trienode *newnode = new Trienode; 
    for (ch = 0; ch < LETTERS; ch++) 
     newnode->branch[ch] = NULL; 

    newnode->ref = NULL; 

    return newnode; 
} 

void TrieType::InsertTrie(Key newkey, EntryType *newentry) 
{ 
    int i; 
    Trienode *current; 
    if (!root) 
     root = CreateNode(); 
    current = root; 
    for (i = 0; i < MAXLENGTH; i++) 
    if (newkey[i] == '\0') 
     break; 
    else 
    { 
     if (!current->branch[newkey[i] - 'a']) 
      current->branch[newkey[i] - 'a'] = CreateNode(); 
     current = current->branch[newkey[i] - 'a']; 
    } 
    if (current->ref != NULL) 
     cout << "\nTried to insert a duplicate key." << endl; 
    else 
     current->ref = newentry; 
} 

//Added:################################################################33 
void Traverse(Trienode *current,vector<string> v) 
{ 
    if(current->ref != NULL) 
    { 
     //add the same prevous word as the new word, will remove char by char while moving upwards the tree to get into ne branch 
     v.push_back(v[v.size()-1]); 
     return; 
    } 
    for (int i = 0; i < LETTERS; i++) 
    { 
     if(current->branch[i] != NULL) 
     { 
      //each level contains childs as much as english letters in the same order(if any is null then the letter in this position is not used) 
      v[v.size()-1] += (char)((int)'a' + i); 
      current = current->branch[i]; 
      Traverse(current, v); 
      //remove any additional chars from previous word to get new word from continuing from old word 
      v[v.size()-1] = v[v.size()-1].substr(0, v[v.size()-1].size()-1); 
     } 
    } 
} 

void TrieType::PrintTrie() 
{ 
    //temporarly saves the list of unsorted words 
    vector<string> wordList; 
    wordList.push_back(""); 
    Traverse(root, wordList); 
    sort(wordList.begin(), wordList.end()); 

    for (int i = 0; i < wordList.size(); i++) 
    { 
     cout<<"Word "<<i<<": "<<wordList[i]<<endl; 
    } 
} 

EntryType.h

#include <iostream> 
using namespace std; 

const int MAXLENGTH = 10; 
class EntryType 
{ 
public: 
    EntryType(); 
    EntryType(char * key); 
    EntryType(EntryType & entry); 
    ~EntryType(); 
    bool operator== (const EntryType& item) const; 
    bool operator!= (const EntryType& item) const; 
    friend istream& operator>> (istream& is, EntryType& item); 
    friend ostream& operator<< (ostream& os, EntryType item); 
    void EntryKey(char word[]); 
    void PrintWord(); 

private: 
    char entryKey[MAXLENGTH]; 
}; 

ostream& operator<< (ostream& os, EntryType item) 
{ 
    os << item.entryKey; 
    return os; 
} 

EntryType::EntryType() 
{ 
    // empty instance constructor 
} 
EntryType::~EntryType() 
{ 
    // destructor 
} 

void EntryType::EntryKey(char word[]) 
{ 
    for (int i = 0; i < 10; i++) 
    { 
     entryKey[i] = word[i]; 
    } 
} 

void EntryType::PrintWord() 
{ 
    cout << entryKey << endl; 
} 

main.cpp

#include <iostream> 
#include <string> 
#include "TrieType.h" 

using namespace std; 

TrieType t; 
char newelem[10]; 

void insert(TrieType & trie) 
{ 
    Key word; 
    cout << "Enter the word you would like to insert into trie: " << endl; 
    cin >> word; 

    EntryType* newEntry = new EntryType; 
    newEntry->EntryKey(word); 

    trie.InsertTrie(word, newEntry); 
    cout << "Word " << word <<" has been inserted into trie!"<< endl; 
} 

void getAllWords(TrieType & trie) 
{ 
    cout << "All words in trie are: " << endl; 

    EntryType* newEntry = new EntryType; 
    //newEntry->PrintWord(); 
    trie.PrintTrie(); 
} 

int main() 
{ 
    int i; 

    do 
    { 
     cout << "\nMENU\n-------------------- " << endl; 
     cout << "1. Insert into a Trie" << endl; 
     cout << "2. Search a Trie" << endl; 
     cout << "3. Print Words Alphabetically" << endl; 
     cout << "4. Exit" << endl; 
     cout << "Please enter an integer value: "; 
     cin >> i; 
     switch (i) 
     { 
     case 1: 
      insert(t); 
      break; 
     case 2: 
      cout << "Enter string to search trie:"; 
      cin >> newelem; 
      if (t.TrieSearch(newelem) != NULL) 
      { 
       cout << "String " << newelem << " is member of trie!" << endl; 
      } 
      else 
      { 
       cout << "String " << newelem << " is NOT member of trie!" << endl; 
      } 
      break; 
     case 3: 
      cout << "TO BE DONE!!!" << endl; 
      t.PrintTrie(); 
      break; 
     case 4: 
      cout << "Exiting program..." << endl; 
      break; 
     default: 
      cout << "Wrong input" << endl; 
      break; 
     } 

    } while (i != 4); 
    return 0; 
} 

Я надеюсь, что это поможет кому-то, чтобы выяснить, как иметь дело с этими типами деревьев