Python初識(shí)二叉樹續(xù)之實(shí)戰(zhàn)binarytree
第三方庫(kù) binarytree
其使用環(huán)境、安裝方法及二叉樹的相關(guān)知識(shí)，請(qǐng)見：《Python 初識(shí)二叉樹，新手也秒懂！》
不能導(dǎo)入的請(qǐng)安裝：pip install binarytree
安裝好了就導(dǎo)入庫(kù)：import binarytree
主要的函數(shù)方法如下：
>>> import binarytree as bt >>> >>> bt.__all__ ['Node', 'tree', 'bst', 'heap', 'build', 'build2', 'get_parent', '__version__'] >>> >>> bt.__version__ '6.3.0' >>>
目前最新版本 V6.3.0，挑其中幾個(gè)來探究一下二叉樹的世界吧：
二叉樹節(jié)點(diǎn)函數(shù) Node()
函數(shù)原型：Node(NodeValue, LeftChildNode=None, LeftChildNode=None)
三個(gè)參數(shù)：NodeValue節(jié)點(diǎn)數(shù)值，必須為實(shí)數(shù)，int或float
LeftChildNode, LeftChildNode 左右子樹節(jié)點(diǎn)
通過創(chuàng)建節(jié)點(diǎn)，生成一棵3層的滿二叉樹：
>>> from binarytree import Node
>>>
>>> bt = Node(1)
>>>
>>> bt.left = Node(2)
>>> bt.right = Node(3)
>>>
>>> bt.left.left = Node(4)
>>> bt.left.right = Node(5)
>>> bt.right.left = Node(6)
>>> bt.right.right = Node(7)
>>>
>>> bt.pprint()
__1__
/ \
2 3
/ \ / \
4 5 6 7
>>> 如果要建很多層的滿二叉樹，用Node()逐個(gè)賦值有點(diǎn)麻煩。比如到第四層要給8個(gè)葉子賦值：
>>> bt.left.left.left = Node(8)
>>> bt.left.right.left = Node(10)
>>> bt.right.left.left = Node(12)
>>> bt.right.right.left = Node(14)
>>> bt.left.left.right = Node(9)
>>> bt.left.right.right = Node(11)
>>> bt.right.left.right = Node(13)
>>> bt.right.right.right = Node(15)
每多一層葉子數(shù)就翻一倍，為了方便我想到用exec()函數(shù)把字符串轉(zhuǎn)成變量操作賦值的方法予以簡(jiǎn)化代碼。自定義函數(shù) createPerfectTree(intTreeLevels, listTreeData)，參數(shù)為需要指定的層數(shù)和節(jié)點(diǎn)賦值數(shù)據(jù)，分別是整數(shù)和列表類型；函數(shù)返回值為一個(gè)滿二叉樹。代碼如下：
from binarytree import Node
def createPerfectTree(intTreeLevels, listTreeData):
if len(listTreeData)+1<2**intTreeLevels or intTreeLevels<1:
return None
t,tmp = ['root'],[]
data = listTreeData[::-1]
root = Node(data[-1])
data.pop()
for j in range(intTreeLevels-1):
for i in t:
exec(i + f'.left=Node({data[-1]})')
data.pop()
exec(i + f'.right=Node({data[-1]})')
data.pop()
tmp.append(i + '.left')
tmp.append(i + '.right')
t=tmp[:]
tmp=[]
return root
# 打印各節(jié)點(diǎn)值為整數(shù)序列的滿二叉樹（0~6層）
for i in range(7):
data = [*range(1,2**i)]
print(createPerfectTree(i, data))
# 用指定列表的數(shù)據(jù)，創(chuàng)建滿二叉樹
data = [15,0,7,2,6,4,3,1,5,6,7,9,34,23,8]
print(createPerfectTree(3, data))
print(createPerfectTree(4, data))
print(createPerfectTree(5, data)) # data長(zhǎng)度不夠返回:None
# 賦值后列印
root = createPerfectTree(4, [*range(1,2**4)])
print(root)運(yùn)行結(jié)果：
None
1
1
/ \
2 3
__1__
/ \
2 3
/ \ / \
4 5 6 7
________1________
/ \
__2___ ___3___
/ \ / \
4 _5 _6 _7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
____________________1____________________
/ \
________2_________ _________3_________
/ \ / \
___4___ ____5___ ____6___ ____7___
/ \ / \ / \ / \
_8 _9 _10 _11 _12 _13 _14 _15
/ \ / \ / \ / \ / \ / \ / \ / \
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
____________________________________________1____________________________________________
/ \
____________________2_____________________ _____________________3_____________________
/ \ / \
_________4_________ __________5_________ __________6_________ __________7_________
/ \ / \ / \ / \
____8___ ____9___ ____10___ ____11___ ____12___ ____13___ ____14___ ____15___
/ \ / \ / \ / \ / \ / \ / \ / \
_16 _17 _18 _19 _20 _21 _22 _23 _24 _25 _26 _27 _28 _29 _30 _31
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
__15__
/ \
0 7
/ \ / \
2 6 4 3
______15_______
/ \
__0__ ___7___
/ \ / \
2 6 4 _3
/ \ / \ / \ / \
1 5 6 7 9 34 23 8
None
________1________
/ \
__2___ ___3___
/ \ / \
4 _5 _6 _7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
嵌套創(chuàng)建節(jié)點(diǎn)，順便判斷對(duì)稱性。得到一個(gè)結(jié)論：屬性.is_symmetric判斷的對(duì)稱是指鏡像對(duì)稱，不是根節(jié)點(diǎn)的左右子樹要完全相等，而是要鏡面反向才返回 True。
>>> from binarytree import Node
>>> a=Node(1,Node(2,Node(3),Node(4)),Node(2,Node(3),Node(4)))
>>> a.pprint()
__1__
/ \
2 2
/ \ / \
3 4 3 4
>>> b=Node(1,Node(2,Node(3),Node(4)),Node(2,Node(4),Node(3)))
>>> b.pprint()
__1__
/ \
2 2
/ \ / \
3 4 4 3
>>> a.is_symmetric
False
>>> b.is_symmetric
True
>>> 二叉樹的方法與屬性
1. 列印方法bt.pprint() 等同于print(bt)
# 以下所有舉例皆用上面代碼中的 root 滿二叉樹：
>>> root
Node(1)
>>> root.pprint()
________1________
/ \
__2___ ___3___
/ \ / \
4 _5 _6 _7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
# 等同于 print(root)
>>> root.right.pprint()
___3___
/ \
_6 _7
/ \ / \
12 13 14 15
>>> root.left.right.pprint()
_5
/ \
10 11
>>> print(root.left.left)
4
/ \
8 9
>>> 2. 判斷類屬性，判斷二叉樹是否平衡、嚴(yán)格、對(duì)稱、完全、完美，是否為最大(小)堆、搜索樹等
對(duì)稱是指根節(jié)點(diǎn)的左右子樹呈鏡像對(duì)稱；嚴(yán)格是指除葉子外所有節(jié)點(diǎn)都有左右兩個(gè)節(jié)點(diǎn)。
>>> 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 True >>> root.is_strict True >>> root.is_symmetric False >>>
3. 數(shù)量數(shù)值類屬性
>>> root.left Node(2) >>> root.right Node(3) >>> root.val 1 >>> root.value 1 >>> root.values [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] >>> root.values2 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] >>> root.left.value 2 >>> root.right.left.value 6 >>> root.max_node_value 15 >>> root.min_node_value 1 >>> root.max_leaf_depth 3 >>> root.min_leaf_depth 3 >>> root.levels [[Node(1)], [Node(2), Node(3)], [Node(4), Node(5), Node(6), Node(7)], [Node(8), Node(9), Node(10), Node(11), Node(12), Node(13), Node(14), Node(15)]] >>> len(root.levels) # == height + 1 4 >>> root.height 3 >>> root.leaves [Node(8), Node(9), Node(10), Node(11), Node(12), Node(13), Node(14), Node(15)] >>> len(root.leaves) 8 >>> root.leaf_count 8 >>>
注： val和value等價(jià)，values和values2差別在于如有多個(gè)連續(xù)空節(jié)點(diǎn)時(shí)后者只返回一個(gè)None
4. 屬性字典，打包了上面兩大類屬性中的一部分放在一個(gè)字典里
>>> root.properties
{'height': 3,
'size': 15,
'is_max_heap': False,
'is_min_heap': True,
'is_perfect': True,
'is_strict': True,
'is_complete': True,
'leaf_count': 8,
'min_node_value': 1,
'max_node_value': 15,
'min_leaf_depth': 3,
'max_leaf_depth': 3,
'is_balanced': True,
'is_bst': False,
'is_symmetric': False
}5. 遍歷類
>>> root.preorder [Node(1), Node(2), Node(4), Node(8), Node(9), Node(5), Node(10), Node(11), Node(3), Node(6), Node(12), Node(13), Node(7), Node(14), Node(15)] >>> root.inorder [Node(8), Node(4), Node(9), Node(2), Node(10), Node(5), Node(11), Node(1), Node(12), Node(6), Node(13), Node(3), Node(14), Node(7), Node(15)] >>> root.postorder [Node(8), Node(9), Node(4), Node(10), Node(11), Node(5), Node(2), Node(12), Node(13), Node(6), Node(14), Node(15), Node(7), Node(3), Node(1)] >>> root.levelorder [Node(1), Node(2), Node(3), Node(4), Node(5), Node(6), Node(7), Node(8), Node(9), Node(10), Node(11), Node(12), Node(13), Node(14), Node(15)] >>> >>> root.left.levelorder [Node(2), Node(4), Node(5), Node(8), Node(9), Node(10), Node(11)] >>> root.right.left.preorder [Node(6), Node(12), Node(13)] >>>
6. .svg() 二叉樹的矢量圖
>>> root.svg()
'\n<svg width="384" height="240" xmlns="http://www.w3.org/2000/svg">\n<style>
\n .value {\n font: 300 16px sans-serif;\n text-align: center;
\n dominant-baseline: middle;\n text-anchor: middle;\n }
\n .node {\n fill: lightgray;\n stroke-width: 1;\n }
\n</style>\n<g stroke="#000000">\n ...... ...... 略去N行
>>>
>>> f = open('d:\\myBiTree.svg','w')
>>> f.write(root.svg())
2434
>>> f.close()
>>> 可以輸出后綴為.svg 的文本文件，一種矢量圖的超文本表達(dá)文件，大部分瀏覽器可以直接查看；也可下載 Inkscape 等軟件來編輯。輸出效果如下：
7. .clone() 克隆一棵二叉樹的全部或者部分
>>> from binarytree import tree
>>> a = tree()
>>> a.pprint()
____13______
/ \
____2 __14
/ \ / \
12 0 6 11
\ \ / \ \
10 4 8 9 3
>>> b = a.clone()
>>> b.pprint()
____13______
/ \
____2 __14
/ \ / \
12 0 6 11
\ \ / \ \
10 4 8 9 3
>>> c = b.right.clone()
>>> c.pprint()
__14
/ \
6 11
/ \ \
8 9 3
>>> 8. .validate() 判斷二叉樹是否有效，正常返回None，有三種情況會(huì)拋出相應(yīng)錯(cuò)誤：
NodeTypeError: 如果節(jié)點(diǎn)不是Node(i)
NodeValueError: 如果節(jié)點(diǎn)值不是數(shù)字，如Node(i)中的參數(shù)i不為int或float
noderReferenceError: 如果二叉樹中存在對(duì)節(jié)點(diǎn)的循環(huán)引用
隨機(jī)二叉樹函數(shù) tree()
指定層數(shù)，隨機(jī)創(chuàng)建一棵二叉樹。
函數(shù)原型：tree(height: int = 3, is_perfect: bool = False)
兩個(gè)參數(shù)：層數(shù)height, 范圍 0 ~ 9，最多創(chuàng)建 9 層，缺省值 3
是否滿二叉樹is_perfect，缺省值False，即非滿二叉樹
創(chuàng)建幾個(gè)隨機(jī)二叉樹吧：
>>> import binarytree as bt
>>> a=bt.tree()
>>> a.pprint()
_8____
/ \
10 __3___
/ / \
7 4 _6
/ \ / \
1 9 12 14
>>> b=bt.tree(4)
>>> b.pprint()
____________8______
/ \
______30________ ____4__
/ \ / \
____5___ ___17 10 1___
/ \ / \ / \
_22 _28 _7 19 0 _6
/ \ / / \ /
20 12 18 23 15 13
>>> c=bt.tree(is_perfect=True)
>>> c.pprint()
_______12______
/ \
____2___ __14__
/ \ / \
13 _0 5 6
/ \ / \ / \ / \
8 11 10 9 7 3 1 4
>>> a.height,b.height,c.height
(3, 4, 3)
>>> a.levels
[[Node(8)],
[Node(10), Node(3)],
[Node(7), Node(4), Node(6)],
[Node(1), Node(9), Node(12), Node(14)]
]
>>> len(a.levels)
4
>>> # 注意： 層數(shù)levels = .height + 1創(chuàng)建一個(gè)3層隨機(jī)的滿二叉樹，再用正整數(shù)序列賦值到每個(gè)節(jié)點(diǎn)
>>> from binarytree import tree
>>> root = tree(is_perfect=True)
>>> root.pprint()
________5________
/ \
__9___ ____12__
/ \ / \
0 _13 11 4
/ \ / \ / \ / \
1 6 10 2 3 14 8 7
>>> tmpAssign = [exec(f'root[{i-1}].val={i}') for i in range(1,16)]
>>> root.pprint()
________1________
/ \
__2___ ___3___
/ \ / \
4 _5 _6 _7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
>>> [i.value for i in root]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> root[0],root[0].value
(Node(1), 1)
>>> root[1],root[1].value
(Node(2), 2)
>>> root[2];root[2].value
Node(3)
3
>>> root[14];root[14].value
Node(15)
15
>>> 或者其它層數(shù)的：
import binarytree as bt
Levels = 3
t = bt.tree(Levels-1, is_perfect=True)
for i in range(2**Levels-1):
t[i].val = i+1
t.pprint()
L = 4
a = bt.tree(L-1, is_perfect=True)
lst = [*range(1,2**L)]
for i,n in enumerate(lst):
a[i].val = n
a.pprint()
L = 5
b = bt.tree(L-1, is_perfect=True)
for i,n in enumerate([*range(1,len(b)+1)]):
b[i].val = n
b.pprint()
'''
__1__
/ \
2 3
/ \ / \
4 5 6 7
________1________
/ \
__2___ ___3___
/ \ / \
4 _5 _6 _7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
____________________1____________________
/ \
________2_________ _________3_________
/ \ / \
___4___ ____5___ ____6___ ____7___
/ \ / \ / \ / \
_8 _9 _10 _11 _12 _13 _14 _15
/ \ / \ / \ / \ / \ / \ / \ / \
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
'''給滿二叉樹“仿房間號(hào)”賦值：
import binarytree as bt
Level = 6
t = bt.tree(Level-1, is_perfect=True)
for i in range(Level):
for j in range(2**i):
n = 2
#n = len(str(2**i))+1
t[2**i+j-1].val=(i+1)*10**n+j+1
t.pprint()
'''
_____________________________________________________________101_____________________________________________________________
/ \
_____________________________201_____________________________ _____________________________202_____________________________
/ \ / \
_____________301_____________ _____________302_____________ _____________303_____________ _____________304_____________
/ \ / \ / \ / \
_____401_____ _____402_____ _____403_____ _____404_____ _____405_____ _____406_____ _____407_____ _____408_____
/ \ / \ / \ / \ / \ / \ / \ / \
_501_ _502_ _503_ _504_ _505_ _506_ _507_ _508_ _509_ _510_ _511_ _512_ _513_ _514_ _515_ _516_
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632
'''用指定列表賦值給滿二叉樹：
>>> from binarytree import tree
>>> data = [15,0,7,2,6,4,3,1,5,6,7,9,34,23,8]
>>> root = tree(is_perfect=True)
>>> root.pprint()
_______10______
/ \
___8___ __12___
/ \ / \
14 _1 4 _3
/ \ / \ / \ / \
5 2 13 9 0 6 11 7
>>> tmpAssign = [exec(f'root[{i}].val={n}') for i,n in enumerate(data)]
>>> root.pprint()
______15_______
/ \
__0__ ___7___
/ \ / \
2 6 4 _3
/ \ / \ / \ / \
1 5 6 7 9 34 23 8
>>> [i.value for i in root] == data
True
>>> 給非滿二叉樹賦值：
>>> from binarytree import tree
>>> root = tree()
>>> root.pprint()
_________13__
/ \
14__ 3__
\ / \
11 9 0
/ \ / \
5 10 2 6
>>> [exec(f'root[{i}].val={n}') for i,n in enumerate([*range(1,16)])]
Traceback (most recent call last):
File "<pyshell#237>", line 1, in <module>
[exec(f'root[{i}].val={n}') for i,n in enumerate([*range(1,16)])]
File "<pyshell#237>", line 1, in <listcomp>
[exec(f'root[{i}].val={n}') for i,n in enumerate([*range(1,16)])]
File "<string>", line 1, in <module>
File "D:\Python38-32\lib\site-packages\binarytree\__init__.py", line 350, in __getitem__
raise NodeNotFoundError("node missing at index {}".format(index))
binarytree.exceptions.NodeNotFoundError: node missing at index 3
>>> root[2]
Node(3)
>>> root[3]
Traceback (most recent call last):
File "<pyshell#238>", line 1, in <module>
root[3]
File "D:\Python38-32\lib\site-packages\binarytree\__init__.py", line 350, in __getitem__
raise NodeNotFoundError("node missing at index {}".format(index))
binarytree.exceptions.NodeNotFoundError: node missing at index 3
>>> root[4]
Node(11)
>>> 使用上面用到過的辦法來“依葫蘆畫瓢”，結(jié)果程序出錯(cuò)。
原因在于：非滿二叉樹相對(duì)于滿二叉樹“缺失”的節(jié)點(diǎn)索引號(hào)是跳空的。
正如上面的測(cè)試所示：root[2],root[4]之間的 root[3]并不存在。代碼修改如下：
>>> from binarytree import tree
>>> root = tree()
>>> root.pprint()
______5__
/ \
13___ 0__
/ \ / \
_3 _6 7 12
/ / / \
10 14 9 2
>>> 15 - len(root)
4 # 比滿樹少4個(gè)節(jié)點(diǎn)
>>> for i in range(15):
try:
root[i].val=i+1
except:
pass
>>> root.pprint()
_____1__
/ \
2___ 3___
/ \ / \
4 _5 6 _7
/ / / \
8 10 14 15
>>> # 跳空：9 11 12 13
>>> 續(xù)上面的節(jié)點(diǎn)結(jié)構(gòu)，重新賦值使得層序遍歷出的數(shù)值連續(xù)：
>>> t = 0
>>> for i in range(15):
try:
t+=1
root[i].val=t
except:
t-=1
>>> root.pprint()
____1__
/ \
2__ 3___
/ \ / \
4 5 6 _7
/ / / \
8 9 10 11
>>> [i.value for i in root]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> root.levelorder
[Node(1), Node(2), Node(3), Node(4), Node(5), Node(6),
Node(7), Node(8), Node(9), Node(10), Node(11)]
>>> 用列表創(chuàng)建二叉樹的函數(shù) build()
函數(shù)原型：build(values: List[Union[float, int]])
一個(gè)參數(shù)：實(shí)數(shù)組成的列表
上面操練Node()，tree()函數(shù)時(shí)，都練習(xí)過用指定列表給二叉樹賦值。那只是為了操練而操練的，因?yàn)橛胋uild()函數(shù)非常方便，一步到位：
>>> from binarytree import build
>>> root = build([*range(1,16)])
>>> root.pprint()
________1________
/ \
__2___ ___3___
/ \ / \
4 _5 _6 _7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
>>> 列表元素個(gè)數(shù)少于節(jié)點(diǎn)數(shù)時(shí)，后面的葉子自動(dòng)為空：
>>> from binarytree import build
>>> root = build([*range(1,10)])
>>> root.pprint()
__1__
/ \
__2 3
/ \ / \
4 5 6 7
/ \
8 9
>>> 樹中間的節(jié)點(diǎn)為空，只要把列表對(duì)應(yīng)的元素置為None：
>>> from binarytree import build
>>> data = [15,0,7,2,6,4,None,1,5,8,9,None,10]
>>> root = build(data)
>>> root.pprint()
______15_____
/ \
__0__ ___7
/ \ /
2 6 4
/ \ / \ \
1 5 8 9 10
>>> 注：給定列表的0號(hào)索引的元素一定不能為空，根節(jié)點(diǎn)為空列表之后元素將無處安放。另外已經(jīng)置空的節(jié)點(diǎn)下的對(duì)應(yīng)索引號(hào)也要置為None，如上面的root根節(jié)點(diǎn)下沒 root.right.right 節(jié)點(diǎn)的， 所以如果要給data增加非None元素的話，程序也會(huì)出錯(cuò)。測(cè)試代碼如下：
>>> from binarytree import build
>>> data = [15,0,7,2,6,4,None,1,5,8,9,None,10] + [3]
>>> build(data)
Traceback (most recent call last):
File "<pyshell#7>", line 1, in <module>
build(data)
File "D:\Python\lib\site-packages\binarytree\__init__.py", line 2132, in build
raise NodeNotFoundError(
binarytree.exceptions.NodeNotFoundError: parent node missing at index 6
>>>
>>> # 正確的元素添加，如下： 空索引的地方相應(yīng)插入None
>>>
>>> data = [15,0,7,2,6,4,None,1,5,8,9,None,10]
>>> data += [None,None,3,11,12,13,14,16,17,18,None,None,19,20]
>>> root = build(data)
>>> root.pprint()
__________________15___________
/ \
________0________ _________7
/ \ /
___2___ ___6___ 4___
/ \ / \ \
1 _5 _8 _9 _10
/ \ / \ / \ / \ / \
3 11 12 13 14 16 17 18 19 20
>>> build2()
用法基本與build()相同，但它的參數(shù)允許更緊湊的列表，因?yàn)樗耐粚庸?jié)點(diǎn)中如果最后連續(xù)為空只要一個(gè)“None”。兩者的區(qū)別有點(diǎn)像上面在二叉樹方法屬性一節(jié)里提到的(已紅色標(biāo)注)：values 和 values2的區(qū)別。請(qǐng)看如下測(cè)試代碼：
>>> root1 = build([2, 5, None,3,None,None, None, 1, 4])
>>> root1.pprint()
2
/
__5
/
3
/ \
1 4
>>> # build()能用的列表，build2()不一定通用：
>>> root1 = build2([2, 5, None,3,None,None, None, 1, 4])
Traceback (most recent call last):
File "<pyshell#10>", line 1, in <module>
root1 = build2([2, 5, None,3,None,None, None, 1, 4])
File "D:\Python\lib\site-packages\binarytree\__init__.py", line 2194, in build2
node = queue.popleft()
IndexError: pop from an empty deque
>>>
>>> # build2()正確的列表參數(shù)：
>>> root2 = build2([2, 5, None,3,None, 1, 4])
>>> root2.pprint()
2
/
__5
/
3
/ \
1 4
>>> bst() heap()
用法基本上與 tree() 相同，參數(shù)也是：層數(shù)（0~9）； is_perfect = False(默認(rèn)值)
返回值：分別是特殊的二叉樹 bst 和 heap；另heap()多一個(gè)參數(shù) is_max = True(默認(rèn)值)
>>> from binarytree import bst
>>> root = bst()
>>> root.height
3
>>> root.is_bst
True
>>> root.pprint()
10______
/ \
__8 ____14
/ /
6 12
/ \ \
4 7 13
>>>
>>> from binarytree import heap
>>> root = heap()
>>> root.height
3
>>> root.is_max_heap
True
>>> root.pprint()
________14____
/ \
__12__ 11
/ \ / \
8 10 3 9
/ \ / \ /
0 4 6 1 2
>>>
>>> root = heap(4, is_max=False)
>>> root.height
4
>>> root.is_min_heap
True
>>>
>>> root = heap(5, is_max=False, is_perfect=True)
>>> root.height
5
>>> root.is_min_heap
True
>>> root.is_perfect
Truetree() 也能造出bst 和 heap 來，只是用循環(huán)來多花點(diǎn)時(shí)間：
>>> from binarytree import bst, heap
>>> bst1 = tree()
>>> while not bst1.is_bst:
bst1 = tree()
>>> bst1.pprint()
1____
\
__14
/
2
\
5
>>> heap1 = tree()
>>> while not heap1.is_max_heap:
heap1 = tree()
>>> heap1.pprint()
________14_____
/ \
__12__ _13
/ \ / \
6 10 11 3
/ \ / \ /
2 0 1 4 9
>>> heap2 = tree()
>>> while not heap2.is_min_heap:
heap2 = tree()
>>> heap2.pprint()
________0___
/ \
__3___ _1
/ \ / \
7 _4 11 2
/ \ / \
9 8 10 13
>>> 獲取雙親節(jié)點(diǎn)函數(shù) get_parent()
get_parent(root: binarytree.Node, child: binarytree.Node)
給定子節(jié)點(diǎn)，返回它在根節(jié)點(diǎn)下的上一層級(jí)的節(jié)點(diǎn)
>>> from binarytree import tree, get_parent
>>> root = tree()
>>> print(root)
______8__
/ \
7 1
/ \ /
6 10 5
/ \
9 11
>>> print(get_parent(root,root.left.left))
7
/ \
6 10
/ \
9 11
>>> get_parent(root,root.left.left) == get_parent(root,root.left.right)
True
>>> 總結(jié)
到此這篇關(guān)于Python初識(shí)二叉樹續(xù)之實(shí)戰(zhàn)binarytree的文章就介紹到這了,更多相關(guān)Python實(shí)戰(zhàn)binarytree內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹的建立實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹的遍歷實(shí)例
- Python中的二叉樹查找算法模塊使用指南
- Python利用前序和中序遍歷結(jié)果重建二叉樹的方法
- python數(shù)據(jù)結(jié)構(gòu)樹和二叉樹簡(jiǎn)介
- python二叉樹遍歷的實(shí)現(xiàn)方法
- python二叉樹的實(shí)現(xiàn)實(shí)例
- Python實(shí)現(xiàn)重建二叉樹的三種方法詳解
- Python簡(jiǎn)單定義與使用二叉樹示例
- python實(shí)現(xiàn)的二叉樹定義與遍歷算法實(shí)例
相關(guān)文章
今天小編就為大家分享一篇pytorch常見的Tensor類型詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-01-01
當(dāng)你需要在長(zhǎng)文檔或報(bào)告中快速找到特定的關(guān)鍵詞或短語(yǔ),Word中提供的查找并高亮這一功能可以幫助你迅速定位這些內(nèi)容,本文將介紹如何使用Python在Word中查找并突出顯示指定的文本,需要的朋友可以參考下2024-03-03
Python一行代碼快速實(shí)現(xiàn)程序進(jìn)度條示例
這篇文章主要為大家介紹了Python一行代碼快速實(shí)現(xiàn)程序進(jìn)度條示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-03-03
一文教會(huì)你使用win10實(shí)現(xiàn)電腦的定時(shí)任務(wù)執(zhí)行
這篇文章主要介紹了一文教會(huì)你使用win10實(shí)現(xiàn)電腦的定時(shí)任務(wù)執(zhí)行,利用Windows任務(wù)計(jì)劃程序創(chuàng)建定時(shí)執(zhí)行自定義腳本的步驟,包括配置環(huán)境、編寫腳本、新建任務(wù)文件夾、設(shè)置觸發(fā)器、編輯任務(wù)信息以及手動(dòng)運(yùn)行測(cè)試,需要的朋友可以參考下2024-09-09
python爬蟲實(shí)戰(zhàn)之爬取京東商城實(shí)例教程
這篇文章主要介紹了python爬取京東商城的相關(guān)資料，文中通過爬取一個(gè)實(shí)例頁(yè)面進(jìn)行了講解，通過示例代碼和圖文介紹的非常詳細(xì)，相信對(duì)大家具有一定的參考價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧。2017-04-04
Django之使用內(nèi)置函數(shù)和celery發(fā)郵件的方法示例
這篇文章主要介紹了Django之使用內(nèi)置函數(shù)和celery發(fā)郵件的方法示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
python解析網(wǎng)頁(yè)上的json數(shù)據(jù)并保存到EXCEL
這篇文章主要為大家詳細(xì)介紹了如何使用python解析網(wǎng)頁(yè)上的json數(shù)據(jù)并保存到EXCEL,文中的示例代碼講解詳細(xì),感興趣的可以了解下2024-11-11
Python推導(dǎo)式是一種獨(dú)特的數(shù)據(jù)處理方式,可以從一個(gè)數(shù)據(jù)序列構(gòu)建另一個(gè)新的數(shù)據(jù)序列的結(jié)構(gòu)體,下面這篇文章主要給大家介紹了關(guān)于Python小知識(shí)之幾種推導(dǎo)式用法的相關(guān)資料,需要的朋友可以參考下2023-01-01
python數(shù)據(jù)結(jié)構(gòu)之二叉樹的建立實(shí)例
這篇文章主要介紹了python數(shù)據(jù)結(jié)構(gòu)之二叉樹的建立實(shí)例,采用了類似遞歸方式建立,需要的朋友可以參考下2014-04-04
python中文分詞,使用結(jié)巴分詞對(duì)python進(jìn)行分詞(實(shí)例講解)
下面小編就為大家?guī)硪黄猵ython中文分詞,使用結(jié)巴分詞對(duì)python進(jìn)行分詞的實(shí)例講解。有比較好的參考價(jià)值，希望能給大家做個(gè)參考。一起跟隨小編過來看看吧2017-11-11