next up previous contents index Search
Next: 0.2.10 Quadtrees and Octrees Up: 0.2.9 Tries Previous: 0.2.9 Tries

0.2.9.1 Source Code

This code, in C++, implements an alphabetic trie class.





 struct trie_node {
 
     // how many nodes are beneath this one?
     int count;                      
 
     // array of pointers to children
     trie_node *child_list[ALPH_SIZE];
 
     // initializer...
     trie_node();
 };
 
 trie_node::trie_node() {
 
     // there is nothing below us...
     count = 0;
 
     // all child pointers start out pointing nowhere...
     for(int index = 0; index < ALPHABET_SIZE; index++)
         child_list[index] = NULL;
 }
 
 
 
 class Trie {
 
 public:
     
     // methods
 
     Trie(int level, int chars);        // create it
     ~Trie();                           // destroy trie nodes
     int node_count;                    // the number of nodes in whole trie
     void AddToTrie(const string \&s);   // add string to trie
     
 private:
 
     // methods
 
     void recursive_delete (trie_node * t);     // recursive delete helper function
     
 
 
     // data
 
     int node_count;                      // number of nodes in the trie
     trie_node * Root;                  // the root of the trie
 };
 
 
 
 
 Trie::Trie() {
     node_count = 0;
     Root(new trie_node);
 }
 
 
 Trie::~Trie() {
 
     // delete whole trie
     recursive_delete(myRoot);
 }
 
 
 void Trie::recursive_delete(trie_node * t) {
     int index;
 
     if (t != NULL) {
 
         // delete all children
         for(index = 0; index < ALPHABET_SIZE; index++)
            recursive_delete(t->child_list[index]);
 
 	// delete self
         delete t;
     }
 }
 
 
 
 
 int Trie::node_count() {
 
     return (node_count);
 
 }
 
      
 
 void Trie::AddToTrie(const string \&s) {
     int lcv, index;
 
     trie_node *t = Root;
     
     // there is one more string stored somewhere under the root...
     t->count++;
     
 
     // loop over the length of the string to add and traverse the trie...
     for(lcv=0; lcv < s.length(); lcv++) {
 
         index = s[lcv]; // the character in s we are processing...
 
 	// is there a child node for this character?
         if (t->child_list[index] == NULL) {
 
 	    // if not, make one!
             t->child_list[index] = new trie_node;
             node_count++;
         }
 
         // there is another string under this node...
         t->child_list[index]->count++;
 
         // move to it this node... and loop
         t = t->child_list[index];
     }
 }




Scott Gasch
1999-07-09