一般語言都提供了按字典排序的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
$ python trie.py
['h', 'n', 'o', 'p', 't', 'y']
而且也可以使用我之前的一篇文章介紹的bitmap來實作：Python: 實作bitmap資料結構 。實作代碼如下：
#!/usr/bin/env python
#coding: utf8
class Bitmap(object):
def __init__(self, max):
self.size = self.calcElemIndex(max, True)
self.array = [0 for i in range(self.size)]
def calcElemIndex(self, num, up=False):
'''up為True則為向上取整, 否則為向下取整'''
if up:
return int((num + 31 - 1) / 31) #向上取整
return num / 31
def calcBitIndex(self, num):
return num % 31
def set(self, num):
elemIndex = self.calcElemIndex(num)
byteIndex = self.calcBitIndex(num)
elem = self.array[elemIndex]
self.array[elemIndex] = elem | (1 <
def clean(self, i):
elemIndex = self.calcElemIndex(i)
byteIndex = self.calcBitIndex(i)
elem = self.array[elemIndex]
self.array[elemIndex] = elem & (~(1 <
def test(self, i):
elemIndex = self.calcElemIndex(i)
byteIndex = self.calcBitIndex(i)
if self.array[elemIndex] & (1 <
return True
return False
if __name__ == '__main__':
MAX = ord('z')
suffle_array = [c for c in 'python']
result = []
bitmap = Bitmap(MAX)
for c in suffle_array:
bitmap.set(ord(c))
for i in range(MAX + 1):
if bitmap.test(i):
result.append(chr(i))
print '原始數組為: %s' % suffle_array
print '排序後的數組為: %s' % result
$ python trie.py
原始數組為: ['p', 'y', 't', 'h', 'o', 'n']
排序後的數組為: ['h', 'n', 'o', 'p', 't', 'y']
bitmap的排序不能有重複字元。其實剛才所說的基于ASCII碼相減的方式進行字典排序，已經有很多成熟算法了，比如插入排序、希爾排序、冒泡排序和堆排序等等。本文為了圖簡單，将使用Python自帶的sorted方法來進行單字元的字典排序。如果讀者自行實作單字元數組的排序也可以，而且這樣将可以自定義字元串的排序方式。
實作思路
整個實作包括2個類：Trie類和Node類。Node類表示Trie樹中的節點，由Trie類組織成一棵Trie樹。我們先來看Node類：
#!/usr/bin/env python
#coding: utf8
class Node(object):
def __init__(self, c=None, word=None):
self.c = c # 節點存儲的單個字元
self.word = word # 節點存儲的詞
self.childs = [] # 此節點的子節點
Node包含三個成員變量。c為每個節點上存儲的字元。word表示一個完整的詞，在本文中指的是一個字元串。childs包含這個節點的所有子節點。既然在每個節點中存儲了c，那麼存儲word有什麼用呢？并且這個word應該存在哪個節點上呢？還是用剛才的圖舉例子：比如go和golang，它們共用go字首，如果是字元串搜尋倒好辦，因為會提供原始字元串，隻要在這棵Trie樹上按照路徑搜尋即可。但是對于排序來說，不會提供任何輸入，是以無法知道單詞的邊界在哪裡，而Node類中的word就是起到單詞邊界作用。具體是存儲在單詞的最後一個節點上，如圖所示：
而Node類中的c成員如果這棵樹不用于搜尋，則可以不定義它，因為在排序中它不是必須的。
接下來我們看看Trie類的定義：
#!/usr/bin/env python
#coding: utf8
'''Trie樹實作字元串數組字典排序'''
class Trie(object):
def __init__(self):
self.root = Node() # Trie樹root節點引用
def add(self, word):
'''添加字元串'''
node = self.root
for c in word:
pos = self.find(node, c)
if pos
node.childs.append(Node(c))
#為了圖簡單，這裡直接使用Python内置的sorted來排序
#pos有問題，因為sort之後的pos會變掉,是以需要再次find來擷取真實的pos
#自定義單字元數組的排序方式可以實作任意規則的字元串數組的排序
node.childs = sorted(node.childs, key=lambda child: child.c)
pos = self.find(node, c)
node = node.childs[pos]
node.word = word
def preOrder(self, node):
'''先序輸出'''
results = []
if node.word:
results.append(node.word)
for child in node.childs:
results.extend(self.preOrder(child))
return results
def find(self, node, c):
'''查找字元插入的位置'''
childs = node.childs
_len = len(childs)
if _len == 0:
return -1
for i in range(_len):
if childs[i].c == c:
return i
return -1
def setWords(self, words):
for word in words:
self.add(word)
Trie包含1個成員變量和4個方法。root用于引用根結點，它不存儲具體的資料，但是它擁有子節點。setWords方法用于初始化，調用add方法來初始化Trie樹，這種調用是基于每個字元串的。add方法将每個字元添加到子節點，如果存在則共用它并尋找下一個子節點，依此類推。find是用于查找是否已經建立了存儲某個字元的子節點，而preOrder是先序擷取存儲的word。樹的周遊方式有三種：先序周遊、中序周遊和後序周遊，如果各位不太明白，可自行Google去了解。接下我們測試一下：
#!/usr/bin/env python
#coding: utf8
'''Trie樹實作字元串數組字典排序'''
class Trie(object):
def __init__(self):
self.root = Node() # Trie樹root節點引用
def add(self, word):
'''添加字元串'''
node = self.root
for c in word:
pos = self.find(node, c)
if pos
node.childs.append(Node(c))
#為了圖簡單，這裡直接使用Python内置的sorted來排序
#pos有問題，因為sort之後的pos會變掉,是以需要再次find來擷取真實的pos
#自定義單字元數組的排序方式可以實作任意規則的字元串數組的排序
node.childs = sorted(node.childs, key=lambda child: child.c)
pos = self.find(node, c)
node = node.childs[pos]
node.word = word
def preOrder(self, node):
'''先序輸出'''
results = []
if node.word:
results.append(node.word)
for child in node.childs:
results.extend(self.preOrder(child))
return results
def find(self, node, c):
'''查找字元插入的位置'''
childs = node.childs
_len = len(childs)
if _len == 0:
return -1
for i in range(_len):
if childs[i].c == c:
return i
return -1
def setWords(self, words):
for word in words:
self.add(word)
class Node(object):
def __init__(self, c=None, word=None):
self.c = c # 節點存儲的單個字元
self.word = word # 節點存儲的詞
self.childs = [] # 此節點的子節點
if __name__ == '__main__':
words = ['python', 'function', 'php', 'food', 'kiss', 'perl', 'goal', 'go', 'golang', 'easy']
trie = Trie()
trie.setWords(words)
result = trie.preOrder(trie.root)
print '原始字元串數組: %s' % words
print 'Trie樹排序後: %s' % result
words.sort()
print 'Python的sort排序後: %s' % words
$ python trie.py
原始字元串數組: ['python', 'function', 'php', 'food', 'kiss', 'perl', 'goal', 'go', 'golang', 'easy']
Trie樹排序後: ['easy', 'food', 'function', 'go', 'goal', 'golang', 'kiss', 'perl', 'php', 'python']
Python的sort排序後: ['easy', 'food', 'function', 'go', 'goal', 'golang', 'kiss', 'perl', 'php', 'python']
結束語
樹的種類非常之多。在樹結構的實作中，樹的周遊是個難點，需要多加練習。上述代碼寫得比較倉促，沒有進行任何優化，但在此基礎上可以實作任何方式的字元串排序，以及字元串搜尋等。