在leecode上面208便是前缀树这个题目，可以看一下。
下面这个图片便是关于前缀树的描述和查找字符的过程。
前缀树的实现
实现前缀树，首先想到的便是创建树和节点，个中子节点利用了map的数据构造存储，节省了遍历，适宜手写代码实现的。这个也是看到leecode上面修正的，刚开始利用切片进行遍历实现的。
type Node struct {isEnd boolChildren map[string]Node // 这里也可以利用切片，进行遍历}type Tree struct {root Node}func NewTree() Tree {return &Tree{root: &Node{Children: make(map[string]Node)},}}
有了树和节点之后，我们不雅观察一下上面图片，就会有想到须要两个方法。一个是增加节点一个是查询字符串是否存在的方法。
新增和判断节点的时候，紧张一下当前字符是否末了一位。如果存入的是 gin，那么查找gi也是不存在的。
func (t Tree) AddStr(str string) {// 添加一个新的字符，那么首先判断一下是否已经存在node := t.root// 遍历字符串for _, b := range str {s := string(b)if _, ex := node.Children[s]; !ex {// 不存在插入空节点node.Children[s] = &Node{Children: make(map[string]Node)}}node = node.Children[s]}node.isEnd = true // 标记末了一位}func (t Tree) SearchStr(str string) bool {node := t.root// 查找便是遍历判断，末了还要判断一下是否末了一位for _, b := range str {s := string(b)if _, ex := node.Children[s]; !ex {return false}node = node.Children[s]}return node.isEnd}
这个便是大略实现前缀树的代码了，可以测试一下看看
func main() {t := NewTree()t.AddStr("gin")t.AddStr("gins")fmt.Println(t.SearchStr("g"))fmt.Println(t.SearchStr("gin"))fmt.Println(t.SearchStr("ginss"))}gin利用的前缀树
压缩前缀树又称基数树或 radix 树，是对前缀树的改良版本，优化点紧张在于空间的节省，核心策略表示在：
倘若某个子节点是其父节点的唯一孩子，则与父节点进行合并。
在 gin 框架中，利用的正是压缩前缀树的数据构造.
