Search code examples
c++binary-treebinary-search-treetrie

Print all words in Alphabetical order from trie


I am pretty new to tries. I found some solutions on net, but tries are defined in totally different way. I need solution for this type of trie.

What I need is function to print all words from trie in alphabetical order. As you can see, Insert and Search functions are done. Here is 2 header files, necessary for main code.

EntryType.h

#include <iostream>
using namespace std;

const int MAXLENGTH = 10;
class EntryType
{
public:
    EntryType();
    EntryType(char * key);
    EntryType(EntryType & entry);
    ~EntryType();
    bool operator== (const EntryType& item) const;
    bool operator!= (const EntryType& item) const;
    friend istream& operator>> (istream& is, EntryType& item);
    friend ostream& operator<< (ostream& os, EntryType item);
    void EntryKey(char word[]);
    void PrintWord();

private:
    char entryKey[MAXLENGTH];
};

ostream& operator<< (ostream& os, EntryType item)
{
    os << item.entryKey;
    return os;
}

EntryType::EntryType()
{
    // empty instance constructor
}
EntryType::~EntryType()
{
    // destructor
}

void EntryType::EntryKey(char word[])
{
    for (int i = 0; i < 10; i++)
    {
        entryKey[i] = word[i];
    }
}

void EntryType::PrintWord()
{
    cout << entryKey << endl;
}

TrieType.h

#include <iostream>
#include <string>
#include "EntryType.h"


const int LETTERS = 26;
typedef char Key[MAXLENGTH];
struct Trienode
{
    Trienode *branch[LETTERS];
    EntryType *ref;
};

class TrieType
{

private:
    Trienode * root;

public:
    TrieType();
    ~TrieType();
    TrieType(TrieType &originalTree);
    void operator=(TrieType & originalTree);
    void MakeEmpty();
    void InsertTrie(Key newkey, EntryType *newentry);
    EntryType *  TrieSearch(Key target);
    bool DeleteTrie(Key delkey);
    void PrintTrie();
};

TrieType::TrieType()
{
    root = NULL;
}


TrieType::~TrieType()
{
    // destructor
}
TrieType::TrieType(TrieType &originalTree)
{
    // constructor
}

EntryType *TrieType::TrieSearch(Key target)
{
    int i;
    Trienode * current = root;
    for (i = 0; i < MAXLENGTH && current; i++)
    if (target[i] == '\0')
        break;
    else
        current =
        current->branch[target[i] - 'a'];
    if (!current)
        return NULL;
    else
    if (!current->ref)
        return NULL;

    return current->ref;
}


Trienode *CreateNode()
{
    int ch;
    Trienode *newnode = new Trienode;
    for (ch = 0; ch < LETTERS; ch++)
        newnode->branch[ch] = NULL;

    newnode->ref = NULL;

    return newnode;
}

void TrieType::InsertTrie(Key newkey, EntryType *newentry)
{
    int i;
    Trienode *current;
    if (!root)
        root = CreateNode();
    current = root;
    for (i = 0; i < MAXLENGTH; i++)
    if (newkey[i] == '\0')
        break;
    else
    {
        if (!current->branch[newkey[i] - 'a'])
            current->branch[newkey[i] - 'a'] = CreateNode();
        current = current->branch[newkey[i] - 'a'];
    }
    if (current->ref != NULL)
        cout << "\nTried to insert a duplicate key." << endl;
    else
        current->ref = newentry;
}

Solution

  • I know it is almost year passed after I post this question, but finally I found solution. Here it is....

    TrieType.h

    #include <iostream>
    #include <string>
    //added:###############################################
    #include<algorithm>
    #include<vector>
    //#####################################################
    #include "EntryType.h"
    
    
    const int LETTERS = 26;
    typedef char Key[MAXLENGTH];
    struct Trienode
    {
        Trienode *branch[LETTERS];
        EntryType *ref;
    };
    
    class TrieType
    {
    
    private:
        Trienode * root;
    
    public:
        TrieType();
        ~TrieType();
        TrieType(TrieType &originalTree);
        void operator=(TrieType & originalTree);
        void MakeEmpty();
        void InsertTrie(Key newkey, EntryType *newentry);
        EntryType *  TrieSearch(Key target);
        bool DeleteTrie(Key delkey);
        void PrintTrie();
    };
    
    TrieType::TrieType()
    {
        root = NULL;
    }
    
    
    TrieType::~TrieType()
    {
        // destructor
    }
    TrieType::TrieType(TrieType &originalTree)
    {
        // constructor
    }
    
    EntryType *TrieType::TrieSearch(Key target)
    {
        int i;
        Trienode * current = root;
        for (i = 0; i < MAXLENGTH && current; i++)
        if (target[i] == '\0')
            break;
        else
            current =
            current->branch[target[i] - 'a'];
        if (!current)
            return NULL;
        else
        if (!current->ref)
            return NULL;
    
        return current->ref;
    }
    
    
    Trienode *CreateNode()
    {
        int ch;
        Trienode *newnode = new Trienode;
        for (ch = 0; ch < LETTERS; ch++)
            newnode->branch[ch] = NULL;
    
        newnode->ref = NULL;
    
        return newnode;
    }
    
    void TrieType::InsertTrie(Key newkey, EntryType *newentry)
    {
        int i;
        Trienode *current;
        if (!root)
            root = CreateNode();
        current = root;
        for (i = 0; i < MAXLENGTH; i++)
        if (newkey[i] == '\0')
            break;
        else
        {
            if (!current->branch[newkey[i] - 'a'])
                current->branch[newkey[i] - 'a'] = CreateNode();
            current = current->branch[newkey[i] - 'a'];
        }
        if (current->ref != NULL)
            cout << "\nTried to insert a duplicate key." << endl;
        else
            current->ref = newentry;
    }
    
    //Added:################################################################33
    void Traverse(Trienode *current,vector<string> v)
    {
        if(current->ref != NULL)
        {
            //add the same prevous word as the new word, will remove char by char while moving upwards the tree to get into ne branch
            v.push_back(v[v.size()-1]);
            return;
        }
        for (int i = 0; i < LETTERS; i++)
        {
            if(current->branch[i] != NULL)
            {
                //each level contains childs as much as english letters in the same order(if any is null then the letter in this position is not used)
                v[v.size()-1] += (char)((int)'a' + i);
                current = current->branch[i];
                Traverse(current, v);
                //remove any additional chars from previous word to get new word from continuing from old word
                v[v.size()-1] =  v[v.size()-1].substr(0, v[v.size()-1].size()-1);
            }
        }
    }
    
    void TrieType::PrintTrie()
    {
        //temporarly saves the list of unsorted words
        vector<string> wordList;
        wordList.push_back("");
        Traverse(root, wordList );
        sort(wordList.begin(), wordList.end());
    
        for (int i = 0; i < wordList.size(); i++)
        {
            cout<<"Word "<<i<<": "<<wordList[i]<<endl;
        }
    }
    

    EntryType.h

    #include <iostream>
    using namespace std;
    
    const int MAXLENGTH = 10;
    class EntryType
    {
    public:
        EntryType();
        EntryType(char * key);
        EntryType(EntryType & entry);
        ~EntryType();
        bool operator== (const EntryType& item) const;
        bool operator!= (const EntryType& item) const;
        friend istream& operator>> (istream& is, EntryType& item);
        friend ostream& operator<< (ostream& os, EntryType item);
        void EntryKey(char word[]);
        void PrintWord();
    
    private:
        char entryKey[MAXLENGTH];
    };
    
    ostream& operator<< (ostream& os, EntryType item)
    {
        os << item.entryKey;
        return os;
    }
    
    EntryType::EntryType()
    {
        // empty instance constructor
    }
    EntryType::~EntryType()
    {
        // destructor
    }
    
    void EntryType::EntryKey(char word[])
    {
        for (int i = 0; i < 10; i++)
        {
            entryKey[i] = word[i];
        }
    }
    
    void EntryType::PrintWord()
    {
        cout << entryKey << endl;
    }
    

    main.cpp

    #include <iostream>
    #include <string>
    #include "TrieType.h"
    
    using namespace std;
    
    TrieType t;
    char newelem[10];
    
    void insert(TrieType & trie)
    {
        Key word;
        cout << "Enter the word you would like to insert into trie: " << endl;
        cin >> word;
    
        EntryType* newEntry = new EntryType;
        newEntry->EntryKey(word);
    
        trie.InsertTrie(word, newEntry);
        cout << "Word " << word <<" has been inserted into trie!"<< endl;
    }
    
    void getAllWords(TrieType & trie)
    {
        cout << "All words in trie are: " << endl;
    
        EntryType* newEntry = new EntryType;
        //newEntry->PrintWord();
        trie.PrintTrie();
    }
    
    int main()
    {
        int i;
    
        do
        {
            cout << "\nMENU\n-------------------- " << endl;
            cout << "1. Insert into a Trie" << endl;
            cout << "2. Search a Trie" << endl;
            cout << "3. Print Words Alphabetically" << endl;
            cout << "4. Exit" << endl;
            cout << "Please enter an integer value: ";
            cin >> i;
            switch (i)
            {
            case 1: 
                insert(t);
                break;
            case 2: 
                cout << "Enter string to search trie:";
                cin >> newelem;
                if (t.TrieSearch(newelem) != NULL)
                {
                    cout << "String " << newelem << " is member of trie!" << endl;
                }
                else
                {
                    cout << "String " << newelem << " is NOT member of trie!" << endl;
                }
                break;
            case 3:
                cout << "TO BE DONE!!!" << endl;
                t.PrintTrie();
                break;
            case 4:
                cout << "Exiting program..." << endl;
                break;
            default:
                cout << "Wrong input" << endl;
                break;
            }
    
        } while (i != 4);
        return 0;
    }
    

    I hope this will help somebody to figure out how to deal with these types of tree