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

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

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

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

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

FastBinaryTree
FastAVLTree
FastRBTree
特別需要說明的是：樹往往要比python內(nèi)置的dict類慢一些，但是它中的所有數(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)用。下面逐條說明其應(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è)增加鍵值對： .__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'})

- 查找某個(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中沒有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ù)據(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)系運(yùn)算

看例子：

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

 >>> bother
 BinaryTree({3: 'http://www.fzitv.net', 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.fzitv.net, 7: 'computer', 9: 'scree'})

 >>> btree.__sub__(bother)  #btree不與bother重疊的部分
 BinaryTree({2: 'phone', 9: 'scree'})
 
 >>> btree.__xor__(bother)  #兩者非重疊部分
 BinaryTree({2: 'phone', 3: 'http://www.fzitv.net, 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(),官方文檔上說是淺拷貝，但是我做了操作實(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'}) #這是不是在說明屬于深拷貝呢？
 
 >>> ctree.__delitem__(7) #刪除ctree的一個(gè)數(shù)據(jù)
 >>> ctree
 BinaryTree({2: 'phone', 9: 'scree'})
 >>> btree
 BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})

- 移除樹中的一個(gè)數(shù)據(jù)： .discard(key)，這個(gè)功能與.__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不存在，會報(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在樹中存在，則返回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") #如果不指定第二個(gè)參數(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的范圍，也就是生成在某個(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的鍵值對數(shù)據(jù)
 ... print k,v
 ...
 7 computer
 8 eight
 >>>

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

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

>>.pop_item(),在樹中隨機(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") #如果沒有，可以返回指定值
 'sing'

- 查找數(shù)據(jù),并返回value： .set_default(key[,d])，在樹的數(shù)據(jù)中查找key,如果存在，則返回該value。如果不存在，當(dāng)指定了d,則將該（key,d）添加到樹內(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") #不存在，則返回后備指定值，并加入到樹
 '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是一個(gè)key組成的list,逐個(gè)刪除樹中的對應(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'})

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

您可能感興趣的文章: