首頁 > 軟體

Python初識二元樹續之實戰binarytree

2022-05-27 14:02:27

第三方庫 binarytree

其使用環境、安裝方法及二元樹的相關知識,請見:《Python 初識二元樹,新手也秒懂!

不能匯入的請安裝:pip install binarytree

安裝好了就匯入庫:import binarytree

主要的函數方法如下:

>>> import binarytree as bt
>>> 
>>> bt.__all__
['Node', 'tree', 'bst', 'heap', 'build', 'build2', 'get_parent', '__version__']
>>> 
>>> bt.__version__
'6.3.0'
>>> 

目前最新版本 V6.3.0,挑其中幾個來探究一下二元樹的世界吧:

二元樹節點函數 Node()

函數原型:Node(NodeValue, LeftChildNode=None, LeftChildNode=None)

三個引數:NodeValue節點數值,必須為實數,int或float

     LeftChildNode, LeftChildNode 左右子樹節點

通過建立節點,生成一棵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()逐個賦值有點麻煩。比如到第四層要給8個葉子賦值:

>>> 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)

每多一層葉子數就翻一倍,為了方便我想到用exec()函數把字串轉成變數操作賦值的方法予以簡化程式碼。自定義函數 createPerfectTree(intTreeLevels, listTreeData),引數為需要指定的層數和節點賦值資料,分別是整數和列表型別;函數返回值為一個滿二元樹。程式碼如下:

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
 
# 列印各節點值為整數序列的滿二元樹(0~6層)
for i in range(7):
    data = [*range(1,2**i)]
    print(createPerfectTree(i, data))
 
# 用指定列表的資料,建立滿二元樹
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長度不夠返回:None
 
# 賦值後列印
root = createPerfectTree(4, [*range(1,2**4)])
print(root)

執行結果:

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

巢狀建立節點,順便判斷對稱性。得到一個結論:屬性.is_symmetric判斷的對稱是指映象對稱,不是根節點的左右子樹要完全相等,而是要鏡面反向才返回 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. 判斷類屬性,判斷二元樹是否平衡、嚴格、對稱、完全、完美,是否為最大(小)堆、搜尋樹等

對稱是指根節點的左右子樹呈映象對稱;嚴格是指除葉子外所有節點都有左右兩個節點。

>>> 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. 數量數值類屬性

>>> 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等價,values和values2差別在於如有多個連續空節點時後者只返回一個None 

4. 屬性字典,打包了上面兩大類屬性中的一部分放在一個字典裡

>>> 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 的文字檔案,一種向量圖的超文字表達檔案,大部分瀏覽器可以直接檢視;也可下載 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,有三種情況會丟擲相應錯誤:

NodeTypeError: 如果節點不是Node(i)

NodeValueError: 如果節點值不是數位,如Node(i)中的引數i不為int或float

noderReferenceError: 如果二元樹中存在對節點的迴圈參照

隨機二元樹函數 tree()

指定層數,隨機建立一棵二元樹。

函數原型:tree(height: int = 3, is_perfect: bool = False) 

兩個引數:層數height, 範圍 0 ~ 9,最多建立 9 層,預設值 3

     是否滿二元樹is_perfect,預設值False,即非滿二元樹

建立幾個隨機二元樹吧:

>>> 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
>>> # 注意: 層數levels = .height + 1

建立一個3層隨機的滿二元樹,再用正整數序列賦值到每個節點

>>> 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
>>> 

或者其它層數的:

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
'''

給滿二元樹“仿房間號”賦值:

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-32libsite-packagesbinarytree__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-32libsite-packagesbinarytree__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)
>>> 

使用上面用到過的辦法來“依葫蘆畫瓢”,結果程式出錯。

原因在於:非滿二元樹相對於滿二元樹“缺失”的節點索引號是跳空的。

正如上面的測試所示: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個節點
>>> 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
>>> 

續上面的節點結構,重新賦值使得層序遍歷出的數值連續:

>>> 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)]
>>> 

用列表建立二元樹的函數 build()

函數原型:build(values: List[Union[float, int]])

一個引數:實陣列成的列表

上面操練Node(),tree()函數時,都練習過用指定列表給二元樹賦值。那只是為了操練而操練的,因為用build()函數非常方便,一步到位:

>>> 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
 
>>> 

列表元素個數少於節點數時,後面的葉子自動為空:

>>> from binarytree import build
>>> root = build([*range(1,10)])
>>> root.pprint()
 
        __1__
       /     
    __2       3
   /        / 
  4     5   6   7
 / 
8   9
 
>>> 

樹中間的節點為空,只要把列表對應的元素置為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號索引的元素一定不能為空,根節點為空列表之後元素將無處安放。另外已經置空的節點下的對應索引號也要置為None,如上面的root根節點下沒 root.right.right 節點的, 所以如果要給data增加非None元素的話,程式也會出錯。測試程式碼如下:

>>> 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:Pythonlibsite-packagesbinarytree__init__.py", line 2132, in build
    raise NodeNotFoundError(
binarytree.exceptions.NodeNotFoundError: parent node missing at index 6
>>>
>>> # 正確的元素新增,如下: 空索引的地方相應插入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()相同,但它的引數允許更緊湊的列表,因為它的同一層節點中如果最後連續為空只要一個“None”。兩者的區別有點像上面在二元樹方法屬性一節裡提到的(已紅色標註):values 和 values2的區別。請看如下測試程式碼:

>>> 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:Pythonlibsite-packagesbinarytree__init__.py", line 2194, in build2
    node = queue.popleft()
IndexError: pop from an empty deque
>>>
>>> # build2()正確的列表引數:
>>> root2 = build2([2, 5, None,3,None, 1, 4])
>>> root2.pprint()
 
        2
       /
    __5
   /
  3
 / 
1   4
 
>>> 

bst() heap()

用法基本上與 tree() 相同,引數也是:層數(0~9); is_perfect = False(預設值)
返回值:分別是特殊的二元樹 bst 和 heap;另heap()多一個引數 is_max = True(預設值)

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

tree() 也能造出bst 和 heap 來,只是用迴圈來多花點時間:

>>> 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
 
>>> 

獲取雙親節點函數 get_parent()

get_parent(root: binarytree.Node, child: binarytree.Node)

給定子節點,返回它在根節點下的上一層級的節點

>>> 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
>>> 

總結

到此這篇關於Python初識二元樹續之實戰binarytree的文章就介紹到這了,更多相關Python實戰binarytree內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com