[Python] 看binarytree源码深入学习二叉树

1. binarytree 库

binarytree

1.1 运行环境

Python 2.7, 3.4, 3.5 或 3.6

1.2 安装方法

pip install binarytree

1.3 自动构建随机二叉树

>>> from binarytree import tree, bst, heap
>>> 
>>> # 构建节点随机的二叉树
>>> my_tree = tree(height=3, is_perfect=True)
>>> print(my_tree)

        ________7_______
       /                \
    __9__             ___8___
   /     \           /       \
  3       10        14       _1
 / \     /  \      /  \     /  \
4   5   2    12   6    0   11   13

>>> # 构建随机的二叉查找树
>>> my_bst = bst(height=3, is_perfect=False)
>>> print(my_bst)

  1______
 /       \
0       __13
       /    \
      3      14
     / \
    2   8
    
>>> # 构建随机最大/小堆二叉树
>>> my_heap = heap(height=3, is_max=True, is_perfect=False)
>>> print(my_heat)

      ___14__
     /       \
    11        13
   /  \      /  \
  6    8    5    7
 /
0

1.4 手动构建二叉树

>>> from binarytree import Node
>>> # 创建根节点
>>> root = Node(1)
>>> # 创建左节点
>>> root.left = Node(2)
>>> # 创建右节点
>>> root.right = Node(3)
>>> # 创建右节点的左节点
>>> root.right.left = Node(4)

  1__
 /   \
2     3
     /
    4
>>> # 取节点
>>> root[1]
Node(2)
>>> root[2]
Node(3)

1.5 查看二叉树性质

>>> 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.height
2
>>> root.is_balanced
True
>>> root.is_bst
False
>>> root.is_complete
True
>>> root.is_max_heap
False
>>> root.is_min_heap
True
>>> root.is_perfect
False
>>> root.is_strict
True
>>> root.leaf_count
3
>>> root.max_leaf_depth
2
>>> root.max_node_value
5
>>> root.min_leaf_depth
1
>>> root.min_node_value
1
>>> root.size
5

>>> properties = root.properties  # Get all properties at once
>>> properties['height']
2
>>> properties['is_balanced']
True
>>> properties['max_leaf_depth']
2

>>> root.leaves
[Node(3), Node(4), Node(5)]

>>> root.levels
[[Node(1)], [Node(2), Node(3)], [Node(4), Node(5)]]

2. 二叉树创建源码解析

接下来就跟着binarytree的源码更深入地学习使用python构建二叉树吧。

2.1 Node

看一下节点Node的源码，看到这里我惭愧了，要知道我自己创建的节点代码只有5行...而binarytree库中的Node代码不算注释与空格就有286行。

首先看一下它的初始化函数__init__：

def __init__(self, value, left=None, right=None):
    if not isinstance(value, numbers.Number):
        raise NodeValueError('node value must be a number')
    if left is not None and not isinstance(left, Node):
        raise NodeTypeError('left child must be a Node instance')
    if right is not None and not isinstance(right, Node):
        raise NodeTypeError('right child must be a Node instance')

    self.value = value
    self.left = left
    self.right = right

这里限制了定义节点时，它的值则必须是数字，且它的左右子节点为空或是Node类的实例（默认为空）。

再看一下设置属性值时会调用的函数__setattr__:

def __setattr__(self, attr, obj):

    if attr == 'left':
        if obj is not None and not isinstance(obj, Node):
            raise NodeTypeError(
                'left child must be a Node instance')
    elif attr == 'right':
        if obj is not None and not isinstance(obj, Node):
            raise NodeTypeError(
                'right child must be a Node instance')
    elif attr == 'value' and not isinstance(obj, numbers.Number):
        raise NodeValueError('node value must be a number')

    object.__setattr__(self, attr, obj)

可以看到这里对设定的属性值做了一下参数校验，随后继承了object的__setattr__。

1.4中的栗子说到，通过Node添加好二叉树后，可以通过index去访问相应节点，如下：

>>>root = Node(1)
>>>root.left = Node(2)
>>>root.right = Node(3)
>>>root.left.left = Node(4)
>>>root.left.right = Node(5)
>>>root[2]
Node(3)

这个用法主要靠__getitem__实现，贴一下__getitem__的代码：

def __getitem__(self, index):
    if not isinstance(index, int) or index < 0:
        raise NodeIndexError(
            'node index must be a non-negative int')
    # 进行遍历的序列
    current_nodes = [self]
    # 设置初始index
    current_index = 0
    # 设置未遍历完的flag
    has_more_nodes = True

    while has_more_nodes:
        has_more_nodes = False
        next_nodes = []
        
        # 遍历队列中的节点
        for node in current_nodes:
            # 若index符合，返回或抛异常
            if current_index == index:
                if node is None:
                    break
                else:
                    return node
            current_index += 1
 
            if node is None:
                next_nodes.extend((None, None))
                continue
            next_nodes.extend((node.left, node.right))
            # 判断是否有后续节点
            if node.left is not None or node.right is not None:
                has_more_nodes = True
        
        # 将节点的子节点添加到队列
        current_nodes = next_nodes

    raise NodeNotFoundError('node missing at index {}'.format(index))

这段代码主要用了队列（先进先出）的思想，广度优先遍历队列中每个节点验证其index，再将该节点的左右子节点加入队列，不断循环直到找到index所对应的节点或是遍历完整个二叉树都没有找到相应的节点（抛出异常）。

再看一下修改节点值的功能，如下：

>>>root = Node(1)
>>>root.left = Node(2)
>>>root.right = Node(3)
>>>root.left.left = Node(4)
>>>root[1] = Node(100)
>>>print(root)
   _1
  /  \
100   3

这个功能依靠__setitem__来实现：

def __setitem__(self, index, node):
    # 修改根节点时，报错
    if index == 0:
        raise NodeModifyError('cannot modify the root node')
    # 判断是否有父节点
    parent_index = (index - 1) // 2
    try:
        parent = self.__getitem__(parent_index)
    except NodeNotFoundError:
        raise NodeNotFoundError(
            'parent node missing at index {}'.format(parent_index))
    # 通过修改父节点的left, right属性来修改索引值
    setattr(parent, 'left' if index % 2 else 'right', node)

可以看到有两种情况会导致报错，一种是更改根节点（root[0]),另一种是更改不存在的节点（无父节点的节点）。

2.2 tree

通过binarytree中的tree可以随机创建指定高度的二叉树。

>>>my_tree = tree(height=3, is_perfect=False)
>>>print(my_tree)

          _____9_____
         /           \
    ____7___       ___11__
   /        \     /       \
  10        _2   8         4
 /  \      /      \       /
5    12   13       14    1

下面看一下源码：

def tree(height=3, is_perfect=False):
    _validate_tree_height(height)
    # 生成随机的节点值
    values = _generate_random_node_values(height)
    if is_perfect:
        return build(values)

    # 根据高度随机生成叶节点的数量
    leaf_count = _generate_random_leaf_count(height)
    root = Node(values.pop(0))
    leaves = set()

    for value in values:
        node = root
        depth = 0
        inserted = False

        while depth < height and not inserted:
            # 随机选择‘左右’子节点
            attr = random.choice(('left', 'right'))
            # 验证是否该节点的’左右‘子节点是否已添加
            if getattr(node, attr) is None:
                setattr(node, attr, Node(value))
                inserted = True
            node = getattr(node, attr)
            depth += 1
            
        # 到了二叉树的最下层，记录叶节点
        if inserted and depth == height:
            leaves.add(node)
        # 叶节点到了指定数量，退出循环
        if len(leaves) == leaf_count:
            break

    return root

从上述代码我们可以看到，当创建一个不完美(is_perfect =False)的指定高度的随机二叉树时，首先会随机生成叶节点的个数leaf_count，当叶节点个数到达此个数时，就跳出循环。

节点的添加也是自上而下，随机选择左右子节点，每当某个值的节点被插入后，就会将inserted标记为True，该值不会继续作为节点值被插入。

我们再来看一下创建一个'完美'随机二叉树(is_perfect =True)调用的代码：

def build(values):
    # 创建‘节点’列表
    nodes = [None if v is None else Node(v) for v in values]

    for index in range(1, len(nodes)):
        node = nodes[index]
        if node is not None:
            # 获取父节点索引
            parent_index = (index - 1) // 2
            parent = nodes[parent_index]
            if parent is None:
                raise NodeNotFoundError(
                    'parent node missing at index {}'.format(parent_index))
            setattr(parent, 'left' if index % 2 else 'right', node)

    return nodes[0] if nodes else None

按广度优先的顺序一一添加节点，非叶节点不存在为空的情况。

2.3 BST

通过binarytree中的bst以及is_bst可以轻松的创建和判断二叉搜索树。先简单看一下二叉搜索树的概念哦：每个节点的值都比左子节点的大，比右子节点的小。

看一下bst的使用哦。

>>>from binarytree import bst
>>>my_tree = bst(height=3, is_perfect=False)
>>>print(my_tree)

        ____8_____
       /          \
    __3__       ___11___
   /     \     /        \
  1       6   9         _13
 / \     /     \       /   \
0   2   5       10    12    14

源码如下：

def bst(height=3, is_perfect=False):
    _validate_tree_height(height)
    if is_perfect:
        return _generate_perfect_bst(height)

    values = _generate_random_node_values(height)
    leaf_count = _generate_random_leaf_count(height)

    root = Node(values.pop(0))
    leaves = set()

    for value in values:
        node = root
        depth = 0
        inserted = False

        while depth < height and not inserted:
            attr = 'left' if node.value > value else 'right'
            if getattr(node, attr) is None:
                setattr(node, attr, Node(value))
                inserted = True
            node = getattr(node, attr)
            depth += 1

        if inserted and depth == height:
            leaves.add(node)
        if len(leaves) == leaf_count:
            break

    return root

与2.2tree的创建的不同点就是，这里的attr不再随机生成，而是根据节点值的大小设定，然后根据attr来决定是插入成左子节点还是右子节点。

看一下perfect bst tree的创建哦：

def _generate_perfect_bst(height):
    max_node_count = 2 ** (height + 1) - 1
    node_values = list(range(max_node_count))
    return _build_bst_from_sorted_values(node_values)


def _build_bst_from_sorted_values(sorted_values):
    if len(sorted_values) == 0:
        return None
    mid_index = len(sorted_values) // 2
    root = Node(sorted_values[mid_index])
    root.left = _build_bst_from_sorted_values(sorted_values[:mid_index])
    root.right = _build_bst_from_sorted_values(sorted_values[mid_index + 1:])
    return root

感觉这段代码十分巧妙，首先在_generate_perfect_bst中生成有序数组，然后在_build_bst_from_sorted_value不断将中值以下的值和中值以上的值放入左右节点进行递归。

3. 二叉树属性源码解析

3.1 中序遍历

中序遍历的顺序是先左-再父-后右，看一下实现：

>>> 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.inorder
[Node(4), Node(2), Node(5), Node(1), Node(3)]

实现源码如下：

def inorder(self):
    node_stack = []
    result = []
    node = self

    while True:
        if node is not None:
            node_stack.append(node)
            # 取左
            node = node.left
        elif len(node_stack) > 0:
            # 弹出
            node = node_stack.pop()
            result.append(node)
            # 取右
            node = node.right
        else:
            break

    return result

这里用了压栈的方式实现了二叉树的中序遍历。

3.2 先序遍历

先序遍历的顺序是先父-再左-后右，看一下实现：

>>> 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.inorder
[Node(1), Node(2), Node(4), Node(5), Node(3)]

实现源码：

def preorder(self):
    node_stack = [self]
    result = []

    while len(node_stack) > 0:
        node = node_stack.pop()
        result.append(node)

        if node.right is not None:
            node_stack.append(node.right)
        if node.left is not None:
            node_stack.append(node.left)

    return result

同样适用栈实现，这里不做赘述。

3.3 后序遍历

后序遍历的顺序：先右-再左-后父，看一下实现：

>>> 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.inorder
[Node(4), Node(5), Node(2), Node(3), Node(1)]

实现源码：

def postorder(self):
    node_stack = []
    result = []
    node = self

    while True:
        while node is not None:
            if node.right is not None:
                node_stack.append(node.right)
            node_stack.append(node)
            node = node.left

        node = node_stack.pop()
        if (node.right is not None and
                    len(node_stack) > 0 and
                    node_stack[-1] is node.right):
            node_stack.pop()
            node_stack.append(node)
            node = node.right
        else:
            result.append(node)
            node = None

        if len(node_stack) == 0:
            break

    return result

3.4 平衡二叉树判断

平衡二叉树指的是任何节点左右子节点高度差不大于1的二叉树，这里可以通过is_balanced来判断：

>>> 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.is_balanced
True

看一下源码：

def _is_balanced(root):
    if root is None:
        return 0
    left = _is_balanced(root.left)
    if left < 0:
        return -1
    right = _is_balanced(root.right)
    if right < 0:
        return -1
    return -1 if abs(left - right) > 1 else max(left, right) + 1

def is_balanced(self):
    return _is_balanced(self) >= 0

这里使用了递归的方式来判断左右子节点的高度差并计算节点的高度，若发现某阶段左右子节点的高度差大于1则返回-1，表示不是平衡二叉树；否则会继续通过后序遍历的方式计算节点高度，直到计算出根节点的高度，此时若根节点的高度大于0，则该二叉树是平衡的。

binarytree库中的功能远远不止本文所述，跟着源码学习二叉树，还算是一种不错的体验～