我很新尝试。我在网上找到了一些解决方案,但是尝试的定义完全不同。我需要这种特里的解决方案。
我需要的功能是按字母顺序打印trie中的所有单词。如您所见,插入和搜索功能已完成。这是2个头文件,对于主代码来说是必需的。
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;
}
最佳答案
我知道这个问题发布已经快一年了,但最终我找到了解决方案。这里是....
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;
}
我希望这会帮助某人弄清楚如何处理这些类型的树
关于c++ - 从trie按字母顺序打印所有单词,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/35253496/