C++ Program to Implement Trie

«
»
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.

  1. /*
  2.  * C++ Program To Implement Trie
  3.  */
  4. #include <iostream>
  5. #include <vector>
  6. #include <string>
  7. #include <list>
  8. #include <algorithm>
  9. using namespace std;
  10.  
  11. /*
  12.  * Trie Node base declaration
  13.  */
  14. struct Trie_node_base
  15. {
  16.     vector<Trie_node_base*> child;
  17.     int num_of_child;
  18.  
  19.     Trie_node_base(int n)
  20.     {
  21.         num_of_child = n;
  22.         for (int i = 0; i < n; ++i)
  23.             child.push_back(NULL);
  24.     }
  25. };
  26. /*
  27.  * Trie Node Declaration
  28.  */
  29. struct Trie_node : public Trie_node_base
  30. {
  31.     bool is_word;
  32.     vector<vector<string>::const_iterator> head;
  33.  
  34.     Trie_node(int num):Trie_node_base(num), is_word(false){}
  35. };
  36.  
  37. /*
  38.  * Trie Class Declaration
  39.  */
  40. class Trie
  41. {
  42.     public:
  43.         Trie(int n = 26)
  44.         {
  45.             root = new Trie_node(n);
  46.         }
  47.         ~Trie()
  48.         {
  49.             destroy(root);
  50.         }
  51.  
  52.         void i_trie_node(const string& w, vector<string>::const_iterator ind);
  53.  
  54.         Trie_node* get_root_node()
  55.         {
  56.             return root;
  57.         }
  58.         private:
  59.             Trie_node* root;
  60.             void destroy(Trie_node* root);
  61. };
  62. /*
  63.  * Insert Trie Node
  64.  */
  65. void Trie::i_trie_node(const string& w, vector<string>::const_iterator ind)
  66. {
  67.     Trie_node *r = root;
  68.     string::const_iterator runner = w.begin();
  69.     for (; runner!=w.end(); ++runner)
  70.     {
  71.         char cur_char = *runner;
  72.         int i = cur_char - 'a';
  73.  
  74.         if (r->child[i] == NULL)
  75.         {
  76.             r->child[i] = new Trie_node(r->num_of_child);
  77.         }
  78.         r = (Trie_node*)r->child[i];
  79.     }
  80.  
  81.     if (!r->is_word)
  82.         r->is_word = true;
  83.     r->head.push_back(ind);
  84. }
  85. /*
  86.  * Destroy Trie
  87.  */
  88. void Trie::destroy(Trie_node* root)
  89. {
  90.     vector<Trie_node_base*>::iterator it = (root->child).begin();
  91.  
  92.     for (; it != (root->child).end(); ++it)
  93.     {
  94.         if (*it != NULL)
  95.             destroy((Trie_node*)(*it));
  96.     }
  97.     delete root;
  98. }
  99.  
  100. /*
  101.  * Trie Traversal
  102.  */
  103. void traversal_trie(const vector<string>& word_arr, Trie_node* r)
  104. {
  105.     size_t i;
  106.     if (r->is_word)
  107.     {
  108.         vector<vector<string>::const_iterator>::iterator it = (r->head).begin();
  109.         for (; it != (r->head).end(); ++it)
  110.         {
  111.             cout << *(*it) << endl;
  112.         }
  113.     }
  114.  
  115.  
  116.     for (i = 0; i < r->num_of_child; ++i)
  117.     {
  118.         if (r->child[i] != NULL)
  119.             traversal_trie(word_arr, (Trie_node*)r->child[i]);
  120.     }
  121. }
  122.  
  123. /*
  124.  * Clustering of Anagrams Using Trie
  125.  */
  126. void cluster_anagrams(const vector<string>& word_arr, size_t size)
  127. {
  128.     Trie* trie = new Trie(26);
  129.  
  130.     vector<string>::const_iterator it = word_arr.begin();
  131.     for (; it != word_arr.end(); ++it)
  132.     {
  133.         string cur_str = *it;
  134.         sort (cur_str.begin(), cur_str.end());
  135.         trie->i_trie_node(cur_str, it);
  136.     }
  137.     traversal_trie(word_arr, trie->get_root_node());
  138. }
  139. /*
  140.  * Main Contains Menu
  141.  */
  142. int main()
  143. {
  144.     const char* word_arr[] = {"cat", "dog", "tac", "god", "act", "gdo"};
  145.     size_t size = sizeof(word_arr) / sizeof(word_arr[0]);
  146.     vector<string> word_arr1(word_arr, word_arr + size);
  147.     cluster_anagrams(word_arr1, size);
  148.     return 0;
  149. }

advertisement
$ 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.

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.