面试刷题-前缀树(Trie)
Trie树,又称前缀树或字典树,是一种树形结构。典型应用是用于统计和排序大量的字符串,经常被搜索引擎系统用于文本词频统计或者自动联想搜索词等。
Trie有三个基本特征:
1)除根节点外,每一个节点都只包含一个字符;
2)从根节点到某一节点的路径上经过的字符连接起来,为该节点对应的字符串;
3)每个节点的所有子节点包含的字符都不相同。)
Trie树实现
Trie 树的结点结构
假设Trie树中存储的全部是英文字符串,英文最多有26个字母,所以TrieNode的next节点最多有26个。
TrieNode中并没有直接保存字符值,而是通过数[……]
Read More