python中的二叉樹模塊內(nèi)容：
BinaryTree：非平衡二叉樹
AVLTree：平衡的AVL樹
RBTree：平衡的紅黑樹
以上是用python寫的，相面的模塊是用c寫的，并且可以做為Cython的包。
FastBinaryTree
FastAVLTree
FastRBTree
特別需要說明的是：樹往往要比python內(nèi)置的dict類慢一些，但是它中的所有數(shù)據(jù)都是按照某個關(guān)鍵詞進(jìn)行排序的，故在某些情況下是必須使用的。
安裝和使用
安裝方法
安裝環(huán)境：
ubuntu12.04, python 2.7.6
安裝方法
下載源碼，地址：https://bitbucket.org/mozman/bintrees/src
進(jìn)入源碼目錄，看到setup.py文件，在該目錄內(nèi)運行
python setup.py install
安裝成功，ok!下面就看如何使用了。
應(yīng)用
bintrees提供了豐富的API,涵蓋了通常的多種應(yīng)用。下面逐條說明其應(yīng)用。
- 引用
如果按照一般模塊的思路，輸入下面的命令引入上述模塊
>>> import bintrees
錯了，這是錯的，出現(xiàn)如下警告：(×××不可用，用×××）
Warning: FastBinaryTree not available, using Python version BinaryTree. Warning: FastAVLTree not available, using Python version AVLTree. Warning: FastRBTree not available, using Python version RBTree.
正確的引入方式是：
>>> from bintrees import BinaryTree #只引入了BinartTree >>> from bintrees import * #三個模塊都引入了
- 實例化
看例子：
>>> btree = BinaryTree() >>> btree BinaryTree({}) >>> type(btree) <class 'bintrees.bintree.BinaryTree'>
- 逐個增加鍵值對： .__setitem__(k,v) .復(fù)雜度O(log(n))(后續(xù)說明中，都會有復(fù)雜度標(biāo)示，為了簡單，直接標(biāo)明：O(log(n)).)
看例子：
>>> btree.__setitem__("Tom","headmaster") >>> btree BinaryTree({'Tom': 'headmaster'}) >>> btree.__setitem__("blog","http://blog.csdn.net/qiwsir") >>> btree BinaryTree({'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
- 批量添加： .update(E) E是dict/iterable，將E批量更新入btree. O(E*log(n))
看例子：
>>> adict = [(2,"phone"),(5,"tea"),(9,"scree"),(7,"computer")] >>> btree.update(adict) >>> btree BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
- 查找某個key是否存在： .__contains__(k) 如果含有鍵k，則返回True,否則返回False. O(log(n))
看例子：
>>> btree BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> btree.__contains__(5) True >>> btree.__contains__("blog") True >>> btree.__contains__("qiwsir") False >>> btree.__contains__(1) False
- 根據(jù)key刪除某個key-value： .__delitem__(key), O(log(n))
看例子：
>>> btree BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> btree.__delitem__(5) #刪除key=5的key-value,即：5:'tea' 被刪除. >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})- 根據(jù)key值得到該kye的value： .__getitem__(key)
看例子：
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> btree.__getitem__("blog") 'http://blog.csdn.net/qiwsir' >>> btree.__getitem__(7) 'computer' >>> btree._getitem__(5) #在btree中沒有key=5，于是報錯。 Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'BinaryTree' object has no attribute '_getitem__'- 迭代器： .__iter__()
看例子：
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> aiter = btree.__iter__() >>> aiter <generator object <genexpr> at 0xb7416dec> >>> aiter.next() #注意：next()一個之后，該值從list中刪除 2 >>> aiter.next() 7 >>> list(aiter) [9, 'Tom', 'blog'] >>> list(aiter) #結(jié)果是空 [] >>> bool(aiter) #but,is True True- 樹的數(shù)據(jù)長度： .__len__(),返回btree的長度。O(1)
看例子：
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'}) >>> btree.__len__() 5- 找出key最大的k-v對： .__max__(),按照key排列，返回key最大的鍵值對。
- 找出key最小的鍵值對： .__min__()
看例子：
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> btree.__max__() (9, 'scree') >>> btree.__min__() (2, 'phone')- 兩棵樹的關(guān)系運算
看例子：
>>> other = [(3,'//m.survivalescaperooms.com'),(7,'qiwsir')] >>> bother = BinaryTree() #再建一個樹 >>> bother.update(other) #加入數(shù)據(jù) >>> bother BinaryTree({3: '//m.survivalescaperooms.com', 7: 'qiwsir'}) >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> btree.__and__(bother) #重疊部分部分 BinaryTree({7: 'computer'}) >>> btree.__or__(bother) #全部 BinaryTree({2: 'phone', 3: '//m.survivalescaperooms.com, 7: 'computer', 9: 'scree'}) >>> btree.__sub__(bother) #btree不與bother重疊的部分 BinaryTree({2: 'phone', 9: 'scree'}) >>> btree.__xor__(bother) #兩者非重疊部分 BinaryTree({2: 'phone', 3: '//m.survivalescaperooms.com, 9: 'scree'})- 輸出字符串模樣，注意僅僅是輸出的模樣罷了： .__repr__()
看例子：
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> btree.__repr__() "BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})"- 清空樹中的所有數(shù)據(jù) :.clear(),O(log(n))
看例子：
>>> bother BinaryTree({3: 'http://blog.csdn.net/qiwsir', 7: 'qiwsir'}) >>> bother.clear() >>> bother BinaryTree({}) >>> bool(bother) False- 淺拷貝： .copy(),官方文檔上說是淺拷貝，但是我做了操作實現(xiàn)，是下面所示，還不是很理解其“淺”的含義。O(n*log(n))
看例子：
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> ctree = btree.copy() >>> ctree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) >>> btree.__setitem__("github","qiwsir") #增加btree的數(shù)據(jù) >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> ctree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) #這是不是在說明屬于深拷貝呢？ >>> ctree.__delitem__(7) #刪除ctree的一個數(shù)據(jù) >>> ctree BinaryTree({2: 'phone', 9: 'scree'}) >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
- 移除樹中的一個數(shù)據(jù)： .discard(key)，這個功能與.__delitem__(key)類似.兩者都不反悔值。O(log(n))
看例子：
>>> ctree BinaryTree({2: 'phone', 9: 'scree'}) >>> ctree.discard(2) #刪除后，不返回值，或者返回None >>> ctree BinaryTree({9: 'scree'}) >>> ctree.discard(2) #如果刪除的key不存在，也返回None >>> ctree.discard(3) >>> ctree.__delitem__(3) #但是，.__delitem__(key)則不同，如果key不存在，會報錯。 Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 264, in __delitem__ self.remove(key) File "/usr/local/lib/python2.7/site-packages/bintrees/bintree.py", line 124, in remove raise KeyError(str(key)) KeyError: '3'- 根據(jù)key查找，并返回或返回備用值： .get(key[,d])。如果key在樹中存在，則返回value,否則如果有d，則返回d值。O(log(n))
看例子：
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> btree.get(2,"algorithm") 'phone' >>> btree.get("python","algorithm") #沒有key='python'的值，返回'algorithm' 'algorithm' >>> btree.get("python") #如果不指定第二個參數(shù)，若查不到，則返回None >>>- 判斷樹是否為空： is_empty().根據(jù)樹數(shù)據(jù)的長度，如果數(shù)據(jù)長度為0,則為空。O(1)
看例子：
>>> ctree BinaryTree({9: 'scree'}) >>> ctree.clear() #清空數(shù)據(jù) >>> ctree BinaryTree({}) >>> ctree.is_empty() True >>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> btree.is_empty() False- 根據(jù)key、value循環(huán)從樹中取值：
>>.items([reverse])--按照(key,value)結(jié)構(gòu)取值;
>>.keys([reverse])--key
>>.values([reverse])--value. O(n)
>>.iter_items(s,e[,reverse]--s,e是key的范圍，也就是生成在某個范圍內(nèi)的key的迭代器 O(n)
看例子：
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> for (k,v) in btree.items(): ... print k,v ... 2 phone 7 computer 9 scree github qiwsir >>> for k in btree.keys(): ... print k ... 2 7 9 github >>> for v in btree.values(): ... print v ... phone computer scree qiwsir >>> for (k,v) in btree.items(reverse=True): #反序 ... print k,v ... github qiwsir 9 scree 7 computer 2 phone >>> btree BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> for (k,v) in btree.iter_items(6,9): #要求迭代6<=key<9的鍵值對數(shù)據(jù) ... print k,v ... 7 computer 8 eight >>>
- 刪除數(shù)據(jù)并返回該值：
>>.pop(key[,d]), 根據(jù)key刪除樹的數(shù)據(jù)，并返回該value，但是如果沒有，并也指定了備選返回的d，則返回d，如果沒有d，則報錯；
>>.pop_item(),在樹中隨機選擇(key,value)刪除，并返回。
看例子：
>>> ctree = btree.copy() >>> ctree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> ctree.pop(2) #刪除key=2的數(shù)據(jù)，返回其value 'phone' >>> ctree.pop(2) #刪除一個不存在的key，報錯 Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 350, in pop value = self.get_value(key) File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 557, in get_value raise KeyError(str(key)) KeyError: '2' >>> ctree.pop_item() #隨機返回一個(key,value),并已刪除之 (7, 'computer') >>> ctree BinaryTree({9: 'scree', 'github': 'qiwsir'}) >>> ctree.pop(7,"sing") #如果沒有，可以返回指定值 'sing'- 查找數(shù)據(jù),并返回value： .set_default(key[,d])，在樹的數(shù)據(jù)中查找key,如果存在，則返回該value。如果不存在，當(dāng)指定了d,則將該（key,d）添加到樹內(nèi)；當(dāng)不指定d的時候，添加(key,None). O(log(n))
看例子：
>>> btree BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'}) >>> btree.set_default(7) #存在則返回 'computer' >>> btree.set_default(8,"eight") #不存在，則返回后備指定值，并加入到樹 'eight' >>> btree BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> btree.set_default(5) #如果不指定值，則會加入None >>> btree BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> btree.get(2) #注意，.get(key)與.set_default(key[,d])的區(qū)別 'phone' >>> btree.get(3,"mobile") #不存在的 key,返回但不增加到樹 'mobile' >>> btree BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})- 根據(jù)key刪除值
>>.remove(key),刪除(key,value)
>>.remove_items(keys),keys是一個key組成的list,逐個刪除樹中的對應(yīng)數(shù)據(jù)
看例子：
>>> ctree BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> ctree.remove_items([5,6]) #key=6，不存在，報錯 Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 271, in remove_items self.remove(key) File "/usr/local/lib/python2.7/site-packages/bintrees/bintree.py", line 124, in remove raise KeyError(str(key)) KeyError: '6' >>> ctree BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'}) >>> ctree.remove_items([2,7,'github']) #按照 列表中順序逐個刪除 >>> ctree BinaryTree({8: 'eight', 9: 'scree'})
##以上只是入門的基本方法啦，還有更多內(nèi)容，請移不到到文章開頭的官方網(wǎng)站
新聞熱點
疑難解答
圖片精選
