python 二叉树模块_Python中的二叉树查找算法模块使用指南

python中的二叉树模块内容：

BinaryTree：非平衡二叉树

AVLTree：平衡的AVL树

RBTree：平衡的红黑树

以上是用python写的，相面的模块是用c写的，并且可以做为Cython的包。

FastBinaryTree

FastAVLTree

FastRBTree

特别需要说明的是：树往往要比python内置的dict类慢一些，但是它中的所有数据都是按照某个关键词进行排序的，故在某些情况下是必须使用的。

安装和使用

安装方法

安装环境：

ubuntu12.04, python 2.7.6

安装方法

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)

- 逐个增加键值对： .__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

- 根据key删除某个key-value： .__delitem__(key), O(log(n))

看例子：

>>> btree

BinaryTree({2: 'phone', 5: 'tea', 7: 'comp