Java 数据结构与算法中的字典树你学会了吗？

​一、前言

Trie 的历史

字典树 Trie 这个词来自于 retrieval，于 1912 年，Axel Thue 首次抽象地描述了一组字符串数据结构的存放方式为 Trie 的想法。这个想法于 1960 年由 Edward Fredkin 独立描述，并创造了 Trie 一词。你看看，多少程序员为了一个词、方法名、属性名，想破脑袋！

二、字典树数据结构

在计算机科学中，字典树(Trie)也被称为”单词查找树“或”数字树“，有时候也被称为基数树或前缀树（因为可以通过前缀的方式进行索引）。—— 它是一种搜索树，一种已排序的数据结构，通常用于存储动态集或键为字符串的关联数组。

与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

• 这是一个把 battle 单词字符串，按照字母拆分到字典树进行存放的图。
• 键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。也就是26个字母对应的 ASCII 转换后的值。

三、字典树结构实现

字典树字母的存放有26个，也就是说在实现的过程中，每一个节点的分支都有26个槽位用来存放可能出现的字母组合。同理如果是数字树的话就是10个数字的组合，每个字典树上的节点对应的分支则有10个操作存放可能