Trie树，也叫字典树、前缀树。可用于”predictive text”和”autocompletion”，亦可用于统计词频（边插入Trie树边更新或添加词频）。

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 这个术语来自于 retrieval。根据词源学，trie 的发明者 Edward Fredkin 把它读作 英语发音：/?tri?/ "tree"。^[1][2] 但是，其他作者把它读作 英语发音：/?tra?/ "try"。^[1][2][3]

在图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。

键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示 trie 的原理。

trie 中的键通常是字符串，但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie 中的键是一串位元，可以用于表示整数或者内存地址。

参考资料：http://zh.wikipedia.org/wiki/Trie

#!/usr/bin/python                                                                                                                                                      
# -*- coding:utf-8 -*-
# * trie, prefix tree
# * author: yangxudongsuda@gmail.com
import sys 
reload(sys)
sys.setdefaultencoding("utf-8")

class Node:
  def __init__(self):
    self.value = http://www.mamicode.com/None>
运行结果如下：
1
4
None
None
1
2
soho
soho 尚都
3
90
('soho \xe5\xb0\x9a\xe9\x83\xbd', 3)
============== keys =================
prefix "sm":  sm | sm 新生活 广场 | sm 城市广场 | sm 广场 | sm 购物 广场 | sm 国际 广场
============== items =================
prefix "sm":  [('sm', 1), ('sm \xe6\x96\xb0\xe7\x94\x9f\xe6\xb4\xbb \xe5\xb9\xbf\xe5\x9c\xba', 5), ('sm \xe5\x9f\x8e\xe5\xb8\x82\xe5\xb9\xbf\xe5\x9c\xba', 3), ('sm \xe5\xb9\xbf\xe5\x9c\xba', 4), ('sm \xe8\xb4\xad\xe7\x89\xa9 \xe5\xb9\xbf\xe5\x9c\xba', 6), ('sm \xe5\x9b\xbd\xe9\x99\x85 \xe5\xb9\xbf\xe5\x9c\xba', 2)]
================= delete =====================
None


支持中文的基于词为基本粒度的前缀树（prefix trie）python实现