前言：
由于网上对Trie树的定义有更全面的讲解，这里不展开详细描述。
这里采用c#与golang语言实现。
特点：
- 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
- 从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
优缺点：空间换时间。
使用场景
字符串查找，词频统计，智能提示，敏感词过滤等。这里采用go和c#实现查找
字符串查找
GO版
type Node struct {
Val rune
Depth int
Count int // 统计分支数量
Child map[rune]*Node
IsWord bool // 标记是否为一个完整的字符串
}
// 创建节点
func NewNode() *Node {
return &Node{Child: make(map[rune]*Node)}
}
type Trie struct {
Root *Node
}
func NewTrie() *Trie {
return &Trie{Root: NewNode()}
}
// 添加节点
func (t *Trie) Insert(str string) {
if len(str) == 0 {
return
}
bt := []rune(str)
node := t.Root
for _, val := range bt {
child, ok := node.Child[val]
if !ok {
child = NewNode()
child.Val = val
node.Child[val] = child
node.Count += 1
child.Depth = node.Depth + 1
}
node = child
}
node.IsWord = true
}
func (t *Trie) Find(str string) bool {
bt := []rune(str)
node := t.Root
for _, val := range bt {
child, ok := node.Child[val]
if !ok {
return false
}
node = child
}
return node.IsWord
}
// 节点的删除分为如下种情况
// 1. 前缀的删除：判断Count是否大于0， 标记IsWord 为false。
// 3. 字符串的删除：
// a. 如果是无分支，则整个删除。
// b. 如果有分支，仅删除不是共有前缀的部分。
func (t *Trie) Del(str string) {
bt := []rune(str)
if len(str) == 0 {
return
}
node := t.Root
var lastBranch *Node
var delVal rune
for index, val := range bt {
child, ok := node.Child[val]
if ok {
if child.Count > 1 {
lastBranch = child
delVal = bt[index+1]
}
}
node = child
}
if node.Count > 0 {
// 删除前缀
node.IsWord = false
} else {
if lastBranch == nil {
// 删除整个字符串
lastBranch = t.Root
delVal = bt[0]
}
delete(lastBranch.Child, delVal)
lastBranch.Count -= 1
}
}
调用
func main(){
trie:=NewTrie()
// 添加
trie.Insert("你好，哈哈")
trie.Insert("你好")
trie.Insert("你好，事事顺遂")
// 搜索
a := trie.Find("你好，哈哈")
fmt.Println(a)
// 删除
trie.Del("你好，哈哈")
a = trie.Find("你好，哈哈")
fmt.Println(a)
}
C#版
-
创建节点
public class Node { public char Val { get; set; } public Dictionary<char, Node> Child { get; set; } public bool IsWord { get; set; } } -
创建根节点以及相关操作方法
public class Trie { public Node Root { get; set; } public Trie() { Root = new Node(); } // 添加节点 public void Insert(string str) { var bt = str.ToCharArray(); var node = Root; foreach (var item in bt) { Node child; if (!node.Child.ContainsKey(item)) { child = new Node(); child.Val = item; node.Child.Add(item, child); } else { child = node.Child[item]; } node = child; } node.IsWord = true; } // 前缀查找 public bool SearchWithStart(string str) { var bt = str.ToCharArray(); var node = Root; foreach (var item in bt) { if (node.Child.ContainsKey(item)) { node = node.Child[item]; } else { return false; } } return node.IsWord; } // 删除 public void Del(string str) { var bt = str.ToCharArray(); var node = Root; Node lastBranch = null; Node child = null; char delVar = default; for (int i = 0; i < bt.Length; i++) { if (node.Child.ContainsKey(bt[i])) { child = node.Child[bt[i]]; if (child.Child.Count > 1) { lastBranch = child; delVar = bt[i + 1]; } node = child; } else { return; } } if (node.Child.Count > 0) { node.IsWord = false; } else { if (lastBranch == null) { lastBranch = Root; delVar = bt[0]; } lastBranch.Child.Remove(delVar); } } }
3.调用
class Program
{
static void Main(string[] args)
{
var str1 = "你好";
var str2 = "你好，世界";
var str3 = "你好，事事开心";
var str4 = "测试数据";
var trie = new Trie();
// 添加字符串
trie.Insert(str1);
trie.Insert(str2);
trie.Insert(str3);
trie.Insert(str4);
// 查找
var result = trie.SearchWithStart(str2);
Console.WriteLine(result);
// 删除
trie.Del(str2);
result = trie.SearchWithStart(str2);
Console.WriteLine(result);
}
}
