一般语言都提供了按字典排序的API，比如跟微信公众平台对接时就需要用到字典排序。按字典排序有很多种算法，最容易想到的就是字符串搜索的方式，但这种方式实现起来很麻烦，性能也不太好。Trie树是一种很常用的树结构，它被广泛用于各个方面，比如字符串检索、中文分词、求字符串最长公共前缀和字典排序等等，而且在输入法中也能看到Trie树的身影。

什么是Trie树

Trie树通常又称为字典树、单词查找树或前缀树，是一种用于快速检索的多叉树结构。如图数字的字典是一个10叉树：

同理小写英文字母或大写英文字母的字典数是一个26叉树。如上图可知，Trie树的根结点是不保存数据的，所有的数据都保存在它的孩子节点中。有字符串go, golang, php, python, perl，它这棵Trie树可如下图所示构造：

我们来分析下上面这张图。除了根节点外，每个子节点只存储一个字符。go和golang共享go前缀，php、perl和python只共用p前缀。为了实现字典排序，每一层节点上存储的字符都是按照字典排序的方式存储(这跟遍历的方式有关)。我们先来看看对单个字符如何进行字典排序。本文只考虑小写字母，其它方式类似。'a'在'b'的前面，而'a'的ASCII码小于'b'的ASCII码，因此通过它们的ASCII相减就可以得到字典顺序。而且python内置了字典排序的API，比如：

复制代码 代码如下:

!/usr/bin/env python

coding: utf8

if name == 'main':
arr = [c for c in 'python']
arr.sort()
print arr