写给小白的字典树介绍

在搜索引擎中输入app，查找以app为前缀的英文单词，你会想到什么数据结构呢？ Trie树，就是用来解决这样的问题。

这是力扣上Top100的一道题目，实现Trie树。 Trie树又称字典树 ，前缀树，本质上是一颗多叉树。在实际中的应用场景可以是单词匹配，例如输入app查找出以app为前缀的英文单词。

什么是字典树

在这道题目中，我们可以根据输入构造出一颗Trie树以便于后续的单词查找。

Trie树的结构如下，其中每个节点最多有26个子节点。

除根节点外的节点需要表示：

• 是否为单词的结尾
• 当前节点代表的字母
• 指向单词的下一个字母节点

当我们想要查找是否有app这个单词，查找顺序为：

• 从根节点出发，查找根节点是否有含有a的子节点；
• 有则继续查找a的子节点是否含有p的节点；
• 有则继续查找p的子节点是否含有p的节点；
• 我们发现最后一个单词p在树中并不是单词的最后一个字母，因此说明字典树中没有app这个单词。

同理，当我们想要查找是否有apple这个单词，由于最后一个单词e在树中是单词的最后一个字母，因此说明字典树有apple这个单词，查找成功。

Trie树的插入

我们用以下结构代表一个节点：

    class Node:
        def __init__(self):
            self.isEndOfWord = False  # 是否为单词的结尾,True表示为单词结尾
            self.childrenNodes = {}   # {key为代表的字母: value为后续子节点}

比如插入like这个单词, 我们查找子节点字典childrenNodes可以获取到根节点对应的子节点 l 已经存在，继续插入后续字母，当字母对应的节点不存在时则插入对应的子节点，当插入完最后一个单词时，标记最后一个单词isEndOfWord 的为true，代表单词结束。

 def insert(self, word: str) -> None:
        if not word:
            return
        node =  self.rootNode
        for ch in word:
            if not node.childrenNodes.get(ch):
                node.childrenNodes[ch] = Node()     
            node = node.childrenNodes[ch]
        node.isEndOfWord = True     # 假设存在apple 和 app, 则分别在p和e 的节点isEndOfWord标志都是true

此时的Trie树如下

说明： 当插入的是app这个单词时，由于前面已经有插入过apple这个单词，因此实际上这次插入只需要将对应p这个节点的标志置为True。

查找单词

遍历单词字母，如果查找中间有字母不存在，则返回False, 如果最后一个单词标识也是False，则说明Trie树中的单词未结束，说明查找的单词不存在。

例如在以下Trie树中查找app这个单词, 则查找失败。

查找前缀

查找前缀则不需要判断标识，即只要前缀中的字母都存在，则查找成功。

最终代码如下

python

class Node:
    def __init__(self):
        self.isEndOfWord = False
        self.childrenNodes = {}   # {'a':NextNode}

class Trie:

    def __init__(self):
        self.rootNode = Node()

    def insert(self, word: str) -> None:
        if not word:
            return
        node =  self.rootNode
        for i, ch in enumerate(word):
            if not node.childrenNodes.get(ch):
                node.childrenNodes[ch] = Node()     
            node = node.childrenNodes[ch]
        node.isEndOfWord = True     

    def search(self, word: str) -> bool:  # 查找单词
        node =  self.rootNode
        for ch in word:
            if not node.childrenNodes.get(ch):
                return False
            node = node.childrenNodes[ch]
        return True if node.isEndOfWord == True else False 

    def startsWith(self, prefix: str) -> bool:  # 查找前缀
        node =  self.rootNode
        for ch in prefix:
            if not node.childrenNodes.get(ch):
                return False
            node = node.childrenNodes[ch]
        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

C++

const int CHILDREN_SIZE = 26;

class TrieNode{
    public:
        bool isEndOfWord;
        vector<TrieNode*> children;

        TrieNode(){
            isEndOfWord = false;
            children = vector<TrieNode*>(CHILDREN_SIZE, nullptr);
        }

        ~TrieNode() {
             for(int i = 0; i < CHILDREN_SIZE;i++){
                 if(children[i] != nullptr){
                     delete children[i];
                 }
             }
         }
};

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

    void insert(string word) {
        TrieNode *node = root;
        for(char c :word){
            int index = c - 'a';
            if(node->children[index] == nullptr)
            {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEndOfWord = true;

    }
    
    bool search(string word) {
        TrieNode *node = root;
        for(char c : word){
            int index = c - 'a';
            if(node->children[index] == nullptr){
                return false;
            }
            node = node->children[index];
        }
        
        return node != nullptr && node->isEndOfWord;
    }
    
    bool startsWith(string prefix) {
        TrieNode *node = root;
        for(char c : prefix){
            int index = c - 'a';
            if(node->children[index] == nullptr){
                return false;
            }
            node = node->children[index];
        }
        
        return node != nullptr;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

喜欢的话就点个赞吧~