错位的梦寐

Python常用数据结构之 binarytree 模块

2019-12-11

Python
   

binarytree 是一个Python库，它通过一个简单的API生成二叉树，可以进行检查和操作。

API Specification

Class: binarytree.Node

classbinarytree.Node(value, left=None, right=None)

树的节点，指当前节点和它的子节点 。

参数：

  • value (int , float , numbers.Number) – Node value (must be a number)
  • left (binarytree.Node , None) – Left child node (default: None).
  • right (binarytree.Node , None) – Right child node (default: None).

常用的方法

  • values 返回二叉树的列表表示形式。返回值类型 ： [int ,float , None]

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.right = Node(4)
>>>
>>> root.values
[1, 2, 3, None, 4]

  • 删除 __delitem__(index)

    参数：index (int) – Level-order index of the node. 但是不能删除根节点，index 不能越界

    from binarytree import Node
  
root = Node(1)       # index: 0, value: 1
root.left = Node(2)  # index: 1, value: 2
root.right = Node(3) # index: 2, value: 3
  
del root[2]

  • 根据 index 获取节点 ，__getitem__(index) 返回 index 处的节点。index 不能越界 。

    >>> from binarytree import Node
>>>
>>> root = Node(1)       # index: 0, value: 1
>>> root.left = Node(2)  # index: 1, value: 2
>>> root.right = Node(3) # index: 2, value: 3
>>>
>>> root[0]
Node(1)
>>> root[1]
Node(2)
>>> root[2]
Node(3)
>>> root[3]  
Traceback (most recent call last):

  • 可迭代，__iter__() 返回值类型为 Node

    from binarytree import Node
  
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print([node for node in root])
# [Node(1), Node(2), Node(3), Node(4), Node(5)]

  • 可以用函数 len() 获取节点的个数，

  • 可以通过下标的方式改变节点的值。

  • 属性 height 查看树的高度

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.left.left = Node(3)
>>>
>>> print(root)
  
    1
   /
  2
 /
3
  
>>> root.height
2

  • 前序遍历 preorder ，返回值类型 ： [binarytree.Node]

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.left = Node(4)
>>> root.left.right = Node(5)
>>>
>>> print(root)
  
    __1
   /   \
  2     3
 / \
4   5
  
>>> root.preorder
[Node(1), Node(2), Node(4), Node(5), Node(3)]

  • 中序遍历 inorder ，返回值类型 ： [binarytree.Node]

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.left = Node(4)
>>> root.left.right = Node(5)
>>>
>>> print(root)
  
    __1
   /   \
  2     3
 / \
4   5
  
>>> root.inorder
[Node(4), Node(2), Node(5), Node(1), Node(3)]

  • 后序遍历 postorder ，返回值类型 ： [binarytree.Node]

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.left = Node(4)
>>> root.left.right = Node(5)
>>>
>>> print(root)
  
    __1
   /   \
  2     3
 / \
4   5
  
>>> root.postorder
[Node(4), Node(5), Node(2), Node(3), Node(1)]

  • levelorder 层次化遍历 ，返回值类型 ： [binarytree.Node]

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.left = Node(4)
>>> root.left.right = Node(5)
>>>
>>> print(root)
  
    __1
   /   \
  2     3
 / \
4   5
  
>>> root.levelorder
[Node(1), Node(2), Node(3), Node(4), Node(5)]

  • leaf_count 计算叶节点的个数 ，返回值类型：int

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.right = Node(4)
>>>
>>> root.leaf_count
2

  • leaves 返回值叶节点 ，返回值类型：[binarytree.Node]

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.right = Node(4)
>>>
>>> print(root)
  
  __1
 /   \
2     3
 \
  4
  
>>> root.leaves
[Node(3), Node(4)]

  • levels 返回每一层的节点，返回值类型：[[binarytree.Node]]

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.right = Node(4)
>>>
>>> print(root)
  
  __1
 /   \
2     3
 \
  4
  
>>>
>>> root.levels
[[Node(1)], [Node(2), Node(3)], [Node(4)]]

  • max_leaf_depth 返回最大叶节点的深度 ， 返回值类型 : int

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.right.left = Node(4)
>>> root.right.left.left = Node(5)
>>>
>>> print(root)
  
  1____
 /     \
2       3
       /
      4
     /
    5
  
>>> root.max_leaf_depth
3

  • min_leaf_depth 返回最小叶节点的深度 ， 返回值类型 : int

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.right.left = Node(4)
>>> root.right.left.left = Node(5)
>>>
>>> print(root)
  
  1____
 /     \
2       3
       /
      4
     /
    5
  
>>> root.min_leaf_depth
1

  • max_node_value 返回最大节点的值 ， 返回值类型 ：int

  • min_node_value 返回最小节点的值 ， 返回值类型 ：int

  • properties 返回二叉树的各种属性。返回值类型 ： dict

    from binarytree import Node
  
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
props = root.properties
  
props
{'height': 2,
 'size': 5,
 'is_max_heap': False,
 'is_min_heap': True,
 'is_perfect': False,
 'is_strict': True,
 'is_complete': True,
 'leaf_count': 3,
 'min_node_value': 1,
 'max_node_value': 5,
 'min_leaf_depth': 1,
 'max_leaf_depth': 2,
 'is_bst': False,
 'is_balanced': True,
 'is_symmetric': False}

  • is_balanced 判断是否是平衡树 ，返回值类型 ：bool

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.left.left = Node(3)
>>>
>>> print(root)
  
    1
   /
  2
 /
3
  
>>> root.is_balanced
False

  • is_bst 判断是否是二叉搜索树，返回值类型：bool

    >>> from binarytree import Node
>>>
>>> root = Node(2)
>>> root.left = Node(1)
>>> root.right = Node(3)
>>>
>>> print(root)
  
  2
 / \
1   3
  
>>> root.is_bst
True

  • is_complete 判断是否是完全二叉树， 返回值类型：bool

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.left = Node(4)
>>> root.left.right = Node(5)
>>>
>>> print(root)
  
    __1
   /   \
  2     3
 / \
4   5
  
>>> root.is_complete
True

  • is_max_heap 判断是否是最大堆，返回值类型：bool

  • is_min_heap 判断是否是最小堆，返回值类型：bool

  • is_perfect Check if the binary tree is perfect , 返回值类型：bool

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.left = Node(4)
>>> root.left.right = Node(5)
>>> root.right.left = Node(6)
>>> root.right.right = Node(7)
>>>
>>> print(root)
  
    __1__
   /     \
  2       3
 / \     / \
4   5   6   7
  
>>> root.is_perfect
True

  • is_strict 返回值类型：bool A binary tree is strict if all its non-leaf nodes have both the left and right child nodes.

    >>> from binarytree import Node
>>>
>>> root = Node(1)
>>> root.left = Node(2)
>>> root.right = Node(3)
>>> root.left.left = Node(4)
>>> root.left.right = Node(5)
>>>
>>> print(root)
  
    __1
   /   \
  2     3
 / \
4   5
  
>>> root.is_strict
True

Function: binarytree.build

binarytree.build(values) 从列表表示形式构建树并返回其根节点。

返回值 ：二叉树的根节点 。

返回值类型 ： binarytree.Node

>>> from binarytree import build
>>>
>>> root = build([1, 2, 3, None, 4])
>>>
>>> print(root)

  __1
 /   \
2     3
 \
  4

Function: binarytree.tree

binarytree.tree(height=3,is_perfect=False) 生成一个随机的二叉树并返回其根节点。

参数：

  • height (int) – Height of the tree (default: 3, range: 0 - 9 inclusive).
  • is_perfect (bool) – If set to True (default: False), a perfect binary tree with all levels filled is returned. If set to False, a perfect binary tree may still be generated by chance.

返回值：二叉树的根节点

返回值类型 ： binarytree.Node

>>> from binarytree import tree
>>>
>>> root = tree()
>>>
>>> root.height
3

>>> from binarytree import tree
>>>
>>> root = tree(height=5, is_perfect=True)
>>>
>>> root.height
5
>>> root.is_perfect
True

Function: binarytree.bst

binarytree.bst**(height=3,is_perfect=False) ** 生成随机BST（二进制搜索树）并返回其根节点。

>>> from binarytree import bst
>>>
>>> root = bst()
>>>
>>> root.height
3
>>> root.is_bst
True

Function: binarytree.heap

binarytree.heap(height=3,is_max=True,is_perfect=False) 生成随机堆并返回其根节点。

>>> from binarytree import heap
>>>
>>> root = heap()
>>>
>>> root.height
3
>>> root.is_max_heap
True

参考：

  1. binarytree

上一篇 Python常用数据结构之 heapq 模块

下一篇 二叉树

Comments

Content