Python中的二叉樹(shù)查找算法模塊使用指南

更新時(shí)間：2014年07月04日 10:03:30 投稿：hebedich

二叉樹(shù)查找算法，在開(kāi)發(fā)實(shí)踐中，會(huì)經(jīng)常用到。按照慣例，對(duì)于這么一個(gè)常用的東西，Python一定會(huì)提供輪子的。是的，python就是這樣，一定會(huì)讓開(kāi)發(fā)者省心，降低開(kāi)發(fā)者的工作壓力。

python中的二叉樹(shù)模塊內(nèi)容：

BinaryTree：非平衡二叉樹(shù)
AVLTree：平衡的AVL樹(shù)
RBTree：平衡的紅黑樹(shù)
以上是用python寫(xiě)的，相面的模塊是用c寫(xiě)的，并且可以做為Cython的包。

FastBinaryTree
FastAVLTree
FastRBTree
特別需要說(shuō)明的是：樹(shù)往往要比python內(nèi)置的dict類(lèi)慢一些，但是它中的所有數(shù)據(jù)都是按照某個(gè)關(guān)鍵詞進(jìn)行排序的，故在某些情況下是必須使用的。

安裝和使用

安裝方法

安裝環(huán)境：

ubuntu12.04, python 2.7.6

安裝方法

下載源碼，地址：https://bitbucket.org/mozman/bintrees/src
進(jìn)入源碼目錄，看到setup.py文件，在該目錄內(nèi)運(yùn)行

python setup.py install

安裝成功，ok!下面就看如何使用了。

應(yīng)用

bintrees提供了豐富的API,涵蓋了通常的多種應(yīng)用。下面逐條說(shuō)明其應(yīng)用。

- 引用

如果按照一般模塊的思路，輸入下面的命令引入上述模塊

>>> import bintrees

錯(cuò)了，這是錯(cuò)的，出現(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 *       #三個(gè)模塊都引入了

- 實(shí)例化

看例子：

>>> btree = BinaryTree()
  >>> btree
  BinaryTree({})
  >>> type(btree)
  <class 'bintrees.bintree.BinaryTree'>

- 逐個(gè)增加鍵值對(duì)： .__setitem__(k,v) .復(fù)雜度O(log(n))(后續(xù)說(shuō)明中，都會(huì)有復(fù)雜度標(biāo)示，為了簡(jiǎn)單，直接標(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'})

- 查找某個(gè)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刪除某個(gè)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中沒(méi)有key=5，于是報(bào)錯(cuò)。
 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()一個(gè)之后，該值從list中刪除
 2
 >>> aiter.next()
 7
 >>> list(aiter)
 [9, 'Tom', 'blog']
 >>> list(aiter)  #結(jié)果是空
 []
 >>> bool(aiter)  #but,is True
 True

- 樹(shù)的數(shù)據(jù)長(zhǎng)度： .__len__(),返回btree的長(zhǎng)度。O(1)

看例子：

>>> btree
  BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
  >>> btree.__len__()
  5

- 找出key最大的k-v對(duì)： .__max__(),按照key排列，返回key最大的鍵值對(duì)。

- 找出key最小的鍵值對(duì)： .__min__()

看例子：

>>> btree
 BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
 >>> btree.__max__()
 (9, 'scree')
 >>> btree.__min__()
 (2, 'phone')

- 兩棵樹(shù)的關(guān)系運(yùn)算

看例子：

>>> other = [(3,'http://www.dhdzp.com'),(7,'qiwsir')]
 >>> bother = BinaryTree()  #再建一個(gè)樹(shù)
 >>> bother.update(other) #加入數(shù)據(jù)

 >>> bother
 BinaryTree({3: 'http://www.dhdzp.com', 7: 'qiwsir'})
 >>> btree
 BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
 
 >>> btree.__and__(bother)  #重疊部分部分
 BinaryTree({7: 'computer'})

 >>> btree.__or__(bother) #全部
 BinaryTree({2: 'phone', 3: 'http://www.dhdzp.com, 7: 'computer', 9: 'scree'})

 >>> btree.__sub__(bother)  #btree不與bother重疊的部分
 BinaryTree({2: 'phone', 9: 'scree'})
 
 >>> btree.__xor__(bother)  #兩者非重疊部分
 BinaryTree({2: 'phone', 3: 'http://www.dhdzp.com, 9: 'scree'})

- 輸出字符串模樣，注意僅僅是輸出的模樣罷了： .__repr__()

看例子：

>>> btree
  BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
  >>> btree.__repr__()
  "BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})"

- 清空樹(shù)中的所有數(shù)據(jù) :.clear(),O(log(n))

看例子：

>>> bother  
 BinaryTree({3: 'http://blog.csdn.net/qiwsir', 7: 'qiwsir'})
 >>> bother.clear()
 >>> bother
 BinaryTree({})
 >>> bool(bother)
 False

- 淺拷貝： .copy(),官方文檔上說(shuō)是淺拷貝，但是我做了操作實(shí)現(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'}) #這是不是在說(shuō)明屬于深拷貝呢？
 
 >>> ctree.__delitem__(7) #刪除ctree的一個(gè)數(shù)據(jù)
 >>> ctree
 BinaryTree({2: 'phone', 9: 'scree'})
 >>> btree
 BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})

- 移除樹(shù)中的一個(gè)數(shù)據(jù)： .discard(key)，這個(gè)功能與.__delitem__(key)類(lèi)似.兩者都不反悔值。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不存在，會(huì)報(bào)錯(cuò)。
 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在樹(shù)中存在，則返回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") #沒(méi)有key='python'的值，返回'algorithm'
 'algorithm'
 >>> btree.get("python") #如果不指定第二個(gè)參數(shù)，若查不到，則返回None
 >>>

- 判斷樹(shù)是否為空： is_empty().根據(jù)樹(shù)數(shù)據(jù)的長(zhǎng)度，如果數(shù)據(jù)長(zhǎng)度為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)從樹(shù)中取值：

>>.items([reverse])--按照(key,value)結(jié)構(gòu)取值;

>>.keys([reverse])--key

>>.values([reverse])--value. O(n)

>>.iter_items(s,e[,reverse]--s,e是key的范圍，也就是生成在某個(gè)范圍內(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的鍵值對(duì)數(shù)據(jù)
 ... print k,v
 ...
 7 computer
 8 eight
 >>>

- 刪除數(shù)據(jù)并返回該值：

>>.pop(key[,d]), 根據(jù)key刪除樹(shù)的數(shù)據(jù)，并返回該value，但是如果沒(méi)有，并也指定了備選返回的d，則返回d，如果沒(méi)有d，則報(bào)錯(cuò)；

>>.pop_item(),在樹(shù)中隨機(jī)選擇(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) #刪除一個(gè)不存在的key，報(bào)錯(cuò)
 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()  #隨機(jī)返回一個(gè)(key,value),并已刪除之
 (7, 'computer')
 >>> ctree
 BinaryTree({9: 'scree', 'github': 'qiwsir'})
 
 >>> ctree.pop(7,"sing") #如果沒(méi)有，可以返回指定值
 'sing'

- 查找數(shù)據(jù),并返回value： .set_default(key[,d])，在樹(shù)的數(shù)據(jù)中查找key,如果存在，則返回該value。如果不存在，當(dāng)指定了d,則將該（key,d）添加到樹(shù)內(nèi)；當(dāng)不指定d的時(shí)候，添加(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") #不存在，則返回后備指定值，并加入到樹(shù)
 'eight'
 >>> btree
 BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
 
 >>> btree.set_default(5) #如果不指定值，則會(huì)加入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,返回但不增加到樹(shù)
 'mobile'
 >>> btree
 BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})

- 根據(jù)key刪除值

>>.remove(key),刪除(key,value)

>>.remove_items(keys),keys是一個(gè)key組成的list,逐個(gè)刪除樹(shù)中的對(duì)應(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，不存在，報(bào)錯(cuò)
 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']) #按照 列表中順序逐個(gè)刪除
 >>> ctree
 BinaryTree({8: 'eight', 9: 'scree'})

##以上只是入門(mén)的基本方法啦，還有更多內(nèi)容，請(qǐng)移不到到文章開(kāi)頭的官方網(wǎng)站

您可能感興趣的文章: