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
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn