字典树

什么是字典树

Trie 树（又叫“前缀树”或“字典树”）是一种用于快速查询“某个字符串/字符前缀”是否存在的数据结构。

• 根节点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符；
• 从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串；
• 任意节点的所有子节点所包含的字符都不相同；