字典树 {#menu_index_1}

定义 {#toc_0}

字典树，顾名思义，是关于"字典"的一棵树。即：它是对于字典的一种存储方式（所以是一种数据结构而不是算法）。这个词典中的每个"单词"就是从根节点出发一直到某一个目标节点的路径，路径中每条边的字母连起来就是一个单词。

结构实例 {#toc_1}

trie1

字典树的功能 {#toc_2}

根据字典树的概念，我们可以发现：字典树的本质是把很多字符串拆成单个字符的形式，以树的方式存储起来。所以我们说字典树维护的是"字典"。那么根据这个最基本的性质，我们可以由此延伸出字典树的很多妙用。简单总结起来大体如下：

1、维护字符串集合（即字典）。
2、向字符串集合中插入字符串（即建树）。
3、查询字符串集合中是否有某个字符串（即查询）。
4、统计字符串在集合中出现的个数（即统计）。
5、将字符串集合按字典序排序（即字典序排序）。
6、求集合内两个字符串的LCP（Longest Common Prefix，最长公共前缀）（即求最长公共前缀）。

我们可以发现，以上列举出的功能都是建立在"字符串集合"的基础上的。再一次强调，字典树是"字典"的树，一切功能都是"字典"的功能。这也为我们使用字典树的时候提供了一个准则：看到一大堆字符串同时出现，就往哈希和Trie树那边想一下。

基于字典树实现的域名匹配 {#toc_3}

有一个需求，给出一个域名名单，当输入一个新域名之后判断其是否存在域名名单中，要求支持通配符匹配

代码实现 {#toc_4}

根据字典树结构，使用go语言实现如下：

package main

import (
"fmt"
"github.com/gookit/goutil/arrutil"
"github.com/gookit/goutil/maputil"
"strings"
)


type TrieNode struct {
children map\[string\]\*TrieNode
isEnd    bool
}


type Trie struct {
root \*TrieNode
}


func initTrie() \*Trie {
return \&Trie{root: \&TrieNode{children: make(map\[string\]\*TrieNode)}}
}


func (t \*Trie) insertDomain(domain string) {
parts := strings.Split(domain, ".")
arrutil.Reverse(parts)
node := t.root


    for _, part := range parts {
        if node.children[part] == nil {
            node.children[part] = &amp;TrieNode{children: make(map[string]*TrieNode)}
        }
        node = node.children[part]
    }

    node.isEnd = true




}


func (t \*Trie) searchDomain(domain string) bool {
parts := strings.Split(domain, ".")
arrutil.Reverse(parts)
node := t.root


    for _, part := range parts {
        isNil := node.children[part] == nil
        if isNil &amp;&amp; !maputil.HasKey(node.children, "*") {
            return false
        }
        if isNil {
            node = node.children["*"]
        } else {
            node = node.children[part]
        }
    }

    return node != nil &amp;&amp; node.isEnd




}


func main() {
trie := initTrie()


    // 示例域名
    domains := []string{"wx.*.com", "example.com", "test.org"}

    // 插入域名到 Trie 中
    for _, domain := range domains {
        trie.insertDomain(domain)
    }

    // 搜索示例
    searchDomains := []string{"wx.qq.com", "openai.com", "test.org", "wx.qq1.com"}

    // 搜索域名是否存在于 Trie 中
    for _, domain := range searchDomains {
        if trie.searchDomain(domain) {
            fmt.Printf("%s 存在\n", domain)
        } else {
            fmt.Printf("%s 不存在\n", domain)
        }
    }



`}`