字典树Trie：字符串的高效存储

字典树Trie：字符串的高效存储搜索引擎的自动补全、输入法的联想词、拼写检查……这些功能的背后，都有一种叫 Trie（字典树）的数据结构。一、什么是字典树？Trie（也叫前缀树、字典树）是一种专门处理字符串的树形结构。它的核心思想：用树的路径表示字符串的前缀。root / | \ a b c /| \ \ p t u a | | | | p p t t | | | l e | | | (end) (end)这棵树存了这些单词：app, apple（假设延伸下去）, but, cat查找 “app”：从根出发，找 ‘a’ 分支 → 存在找 ‘p’ 分支 → 存在找 ‘p’ 分支 → 存在标记为单词结尾 → "app"在树中！二、Trie 的特点根节点为空，不存字符每个