Implement Trie

文章目录

1. Implement Trie

问题是让我们实现一个字典树（Trie），那么什么是字典树呢？就是根据输入的字符串的前缀来构建树，比如输入是”aba”,”abc”，那么从树的根节点出发（根节点什么也没有，从它出发可以访问所有一个字符的节点），两个字符串共享节点a。接着节点a出发，可以访问节点b，从节点b出发，分别可以访问节点a和节点c。

这样看字典树的其中一层就是字符串的第几个字符。这样储存字符串的好处就是节省了空间，因为可以将相同的字符串前缀储存在一起。

那我是如何实现字典树的呢？首先会有一个节点结构TrieNode来实现字典树中每个节点的情况。字典树和二叉树不同，字典树可以有26个子节点（只考虑小写），二叉树只有左右子节点。所以TrieNode下会有个TrieNode的二维指针来储存它所有的子节点。我们还需要设计一个变量来记录从根节点到当前节点是否已经存在字符串了，比如”aba”，在构建的时候如果没有这个变量的话，我们就不知道到底a在不在字典中，ab在不在字典中。

字典树还要实现插入和查找的操作。插入的操作只需要从根节点出发，访问第str[i]-‘a’的TrieNode*变量即可。查找需要使用我们再创建TrieNode结构时设计的变量。