Python二元樹初識(新手也秒懂!)

2022-05-27 14:03:03

樹

樹（Tree）是n(n≥0)個節點的有限集。

在任意一棵樹中：

（1）有且僅有一個特定的稱為根（Root）的節點；

（2）當n＞1時，其餘節點可分m(m＞0)為個互不相交的有限集T1,T2,...,Tm；

其中每一個集合本身又是一棵樹，並且稱為根的子樹（SubTree）。

Tree:
--------------------
Height=4 Leves=5 Root
Degree=3 Size=26 ↙
___________________17____________    Node           Level1
/ / ↙
26______ 2 ___9__ ←- Child       Level2
/ / /
___0 19 _3___ 6 ___21 15               Level3
/ / / /
7 _16 _24 _8 10 4 23           Level4
/ / / / /
5 11 28 13 1 27 29 18 22       Level5
↑ ↑
↑___↑_______↑... Leaf Left Child Right Child

術語

節點：包含一個資料元素及若干指向其子樹的分支，又的譯成“結點”（Node）

根：樹和子樹的“頂點”（Root）

度：節點擁有的子樹數量稱為節點的度（Degree）；樹的度是指樹內個結點的度的最大值

分支節點：度不為0的節點

葉子：沒有子樹的節點，即它的度為0 （Leaf）

子節點：結點的子樹的根稱為該節點的孩子（Child）

父節點：對應子節點上一層(level)節點稱為該節點的雙親（Parent）

兄弟結點：同一父節點的子節點，互稱兄弟（Sibling）

節點的祖先：是從根到該結點所經分支上的所有節點

節點的子孫：以某結點為根的子樹中的所有節點

層：從根開始，根為第一層，根的孩子為第二層...（Level）

深度：樹中結點的最大層次數，稱為樹的深度或高度（Depth or Height）

森林：是很多互不相交的樹的集合（Forest）

無序樹：樹中任意節點的子節點之間沒有順序關係，這種樹稱為無序樹，也稱為自由樹

有序樹：樹中任意節點的子節點之間有順序關係，這種樹稱為有序樹

最大樹（最小樹）：每個結點的值都大於（小於）或等於其子結點（如果有的話）值的樹

二元樹

二元樹（Binary Tree）是一種特殊的有序樹型結構。

特點：

（1）每個節點至多有兩棵子樹；

（2）二元樹的子樹有左右之分；

（3）子樹的次序不能任意顛倒（有序樹）。

性質：

（1）在二元樹的第i層上至多有2^(i-1)個節點(i>=1)；

（2）深度為k的二元樹至多有2^k-1個節點(k>=1)；

（3）對任何一棵二元樹，如果其葉子節點數為N0,度為2的結點數為N2，則N0=N2+1。

特殊二元樹

滿二元樹：

所有層的節點都達到最大數量，葉子除外的所有節點都有兩個子節點，所有葉子都在最底一層(k)且數目為2^(k - 1)。即深度k且有2^k - 1個節點(葉子“長”滿最後一層)，或稱完美二元樹（Perfect Binary Tree）

______12_______
/
__3__ __5__
/ /
_7 6 _9 11
/ / / /
13 8 1 4 10 2 0 14

完全二元樹：

如果刪除最底一層的所有葉子它就是滿二元樹，即除了最後一層，每層節點都達到最大數量，即有深度k的個節點數在左閉右開【2^(k-1)+1,2^k-1】區間內。（Complete Binary Tree）

________3______
/
___11___ __4__
/ /
14 7 9 13
/ / /
2 5 8 6 1

完全二元樹性質：

1. 具有N個節點的完全二元樹的深度為[log2 N]+1，其中[x]為高斯函數，截尾取整。

2. 如果對一棵有n個節點的完全二元樹的節點按層序編號（從第一層到最後一層，每層從左到右），則對任一節點，有：

（1）如果i=1，則節點i是二元樹的根，無雙親；如果i>1,則其雙親節點為[i/2]；

（2）如果2i>n，則節點i無左孩子；否則其左孩子是節點2i；

（3）如果2i+1>n，則節點i無右孩子；否則其右孩子是節點2i+1。

其他特殊二元樹

排序二元樹

二叉查詢樹（Binary Search Tree），也稱二元搜尋樹或有序二元樹

平衡二元樹

左右子樹的高度差不大於1的二元樹，且一定有：它的左、右子樹也都是平衡二元樹（Self-Balancing Binary Search Tree）

退化樹

退化樹是每個節點都只有一個孩子的樹，孩子或左或右，或稱病態樹

斜二元樹

一種特殊的退化樹，其中全部節點只有左孩子或右孩子，分別稱左斜二元樹和右斜二元樹，功能基本上退化到和連結串列一樣了

霍夫曼樹

帶權路徑最短的二元樹稱為哈夫曼樹或最優二元樹

B樹

一種對讀寫操作進行優化的自平衡的二元樹查詢，能夠保持資料有序，擁有多餘兩個子樹

堆 heap

binary heap 是一種完全二元樹，除了最底層的葉子節點之外，是填滿的；而且最底層的葉子節點從左至右是連續的，不得有空隙。最大堆（最小堆）就是最大（最小）的完全二元樹。

二元樹的遍歷

指如何按某種搜尋路徑巡防樹中的每個結點，使得每個結點均被存取一次，而且僅被存取一次。

常見的遍歷方法有：先序遍歷，中序遍歷，後序遍歷，層序遍歷；一般都使用遞迴演演算法來實現。

以滿二元樹為例：

_______1________
/
__2__ ___3___
/ /
4 5 _6 _7
/ / / /
8 9 10 11 12 13 14 15

先序遍歷

若二元樹為空，為空操作；

否則（1）存取根節點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。

遍歷結果： 1 [2 [4 8 9] [5 10 11]] [3 [6 12 13] [7 14 15] “根左右”

中序遍歷

若二元樹為空，為空操作；

否則（1）中序遍歷左子樹；（2）存取根結點；（3）中序遍歷右子樹。

遍歷結果： [[8 4 9] 2 [10 5 11]] 1 [[12 6 13] 3 [14 7 15]] “左根右”

後序遍歷

若二元樹為空，為空操作；

否則（1）後序遍歷左子樹；（2）後序遍歷右子樹；（3）存取根結點。

遍歷結果： [[8 9 4] [10 11 5] 2] [[12 13 6] [14 15 7] 3] 1 “左右根”

層序遍歷

若二元樹為空，為空操作；否則從上到下、從左到右按層次進行存取。

遍歷結果： 1 [2 3] [4 5 6 7] [8 9 10 11 12 13 14 15]

非滿二元樹的遍歷結果：

________1________
/
__2___ ___3
/ /
4 _5 6 7
/ /
9 10 11 12 15

先序：1 [2 [4 ' 9] [5 10 11]] [3 [6 12 '] [7 ' 15]]

中序：[' 4 9] 2 [10 5 11] 1 [12 6 '] 3 [' 7 15]

後序：[[' 9 4] [10 11 5] 2] [[12 ' 6] [' 15 7] 3] 1

層序：1 [2 3] [4 5 6 7] [' 9 10 11 12 ' ' 15]

注：結果中 ' 只是標記相對於滿二元樹缺失的子節點，實際結果並不展現。

Python 實現二元樹

用Python簡單實現如下二元樹的遍歷功能，並列出層數和所有葉子：

______A______
/
__B__ __C__
/ /
D E F G
/ /
H I J K L M

程式碼如下：

class Node():
 
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
    def Preorder(self):
        if self.data is not None:
            print(self.data, end=' ')
        if self.left is not None:
            self.left.Preorder()
        if self.right is not None:
            self.right.Preorder()
 
    def Inorder(self):
        if self.left is not None:
            self.left.Inorder()
        if self.data is not None:
            print(self.data, end=' ')
        if self.right is not None:
            self.right.Inorder()
 
    def Postorder(self):
        if self.left is not None:
            self.left.Postorder()
        if self.right is not None:
            self.right.Postorder()
        if self.data is not None:
            print(self.data, end=' ')
 
    def Height(self):
        if self.data is None:
            return 0
        elif not any([self.left, self.right]):
            return 1
        elif all([not self.left, self.right]):
            return self.right.Height()+1
        elif all([self.left, not self.right]):
            return self.left.Height()+1
        else:
            return max(self.left.Height(), self.right.Height())+1
 
    def Leaves(self):
        if self.data is None:
            return None
        elif not any([self.left, self.right]):
            print(self.data, end=' ')
        elif all([not self.left, self.right]):
            self.right.Leaves()
        elif all([self.left, not self.right]):
            self.left.Leaves()
        else:
            self.left.Leaves()
            self.right.Leaves()
 
 
bt = Node('A')
 
bt.left = Node('B')
bt.right = Node('C')
 
bt.left.left = Node('D')
bt.left.right = Node('E')
bt.right.left = Node('F')
bt.right.right = Node('G')
 
bt.left.left.left = Node('H')
bt.left.left.right = Node('I')
bt.left.right.left = Node('J')
bt.left.right.right = Node('K')
 
bt.right.left.right = Node('L')
bt.right.right.right = Node('M')
 
print('Perorder:')
bt.Preorder()
 
print('nInorder:')
bt.Inorder()
 
print('nPostorder:')
bt.Postorder()
 
print('nTree Height:n',bt.Height())
 
print('nLeaves:')
bt.Leaves()

執行結果：

Perorder:
A B D H I E J K C F L G M
Inorder:
H D I B J E K A F L C G M
Postorder:
H I D J K E B L F M G C A
Tree Height: # 實為層數，相當於樓房高度地面一層從0計算高度
4
Leaves:
H I J K L M

要實現二元樹完整的所有功能，程式碼肯定巨長無比。還是找一個優秀的第三方庫比較明智！！！

二元樹第三方庫 binarytree

使用環境與安裝

Requirements: Python 3.6+

Installation:
> pip install binarytree

For conda users:
> conda install binarytree -c conda-forge

簡單範例

binarytree.Node() 二元樹節點

from binarytree import Node
 
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(4)
 
print(root)
 
# 或者： root.pprint()
#
#      __1
#     /   
#    2     3
#     
#      4
#

binarytree.tree() 隨機二元樹

from binarytree import tree
bt = tree(is_perfect=True)
bt.pprint()
 
#    
#              _______14______
#             /               
#         ___13__            __8__
#        /                 /     
#      _9         0        6       3
#     /         /       /      / 
#    10   12    5   7    4   2   1   11
#

下一篇準備實戰這個第三方庫 binarytree ！

本文的續篇來了，請點以下連結：

——初步探索二元樹的第三方庫 binarytree