字典树又称单词查找树，Trie树，适用于统计、排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本检索和词频统计。它利用字符串的公共前缀最大限度地减少无谓的字符串比较，查询效率较高。其具有以下特点：
(1)根节点不包含字符，除根节点外每个节点都只包含一个字符。
(2)从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的键字符串。
(3)每个节点的所有子节点包含的字符都不相同。
字典树可以简单理解为一种用于快速检索的多叉树结构，如小写英文字母的字典树是一个26叉树，数字的字典树是一个10叉树，如下图所示。
字典树的存入
字典树是一个多叉树结构，它的下级指针是一个集合。一个字符串首先被分解成多个字符，然后依次存人字典树。字典树中的每层存储字符串中的1个字符，第1层存第1个，第2层存第2个，以此类推。每层中的下级指针集合可以是一个数组、链表或二叉树等结构。
字典树构成的算法逻辑：一个字符串在存入字典树之前，首先要分解成一串字符列表，然后把每个字符依次放入字典树的相应位置上。字典树中插入新键值的算法图解如下图所示。
实际上字典树的下级指针集合并不像图示那么少，逐个比较查找显然是不行的，因此下级指针集合一般用二叉树、堆和快速排序数组等速查集合，加快字典树的查找速度。如果字典树每个节点的下级指针集合采用二叉排序树方式实现，那么每个节点实际只需一个下级指针指向这个二叉树的根节点，一个连接实现多叉。如下图所示。
字典树的遍历
字典树显然不能和其他树一样遍历，每个节点的下级集合采用中序遍历，一个节点的下级集合遍历后询问遍历它的下级那个节点，然后再递归遍历它。
程序代码：
运行结果：
练习１：把h和k开头的50个单词输入上例中再遍历看看如何？
练习２：把节点的值作为出现次数，统计下面一段英语的单词出现次数。例题原码在附录１中，复制修改完成这个练习。
john escott has written many books for readers of all ages and particularly enjoys writing crime and mystery thrillers he was born in the west of england but now lives on the south coast when he is not writing he visits second-hand bookshops watches videos of old hollywood movies and takes long walks along empty beaches he has written kidnap a pretty face and retold william tell and other stories and white fang
学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：
Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。
更多课程请打开“学思营”同步网站：
http://www.5xstar.com/doc.html
参考资料：
１、《Python算法图解》何韬编著 清华大学出版社
附录１：
#字典树插入
#（１）字典树节点类
class TrieNode: #多叉树和二茬树的节点
def __init__(self,char=None):
self.char = char #节点字符
self.value = None #节点值
self.pointers = SortTree() #下级节点指针集合（二叉树）
#下级节点集合中用二叉树快速查找
self.left = None #左指针
self.right = None #右指针
def addChar(self,char): #在下级记得集合中查找或创建字典树节点
tnode = self.pointers.add(char)
return tnode
def display(self,lst): #中序遍历方法
if self.left!=None: #如果左指针不为空
self.left.display(lst) #递归调用左节点遍历
lst.append(self) #节点本身
if self.right!=None: #如果右指针不为空
self.right.display(lst) #递归调用右节点遍历
#（２）节点中下级指针集合类（二叉搜索树结构）
class SortTree:
def __init__(self):
self.root = None
self.length = 0 #节点数
def add(self,char): #在节点下级指针集合中添加节点
if self.root!=None:
node = self.root
while True:
if char<node.char: #如果传入的字符值小于节点本身的字符值
if node.left!=None: #如果左指针不为空，往下循环
node = node.left
else: #如果左指针为空，加上新节点
node.left = TrieNode(char)
node = node.left
self.length += 1
break
elif char>node.char: #如果传入字符大于节点本身字符值
if node.right!=None: #如果右指针不为空，循环往下
node = node.right
else: #如果右指针为空，直接加上新字符节点
node.right = TrieNode(char)
node = node.right
self.length += 1
break
else: #如果传入字符与节点本身字符相等，此字符节点已找到
break
else: #添加根节点，也就是上级节点的第一个下级节点
node = TrieNode(char)
self.root = node
self.length += 1
return node
def display(self): #中序遍历
lst = []
self.root.display(lst)
return lst
#（３）字典树类
class TrieTree:
def __init__(self):
self.root = TrieNode() #根节点是无字符的
def put(self,key,value): #压入键值对
slist = list(key) #把键分解为字符列表
tnode = self.root #从根节点开始
key = ''
for char in slist: #把键中字符逐个取出
key = "%s%s"%(key,char) #组合路径
print(key) #打印路径
tnode = tnode.addChar(char) #把字符逐个插入字典树中
tnode.value = value #把值保存在最后路径中
def display(self): #遍历
key = ""
self.__display(self.root, key)
def __display(self, node, key): #递归遍历
key += "" if node.char == None else node.char #组合关键词
print("上级键:", key, "值:", node.value) #打印上级节点
if node.pointers.length > 0: #下级指针集合中有记录
lst = node.pointers.display() #获取下级集合
dlen = len(lst)
print("序号\t键\t值\t下级集合")
for i in range(dlen):
nd = lst[i]
dw = "有" if nd.pointers.length > 0 else "无" #是否有下级集合
print("%d\t%s\t%s\t%s" % (i,key+nd.char,str(nd.value),dw)) #打印一行
dnum = input("请输入下级序号：")
if dnum != None and dnum != "":
dnum = int(dnum)
if dnum>-1 and dnum < dlen:
self.__display(lst[dnum], key)
#（４）测试
if __name__ == "__main__":
trieTree = TrieTree()
trieTree.put('house','房子')
trieTree.put('horse','马')
trieTree.display()