樹
樹（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 binarytreeFor 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290263.html
標籤：其他