提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

提示：这里可以添加本文要记录的大概内容：

例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、前缀树是什么？

1.定义

含义：前缀树的一个节点代表一个前缀（一个字符串），一个边代表一个字符，根节点代表空字符串
特点：节点所有的后代都与该节点相关的字符串有着共同的前缀

2.实现

a .数组

节点只表达a-z的26个字母时，可以声明一个大小为26的数组存储子节点，用 某字符 - ‘a’ 来确定索引（ascii）

#define N 26struct TrieNode {TrieNode* children[N];
};

这种方式的优势是查找比较快，劣势是空间浪费（长度为26的数组其实只用了一个）

b.hashmap

在每个节点声明一个Hashmap，键是字符，值是对应的字节点
有时是节省空间，但可能会稍慢一些

二、例题-添加与搜索单词（数据结构设计）

1.题目

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。

示例：

输入：
[“WordDictionary”,“addWord”,“addWord”,“addWord”,“search”,“search”,“search”,“search”]
[[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b…”]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord(“bad”);
wordDictionary.addWord(“dad”);
wordDictionary.addWord(“mad”);
wordDictionary.search(“pad”); // 返回 False
wordDictionary.search(“bad”); // 返回 True
wordDictionary.search(“.ad”); // 返回 True
wordDictionary.search(“b…”); // 返回 True

2.思路

结合前缀树和dfs，对于确定的字母，直接查找，对于“.”，先序遍历所有孩子节点
前缀树用数组方式实现

3.代码

class WordDictionary {//根节点private Trie root;//构造函数public WordDictionary() {//根节点是一个Trie树节点root = new Trie();}//插入单词直接用Trie的insert方法即可public void addWord(String word) {root.insert(word);}//dfs深度优先遍历查找单词是否存在public boolean search(String word) {return dfs(word, 0, root) ; //单词的第一个字符（索引 0） 开始，递归地遍历以 root 为起点的 Trie 树}private boolean dfs(String word, int index, Trie node){if (index == word.length()){return node.isEnd();}//获取当前字符char ch = word.charAt(index);//判断当前字符是字母还是.if(Character.isLetter(ch)){int childIndex = ch - 'a';Trie children = node.getChildren()[childIndex];if(children != null && dfs(word, index + 1, children)){return true;}}else{for(int i = 0; i < 26; i++){Trie children = node.getChildren()[i];if(children != null && dfs(word, index + 1, children)){return true;}}}return false;}
}// 前缀树
class Trie{private Trie[] children ; //当前节点的孩子private boolean isEnd ; //当前节点是否是单词结尾//构造函数public Trie(){children = new Trie[26];isEnd = false;}//插入单词的函数，参数是单词，没有返回值//String类的charAt函数返回字符串中指定索引位置的字母public void insert(String word){Trie node = this;for(int i = 0; i < word.length(); i++){char ch = word.charAt(i); //获取当前索引的字符int index = ch - 'a' ; //获取字符对应的孩子数组的下标//如果对应位置是空，造一个节点，如果不是空，则不用操作，复用即可if(node.children[index] == null){node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}//公共的获取当前成员变量的接口，因为成员变量是私有的public Trie[] getChildren(){return children;}public boolean isEnd(){return isEnd;}
}