1. binarytree 庫(kù)
1.1 運(yùn)行環(huán)境
Python 2.7, 3.4, 3.5 或 3.6
1.2 安裝方法
pip install binarytree
1.3 自動(dòng)構(gòu)建隨機(jī)二叉樹(shù)
>>> from binarytree import tree, bst, heap
>>>
>>> # 構(gòu)建節(jié)點(diǎn)隨機(jī)的二叉樹(shù)
>>> 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
>>> # 構(gòu)建隨機(jī)的二叉查找樹(shù)
>>> my_bst = bst(height=3, is_perfect=False)
>>> print(my_bst)
1______
/ \
0 __13
/ \
3 14
/ \
2 8
>>> # 構(gòu)建隨機(jī)最大/小堆二叉樹(shù)
>>> my_heap = heap(height=3, is_max=True, is_perfect=False)
>>> print(my_heat)
___14__
/ \
11 13
/ \ / \
6 8 5 7
/
0
1.4 手動(dòng)構(gòu)建二叉樹(shù)
>>> from binarytree import Node
>>> # 創(chuàng)建根節(jié)點(diǎn)
>>> root = Node(1)
>>> # 創(chuàng)建左節(jié)點(diǎn)
>>> root.left = Node(2)
>>> # 創(chuàng)建右節(jié)點(diǎn)
>>> root.right = Node(3)
>>> # 創(chuàng)建右節(jié)點(diǎn)的左節(jié)點(diǎn)
>>> root.right.left = Node(4)
1__
/ \
2 3
/
4
>>> # 取節(jié)點(diǎn)
>>> root[1]
Node(2)
>>> root[2]
Node(3)
1.5 查看二叉樹(shù)性質(zhì)
>>> 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. 二叉樹(shù)創(chuàng)建源碼解析
接下來(lái)就跟著binarytree的源碼更深入地學(xué)習(xí)使用python構(gòu)建二叉樹(shù)吧估蹄。
2.1 Node
看一下節(jié)點(diǎn)Node的源碼痹升，看到這里我慚愧了，要知道我自己創(chuàng)建的節(jié)點(diǎn)代碼只有5行...而binarytree庫(kù)中的Node代碼不算注釋與空格就有286行典蜕。
首先看一下它的初始化函數(shù)__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
這里限制了定義節(jié)點(diǎn)時(shí)断盛，它的值則必須是數(shù)字，且它的左右子節(jié)點(diǎn)為空或是Node類(lèi)的實(shí)例（默認(rèn)為空）愉舔。
再看一下設(shè)置屬性值時(shí)會(huì)調(diào)用的函數(shù)__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)
可以看到這里對(duì)設(shè)定的屬性值做了一下參數(shù)校驗(yàn)钢猛，隨后繼承了object的__setattr__。
1.4中的栗子說(shuō)到轩缤，通過(guò)Node添加好二叉樹(shù)后命迈，可以通過(guò)index去訪(fǎng)問(wèn)相應(yīng)節(jié)點(diǎn)，如下：
>>>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)
這個(gè)用法主要靠__getitem__實(shí)現(xiàn)火的，貼一下__getitem__的代碼：
def __getitem__(self, index):
if not isinstance(index, int) or index < 0:
raise NodeIndexError(
'node index must be a non-negative int')
# 進(jìn)行遍歷的序列
current_nodes = [self]
# 設(shè)置初始index
current_index = 0
# 設(shè)置未遍歷完的flag
has_more_nodes = True
while has_more_nodes:
has_more_nodes = False
next_nodes = []
# 遍歷隊(duì)列中的節(jié)點(diǎn)
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))
# 判斷是否有后續(xù)節(jié)點(diǎn)
if node.left is not None or node.right is not None:
has_more_nodes = True
# 將節(jié)點(diǎn)的子節(jié)點(diǎn)添加到隊(duì)列
current_nodes = next_nodes
raise NodeNotFoundError('node missing at index {}'.format(index))
這段代碼主要用了隊(duì)列（先進(jìn)先出）的思想，廣度優(yōu)先遍歷隊(duì)列中每個(gè)節(jié)點(diǎn)驗(yàn)證其index馏鹤，再將該節(jié)點(diǎn)的左右子節(jié)點(diǎn)加入隊(duì)列征椒，不斷循環(huán)直到找到index所對(duì)應(yīng)的節(jié)點(diǎn)或是遍歷完整個(gè)二叉樹(shù)都沒(méi)有找到相應(yīng)的節(jié)點(diǎn)（拋出異常）。
再看一下修改節(jié)點(diǎn)值的功能湃累，如下：
>>>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
這個(gè)功能依靠__setitem__來(lái)實(shí)現(xiàn)：
def __setitem__(self, index, node):
# 修改根節(jié)點(diǎn)時(shí)勃救，報(bào)錯(cuò)
if index == 0:
raise NodeModifyError('cannot modify the root node')
# 判斷是否有父節(jié)點(diǎn)
parent_index = (index - 1) // 2
try:
parent = self.__getitem__(parent_index)
except NodeNotFoundError:
raise NodeNotFoundError(
'parent node missing at index {}'.format(parent_index))
# 通過(guò)修改父節(jié)點(diǎn)的left, right屬性來(lái)修改索引值
setattr(parent, 'left' if index % 2 else 'right', node)
可以看到有兩種情況會(huì)導(dǎo)致報(bào)錯(cuò)，一種是更改根節(jié)點(diǎn)（root[0]),另一種是更改不存在的節(jié)點(diǎn)（無(wú)父節(jié)點(diǎn)的節(jié)點(diǎn)）治力。
2.2 tree
通過(guò)binarytree中的tree可以隨機(jī)創(chuàng)建指定高度的二叉樹(shù)蒙秒。
>>>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)
# 生成隨機(jī)的節(jié)點(diǎn)值
values = _generate_random_node_values(height)
if is_perfect:
return build(values)
# 根據(jù)高度隨機(jī)生成葉節(jié)點(diǎn)的數(shù)量
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:
# 隨機(jī)選擇‘左右’子節(jié)點(diǎn)
attr = random.choice(('left', 'right'))
# 驗(yàn)證是否該節(jié)點(diǎn)的’左右‘子節(jié)點(diǎn)是否已添加
if getattr(node, attr) is None:
setattr(node, attr, Node(value))
inserted = True
node = getattr(node, attr)
depth += 1
# 到了二叉樹(shù)的最下層，記錄葉節(jié)點(diǎn)
if inserted and depth == height:
leaves.add(node)
# 葉節(jié)點(diǎn)到了指定數(shù)量宵统，退出循環(huán)
if len(leaves) == leaf_count:
break
return root
從上述代碼我們可以看到晕讲，當(dāng)創(chuàng)建一個(gè)不完美(is_perfect =False)的指定高度的隨機(jī)二叉樹(shù)時(shí)，首先會(huì)隨機(jī)生成葉節(jié)點(diǎn)的個(gè)數(shù)leaf_count，當(dāng)葉節(jié)點(diǎn)個(gè)數(shù)到達(dá)此個(gè)數(shù)時(shí)瓢省，就跳出循環(huán)弄息。
節(jié)點(diǎn)的添加也是自上而下，隨機(jī)選擇左右子節(jié)點(diǎn)净捅，每當(dāng)某個(gè)值的節(jié)點(diǎn)被插入后疑枯，就會(huì)將inserted標(biāo)記為T(mén)rue，該值不會(huì)繼續(xù)作為節(jié)點(diǎn)值被插入蛔六。
我們?cè)賮?lái)看一下創(chuàng)建一個(gè)'完美'隨機(jī)二叉樹(shù)(is_perfect =True)調(diào)用的代碼：
def build(values):
# 創(chuàng)建‘節(jié)點(diǎn)’列表
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:
# 獲取父節(jié)點(diǎn)索引
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
按廣度優(yōu)先的順序一一添加節(jié)點(diǎn)荆永，非葉節(jié)點(diǎn)不存在為空的情況。
2.3 BST
通過(guò)binarytree中的bst以及is_bst可以輕松的創(chuàng)建和判斷二叉搜索樹(shù)国章。先簡(jiǎn)單看一下二叉搜索樹(shù)的概念哦：每個(gè)節(jié)點(diǎn)的值都比左子節(jié)點(diǎn)的大具钥，比右子節(jié)點(diǎn)的小。
看一下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的創(chuàng)建的不同點(diǎn)就是骂删，這里的attr不再隨機(jī)生成，而是根據(jù)節(jié)點(diǎn)值的大小設(shè)定四啰，然后根據(jù)attr來(lái)決定是插入成左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)宁玫。
看一下perfect bst tree的創(chuàng)建哦：
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
感覺(jué)這段代碼十分巧妙，首先在_generate_perfect_bst中生成有序數(shù)組柑晒，然后在_build_bst_from_sorted_value不斷將中值以下的值和中值以上的值放入左右節(jié)點(diǎn)進(jìn)行遞歸欧瘪。
3. 二叉樹(shù)屬性源碼解析
3.1 中序遍歷
中序遍歷的順序是先左-再父-后右，看一下實(shí)現(xiàn)：
>>> 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)]
實(shí)現(xiàn)源碼如下：
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
這里用了壓棧的方式實(shí)現(xiàn)了二叉樹(shù)的中序遍歷匙赞。
3.2 先序遍歷
先序遍歷的順序是先父-再左-后右佛掖，看一下實(shí)現(xiàn)：
>>> 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)]
實(shí)現(xiàn)源碼：
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
同樣適用棧實(shí)現(xiàn)，這里不做贅述涌庭。
3.3 后序遍歷
后序遍歷的順序：先右-再左-后父芥被，看一下實(shí)現(xiàn)：
>>> 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)]
實(shí)現(xiàn)源碼：
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 平衡二叉樹(shù)判斷
平衡二叉樹(shù)指的是任何節(jié)點(diǎn)左右子節(jié)點(diǎn)高度差不大于1的二叉樹(shù)，這里可以通過(guò)is_balanced來(lái)判斷：
>>> 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
這里使用了遞歸的方式來(lái)判斷左右子節(jié)點(diǎn)的高度差并計(jì)算節(jié)點(diǎn)的高度坐榆，若發(fā)現(xiàn)某階段左右子節(jié)點(diǎn)的高度差大于1則返回-1拴魄，表示不是平衡二叉樹(shù)；否則會(huì)繼續(xù)通過(guò)后序遍歷的方式計(jì)算節(jié)點(diǎn)高度席镀，直到計(jì)算出根節(jié)點(diǎn)的高度羹铅，此時(shí)若根節(jié)點(diǎn)的高度大于0，則該二叉樹(shù)是平衡的愉昆。
binarytree庫(kù)中的功能遠(yuǎn)遠(yuǎn)不止本文所述，跟著源碼學(xué)習(xí)二叉樹(shù)麻蹋，還算是一種不錯(cuò)的體驗(yàn)～
