Trie的定义

Trie（发音为“try”），又名前缀树或字典树，是一种有序树，是一种专门处理字符串匹配的数据结构。它的优势在于，查询某个字符串是否为某个文本串的子串时，只需要进行一次遍历，就可以得到结果。

Trie的实现原理

Trie树是一种多叉树，其每个节点有多个子节点，每个节点都有一个字符，这个字符指的是从根结点到该节点组成的字符串。Trie树的根结点不包含字符，除根结点外每一个节点都只包含一个字符。每个节点的所有子节点包含的字符都不相同。

Trie的实现方法

Trie树的实现一般是用数组或者链表实现，用数组实现Trie树，每个节点的孩子节点用一个长度为26的数组来表示，其中每个元素代表一个字符，数组的下标代表字符的顺序，比如字符'a'对应下标0，字符'b'对应下标1，以此类推。

Trie的实现代码

class TrieNode:
def __init__(self):
self.children = [None] * 26
self.isEndOfWord = False

class Trie:
def __init__(self):
self.root = self.getNode()

def getNode(self):
return TrieNode()

def _charToIndex(self,ch):
return ord(ch) - ord('a')

def insert(self,key):
pCrawl = self.root
length = len(key)
for level in range(length):
index = self._charToIndex(key[level])
if not pCrawl.children[index]:
pCrawl.children[index] = self.getNode()
pCrawl = pCrawl.children[index]
pCrawl.isEndOfWord = True

def search(self, key):
pCrawl = self.root
length = len(key)
for level in range(length):
index = self._charToIndex(key[level])
if not pCrawl.children[index]:
return False
pCrawl = pCrawl.children[index]
return pCrawl != None and pCrawl.isEndOfWord