Cài đặt trie

code:


#include<algorithm>
#include<iostream>

using namespace std;

class trie
{
private:
struct nodeTrie
{
char c; // ki tu cua nut hien tai
bool eow; // danh dau nut nay het mot tu
int prefixes; // cho biet co bao nhieu nut truoc nut nay
nodeTrie* edge[26]; //
}*root;
void preorder_display(nodeTrie* leaf);
void destroy_trie(nodeTrie* leaf);
void delete_node(nodeTrie* leaf);

public:
trie();
~trie();

void insert_word(char* w);
void delete_word(char* w);
bool search_word(char* w);
void display();

};

trie::trie()
{
root = new nodeTrie();
root->c = '\0';
root->prefixes = 0;
root->eow = false;
for(int i = 0; i < 26; i++)
root->edge[i] = NULL;
}
void trie::destroy_trie(nodeTrie* leaf)
{
for(int i = 0; i < 26; i++)
if(leaf->edge[i] != NULL) destroy_trie(leaf->edge[i]);
delete(leaf);
}
trie::~trie()
{
destroy_trie(root);
}

void trie::insert_word(char* w)
{
nodeTrie* leaf = root;
while(*w != '\0')
{
int index = toupper(*w) - 'A';
if(leaf->edge[index] == NULL)
{
nodeTrie* child = new nodeTrie();
child->c = *w;
child->eow = false;
child->prefixes = 1;
for(int i = 0; i < 26; i++)
child->edge[i] = NULL;
leaf->edge[index] = child;
leaf = child;
}
else
{
leaf = leaf->edge[index];
leaf->prefixes++;
}
w++;
}
leaf->eow = true;
}
bool trie::search_word(char * w)
{
nodeTrie* leaf = root;
while(*w != '\0')
{
int index = toupper(*w) - 'A';
if(leaf->edge[index] == NULL) return false;
leaf = leaf->edge[index];
w++;
}
return leaf->eow;
}
void trie::delete_word(char* w)
{
nodeTrie* leaf = root;
while(*w != '\0')
{
int index = toupper(*w) - 'A';
if(leaf->edge[index] == NULL) return;
else if(leaf->edge[index]->prefixes == 1)
{
destroy_trie(leaf->edge[index]);
leaf->edge[index] = NULL;
return;
}
else
{
//if(leaf->count > 1) leaf->count--;
leaf=leaf->edge[index];
}
w++;
}
}
void trie::preorder_display(nodeTrie* leaf)
{
if(leaf == NULL) return;
cout << leaf->c << ":" << leaf->eow << ":" << leaf->prefixes << endl;
for(int i=0; i< 26; i++)
if(leaf->edge[i] != NULL)
preorder_display(leaf->edge[i]);
}
void trie::display()
{
preorder_display(root);
}


int main()
{
trie mytrie;
    char *s[] = {"tree","trie","algo","assoc","all","also","ass"};
    for(int i=0;i<sizeof(s)/sizeof(*s);i++)
    {
        mytrie.insert_word(s[i]);
    }

    mytrie.display();

    if(mytrie.search_word("all") == true) cout << "all exist" << endl;
    else cout << "all do not exist" << endl;

    mytrie.delete_word("all");

    if(mytrie.search_word("all") == true) cout << "all exist" << endl;
    else cout << "all do not exist" << endl;

    mytrie.display();

if(mytrie.search_word("also") == true) cout << "all exist" << endl;
    else cout << "all do not exist" << endl;

system("pause");

return 0;
}