fork download
copy 
  1. #include<iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int alpha=26;
  5.  
  6. class trie {
  7.  
  8. private: 
  9.  
  10. 	struct node{
  11. 		vector<node*> child;
  12. 		bool end;
  13. 		int countchild;
  14. 			  // initialization should be in the class/struct constructor	
  15. 	node () : child(alpha,nullptr), end(false), countchild(0) { }
  16. 	};
  17.  
  18. 	node* root;  
  19.  
  20. 	void show(node* n,  int inc) {
  21. 		cout<< string(inc, ' ')<<(n->end?"(END)":"()")<<" children:"<<n->countchild<<endl; 
  22. 		for (int i=0; i<alpha; i++) 
  23. 	    if (n->child[i]) {
  24. 	    	cout << string(inc, ' ') << (char)('a'+i)<<": "<<endl; 
  25. 	    	show (n->child[i], inc+2);
  26. 	    }
  27. 	}
  28.  
  29. public:  
  30.     trie() {
  31.     	root = new node; 
  32.     }
  33.  
  34. 	~trie() {
  35. 	//TODO rule of 3	
  36. 	}
  37.  
  38. 	trie& operator= (trie) = delete;  //TODO rule of 3
  39.  
  40. 	void insert(string key){
  41.     	node* pcrawl=root;
  42.     	for(auto c:key){
  43.         	int index=tolower(c)-'a';
  44.         	if (index<0 || index>=alpha)
  45.         		continue;  
  46.         	if(!pcrawl->child[index]){
  47.             	pcrawl->child[index]=new node; 
  48.         	}
  49.         	pcrawl->countchild+=1;
  50.         	pcrawl=pcrawl->child[index];
  51.  
  52.     	}
  53.     	pcrawl->end=true;
  54. 	}
  55.  
  56.     void show() {
  57.     	show(root,0); 
  58.     }
  59. }; 
  60.  
  61. int main() {
  62. 	trie t;
  63. 	t.insert ("tester");
  64. 	t.insert ("test");
  65. 	t.insert ("TERM");
  66. 	t.insert ("T.;0C"); 
  67.     t.show(); 	
  68. }
Success #stdin #stdout 0s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
() children:4
t: 
  () children:4
  c: 
    (END) children:0
  e: 
    () children:3
    r: 
      () children:1
      m: 
        (END) children:0
    s: 
      () children:2
      t: 
        (END) children:1
        e: 
          () children:1
          r: 
            (END) children:0
https://ideone.com/Yt30Os
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!