数据结构与算法：字典树

本节目标：了解c语言和Python如何写前缀树

本节内容：前缀树

本节阅读需要（20）min。
本节实操需要（20）min。

文章目录

数据结构与算法：字典树
前言
一、C版本的前缀树
- 节点的创建。
- 查询
二、Python版本的前缀树
总结

前言

1. 技能的意义所在。
2. 内容中概念的提出

前缀树的本质其实是多分支多层次的字典。

一、C版本的前缀树

节点的创建。

public class TrieNode {int count;int prefix;TrieNode[] nextNode=new TrieNode[26];public TrieNode(){count=0;prefix=0;}
}

TrieNode[] nextNode=new TrieNode[26]为什么是26，很简单，因为26个英文字母。也就是说只有有限的26种后缀。
并且通过数列的位置去编号字母的。

查询

//插入一个新单词public static void insert(TrieNode root,String str){if(root==null||str.length()==0){return;}char[] c=str.toCharArray();for(int i=0;i<str.length();i++){//如果该分支不存在，创建一个新节点if(root.nextNode[c[i]-'a']==null){root.nextNode[c[i]-'a']=new TrieNode();}root=root.nextNode[c[i]-'a'];root.prefix++;//注意，应该加在后面}//以该节点结尾的单词数+1root.count++;}

//查找该单词是否存在，如果存在返回数量，不存在返回-1public static int search(TrieNode root,String str){if(root==null||str.length()==0){return -1;}char[] c=str.toCharArray();for(int i=0;i<str.length();i++){//如果该分支不存在，表名该单词不存在if(root.nextNode[c[i]-'a']==null){return -1;}//如果存在，则继续向下遍历root=root.nextNode[c[i]-'a'];	}//如果count==0,也说明该单词不存在if(root.count==0){return -1;}return root.count;}//查询以str为前缀的单词数量public static int searchPrefix(TrieNode root,String str){if(root==null||str.length()==0){return -1;}char[] c=str.toCharArray();for(int i=0;i<str.length();i++){//如果该分支不存在，表名该单词不存在if(root.nextNode[c[i]-'a']==null){return -1;}//如果存在，则继续向下遍历root=root.nextNode[c[i]-'a'];	}return root.prefix;}

注意这里有两个数量。
一个是到这个节点为止的前缀字符串的数量。
一个是以这个节点为止的前缀的完整单词的数量。

二、Python版本的前缀树

class TreeNode(object):def __init__(self):self.nodes = {}         # 记录当前结点的子结点self.is_leaf = False   # 当前结点是否表示一个单词self.count = 0          # 单词树中单词的总量def insert(self,word):curr = selffor c in word:if not curr.nodes.get(c,None):new_node = TreeNode()curr.nodes[c] = new_nodecurr = curr.nodes[c]curr.is_leaf = Trueself.count += 1returndef insert_many(self,words):for word in words:self.insert(word)returndef search(self,word):curr = selftry:for c in word:curr = curr.nodes[c]except:return Falsereturn curr.is_leaf