如何通过代码实现Tire树图解？

本文共计1921个文字，预计阅读时间需要8分钟。

Trie树，又称前缀树或字典树，是一种有序树形数据结构。它专门用于处理字符串匹配，可以快速查找字符串中是否存在某个子串。Google搜索的关键字提示实现原理就是基于Trie树。

Trie又称为前缀树或字典树，是一种有序树，它是一种专门用来处理串匹配的数据结构，用来解决一组字符中快速查找某个字符串的问题。Google搜索的关键字提示实现原理就是基于Tire树。 简介

  Trie又称为前缀树或字典树，是一种有序树，它是一种专门用来处理串匹配的数据结构，用来解决一组字符中快速查找某个字符串的问题。Google搜索的关键字提示功能相信大家都不陌生，我们在输入框中进行搜索的时候，会下拉出一系列候选关键词。

  上面这个关键词提示功能，底层最基本的原理就是我们今天说的数据结构：Trie树
  我们先看看Tire树长什么样子，以单纯的单词匹配为例，首先它是一棵多叉树结构，根节点是一个空字符，树中节点分为普通节点和结尾节点（如图中红色节点）。结尾节点表示加上前面前缀，可以称为一个单词，如图中hi，him。

工作过程

​ Tire树与之前串匹配最大的不同点是，之前我们都是单模式串，查看主串中是否有与模式串匹配的子串，操作过程也是用模式串去与主串进行比较。而Tire树是多模式串，我们先将模式串提前构建成Tire树，然后查看主串是否匹配模式串，且更适用于类似如上关键词提示的前缀匹配。接下来我们自己通过实现一个简易的关键词提示功能来讲解Tire树。