欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Trie树的C++实现

程序员文章站 2022-09-28 15:51:13
先给出LintCode的题目:实现Trie树 Trie树就是字典树,用在搜索引擎如百度搜索词条,还比如说之前DNS域名解析系统搜索根据域名搜索IP。总之,是棵树,根据字符串搜索某...

先给出LintCode的题目:实现Trie树

Trie树就是字典树,用在搜索引擎如百度搜索词条,还比如说之前DNS域名解析系统搜索根据域名搜索IP。总之,是棵树,根据字符串搜索某一节点,同时就可获得节点存储的信息了。

Trie树的一般性质如下:

1.根节点不包含字符,除根节点外每一个节点都只包含一个字符。

2.从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。

3.每个节点的所有子节点包含的字符都不相同。

那么既然是树,既然需要和字符串匹配,那么树的节点怎么定义?我们可以这样分析,插入一个字符串“ABCD”时我们一个一个插,且A->B->C->D,我们的节点必须要包含A等字符信息,在查找时好一一匹配。同时我们要有结束符来表示字符串末尾,这是为了ABCD和ABCDE区别开来。

实现代码如下,LintCode通过率为70%,不知道哪里有问题。

 

/**
 * Your Trie object will be instantiated and called as such:
 * Trie trie;
 * trie.insert("lintcode");
 * trie.search("lint"); will return false
 * trie.startsWith("lint"); will return true
 */
 #define MAX_CHILD 26
class TrieNode {
public:
    // Initialize your data structure here.
    int count;
    TrieNode *child[MAX_CHILD];
    TrieNode() {
      count=0;
    }
};

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

    // Inserts a word into the trie.
    void insert(string word) {
        if(root==NULL||word.size()==0)
        return;
        int n=word.size();
        int i=0;
        TrieNode *t=root;
        while(ichild[word[i]-'a']==NULL)
            {
                TrieNode *tmp=new TrieNode();
                t->child[word[i]-'a']=tmp;
                t=t->child[word[i]-'a'];
            }
            else
            t=t->child[word[i]-'a'];
            i++;
        }
        t->count=1;
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        if(root==NULL||word.size()==0)
        return false;
        TrieNode *t=root;
        int n=word.size();
        int i=0;
        while(ichild[word[i]-'a']==NULL)
            return false;
            else
            {
                t=t->child[word[i]-'a'];
            }
            i++;
        }
        if((i==n)&&(t->count==1))return true;
        return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        if(root==NULL||prefix.size()==0)return false;
        int n=prefix.size();
        TrieNode *t=root;
        int i=0;
        while(ichild[prefix[i]-'a']==NULL)
            return false;
            else
            {
                t=t->child[prefix[i]-'a'];
            }
            i++;
        }
       return true;
    }

private:
    TrieNode* root;
};


 

还有一种节点数据结构的方法,就是结构体换成map和bool isLeaf两个成员变量。思想一样,也可以这样来实现。,trienode*>

重点在插入时,顺着某一节点不断插入。上述用TrieNode*数组作为当前节点的成员变量,实则指向下一个节点,因为TrieNode*存放的是下一节点的值,数组下标表示边值。因为字母仅有26,所以数组大小可以声明为26.

map的实现机制是一样的,键保存字符,值表示下一节点的值。