python中的二叉樹模塊內容：

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

FastBinaryTree
 FastAVLTree
 FastRBTree
特別需要說明的是：樹往往要比python內置的dict類慢一些，但是它中的所有數據都是按照某個關鍵詞進行排序的，故在某些情況下是必須使用的。

安裝和使用

安裝方法

安裝環境：

ubuntu12.04, python 2.7.6

安裝方法

下載源碼，地址：https://bitbucket.org/mozman/bintrees/src
進入源碼目錄，看到setup.py文件，在該目錄內運行   

python setup.py install

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

應用

bintrees提供了豐富的API,涵蓋了通常的多種應用。下面逐條說明其應用。

- 引用

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

>>> import bintrees

 
錯了，這是錯的，出現如下警告：(×××不可用，用×××）

  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) .復雜度O(log(n))(后續說明中，都會有復雜度標示，為了簡單，直接標明：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