Trie in C++ - Sanfoundry

This C++ Program demonstrates the implementation of Trie.

Here is source code of the C++ Program to demonstrate the implementation of Trie. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```
```
 * C++ Program To Implement Trie
```
```
 */
```
```
#include <iostream>
```
```
#include <vector>
```
```
#include <string>
```
```
#include <list>
```
```
#include <algorithm>
```
```
using namespace std;
```
```
 
```
```
/*
```
```
 * Trie Node base declaration
```
```
 */
```
```
struct Trie_node_base
```
```
{
```
```
    vector<Trie_node_base*> child;
```
```
    int num_of_child;
```
```
 
```
```
    Trie_node_base(int n)
```
```
    {
```
```
        num_of_child = n;
```
```
        for (int i = 0; i < n; ++i)
```
```
            child.push_back(NULL);
```
```
    }
```
```
};
```
```
/*
```
```
 * Trie Node Declaration
```
```
 */
```

struct Trie_node : public Trie_node_base

```
{
```
```
    bool is_word;
```

    vector<vector<string>::const_iterator> head;

```
 
```

    Trie_node(int num):Trie_node_base(num), is_word(false){}

```
};
```
```
 
```
```
/*
```
```
 * Trie Class Declaration
```
```
 */
```
```
class Trie
```
```
{
```
```
    public:
```
```
        Trie(int n = 26)
```
```
        {
```
```
            root = new Trie_node(n);
```
```
        }
```
```
        ~Trie()
```
```
        {
```
```
            destroy(root);
```
```
        }
```
```
 
```

        void i_trie_node(const string& w, vector<string>::const_iterator ind);

```
 
```
```
        Trie_node* get_root_node()
```
```
        {
```
```
            return root;
```
```
        }
```
```
        private:
```
```
            Trie_node* root;
```

            void destroy(Trie_node* root);

```
};
```
```
/*
```
```
 * Insert Trie Node
```
```
 */
```

void Trie::i_trie_node(const string& w, vector<string>::const_iterator ind)

```
{
```
```
    Trie_node *r = root;
```

    string::const_iterator runner = w.begin();

```
    for (; runner!=w.end(); ++runner)
```
```
    {
```
```
        char cur_char = *runner;
```
```
        int i = cur_char - 'a';
```
```
 
```
```
        if (r->child[i] == NULL)
```
```
        {
```

            r->child[i] = new Trie_node(r->num_of_child);

```
        }
```
```
        r = (Trie_node*)r->child[i];
```
```
    }
```
```
 
```
```
    if (!r->is_word)
```
```
        r->is_word = true;
```
```
    r->head.push_back(ind);
```
```
}
```
```
/*
```
```
 * Destroy Trie
```
```
 */
```
```
void Trie::destroy(Trie_node* root)
```
```
{
```

    vector<Trie_node_base*>::iterator it = (root->child).begin();

```
 
```

    for (; it != (root->child).end(); ++it)

```
    {
```
```
        if (*it != NULL)
```
```
            destroy((Trie_node*)(*it));
```
```
    }
```
```
    delete root;
```
```
}
```
```
 
```
```
/*
```
```
 * Trie Traversal
```
```
 */
```

void traversal_trie(const vector<string>& word_arr, Trie_node* r)

```
{
```
```
    size_t i;
```
```
    if (r->is_word)
```
```
    {
```

        vector<vector<string>::const_iterator>::iterator it = (r->head).begin();

        for (; it != (r->head).end(); ++it)

```
        {
```
```
            cout << *(*it) << endl;
```
```
        }
```
```
    }
```
```
 
```
```
 
```

    for (i = 0; i < r->num_of_child; ++i)

```
    {
```
```
        if (r->child[i] != NULL)
```

            traversal_trie(word_arr, (Trie_node*)r->child[i]);

```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Clustering of Anagrams Using Trie
```
```
 */
```

void cluster_anagrams(const vector<string>& word_arr, size_t size)

```
{
```
```
    Trie* trie = new Trie(26);
```
```
 
```

    vector<string>::const_iterator it = word_arr.begin();

```
    for (; it != word_arr.end(); ++it)
```
```
    {
```
```
        string cur_str = *it;
```

        sort (cur_str.begin(), cur_str.end());

```
        trie->i_trie_node(cur_str, it);
```
```
    }
```

    traversal_trie(word_arr, trie->get_root_node());

```
}
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```

    const char* word_arr[] = {"cat", "dog", "tac", "god", "act", "gdo"};

    size_t size = sizeof(word_arr) / sizeof(word_arr[0]);

    vector<string> word_arr1(word_arr, word_arr + size);

```
    cluster_anagrams(word_arr1, size);
```
```
    return 0;
```
```
}
```

$ g++ trie.cpp
$ a.out
 
cat
tac
act
dog
god
gdo
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Subscribe Now: Data Structures in C++ Newsletter | Important Subjects Newsletters

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement LRU Cache

» Next - C++ Program to Implement Vector

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Apply for Information Technology Internship
Buy Computer Science Books
Practice Computer Science MCQs
Buy Programming Books

Recommended Articles: