Trie

要点：

1）Trie树的意义；

2）TrieNode --- map<char, trienode*>

3）Trie树三大操作：insert，findWord, findPrefix；

4）Trie树不能删除；

5）Trie树与Hash表的优劣；

class TrieNode {
public:
    char c;
    bool isword;
    string str;
    map<char, TrieNode*> hash;
    // Initialize your data structure here.
    TrieNode(char c) 
    {
        this->c = c;
        this->isword = false;
    }
    TrieNode() 
    {
        this->isword = false;
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode* p = root;
        for(int i = 0; i<word.length(); i++)
        {
            if(p->hash.find(word[i]) == p->hash.end())
            {
                TrieNode* newnode = new TrieNode(word[i]);
                p->hash[word[i]] = newnode;
                p = newnode;
            }
            else
            {
                p = p->hash[word[i]];
            }

            if(i == word.length()-1)
            {
                p->isword = true;
                p->str = word;
            }
        }
    }
public:
    TrieNode* root;
};