樹的定義與基本術(shù)語
樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用，是以分支關(guān)系定義的層次結(jié)構(gòu)。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構(gòu)；在計算機領(lǐng)域中也有廣泛應(yīng)用，如在編譯程序中，可用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)也是信息的重要組織形式之一；在機器學習中，決策樹，隨機森林，GBDT等是常見的樹模型。
樹（Tree）是
個結(jié)點的有限集。在任意一棵樹中：（1）有且僅有一個特定的稱為根（Root）的節(jié)點；（2）當
時，其余節(jié)點可分為
個互不相交的有限集
其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。
圖1 樹型結(jié)構(gòu)
在圖1，該樹一共有13個節(jié)點，其中A是根，其余節(jié)點分成3個互不相交的子集：
,
,
;
都是根A的子樹，且本身也是一棵樹。例如
，其根為B，其余節(jié)點分為兩個互不相交的子集；
,
。
和
都是B的子樹。而在
中E是根，
和
是E的兩棵互不相交的子樹，其本身又是只有一個根節(jié)點的樹。
接下來講一下樹的基本術(shù)語。
樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。節(jié)點擁有的子樹數(shù)量稱為節(jié)點的度（Degree）。在圖1中，A的度為3，B的度為2，C的度為1，F(xiàn)的度為0。度為0的結(jié)點稱為葉子（Leaf）結(jié)點。在圖1中，K,L,F,G,M,I,J都是該樹的葉子。度不為0的結(jié)點稱為分支結(jié)點。樹的度是指樹內(nèi)個結(jié)點的度的最大值。
結(jié)點的子樹的根稱為該結(jié)點的孩子（Child），相應(yīng)地，該結(jié)點稱為孩子的雙親（Parent）。在圖1,中，D是A的孩子，A是D的雙親。同一個雙親的孩子之間互稱兄弟（Sibling）。在圖1中，H,I,J互為兄弟。結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。在圖1中，M的祖先為A,D,H。對應(yīng)地，以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。在圖1中，B的子孫為E,F,K,L。
樹的層次(Level)是從根開始，根為第一層，根的孩子為第二層等。雙親在同一層的結(jié)點互為同兄弟，在圖1中，K,L,M互為堂兄弟。樹中結(jié)點的最大層次稱為樹的深度(Depth)或高度，在圖1中，樹的深度為4。
如果將樹中結(jié)點的各子樹看成從左到右是有次序的（即不能交換），則稱該樹為有序樹，否則為無序樹。
森林（Forest）是
棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。在機器學習模型中，決策樹為樹型結(jié)構(gòu)，而隨機森林為森林，是由若干決策樹組成的森林。
二叉樹的定義與基本性質(zhì)
二叉樹（Binary Tree）是一種特殊的樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點），且二叉樹的子樹有左右之分，其次序不能任意顛倒（有序樹）。
根據(jù)二叉樹的定義，其具有下列重要性質(zhì)：（這里不給出證明，證明細節(jié)可參考清華大學出版社 嚴蔚敏 吳偉民的《數(shù)據(jù)結(jié)構(gòu)（C語言版）》）
性質(zhì)1）在二叉樹的第
層上至多有
個結(jié)點
。
性質(zhì)2）深度為
的二叉樹至多有
個結(jié)點
。
性質(zhì)3）對任何一棵二叉樹，如果其葉子節(jié)點數(shù)為
,度為2的結(jié)點數(shù)為
，則
。
一棵深度為
且有
個結(jié)點的二叉樹稱為滿二叉樹。深度為
，結(jié)點數(shù)數(shù)
的二叉樹，當且僅當其每一個結(jié)點都與深度為
的滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。在下圖2中，（a）為滿二叉樹，（b）為完全二叉樹。
圖2 特殊形態(tài)的二叉樹
下面介紹完全二叉樹的兩個特性：
性質(zhì)4）具有
個結(jié)點的完全二叉樹的深度為
,其中
表示不大于x的最大整數(shù)。
性質(zhì)5）如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號（從第一層到最后一層，每層從左到右），則對任一結(jié)點
,有：
（1）如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i>1,則其雙親結(jié)點為[1/2]。
（2）如果2i>n，則結(jié)點i無左孩子；否則其左孩子是結(jié)點2i。
（3）如果2i+1>n，則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i+1。
介紹完了二叉樹的定義及基本性質(zhì)，接下來，我們需要了解二叉樹的遍歷。所謂二叉樹的遍歷，指的是如何按某種搜索路徑巡防樹中的每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。對于二叉樹，常見的遍歷方法有：先序遍歷，中序遍歷，后序遍歷，層序遍歷。這些遍歷方法一般使用遞歸算法實現(xiàn)。
先序遍歷的操作定義為：若二叉樹為空，為空操作；否則（1）訪問根節(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。
中序遍歷的操作定義為：若二叉樹為空，為空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。
后序遍歷的操作定義為：若二叉樹為空，為空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。
層序遍歷的操作定義為：若二叉樹為空，為空操作；否則從上到下、從左到右按層次進行訪問。
如對于下圖3，
圖3 示例二叉樹
其先序遍歷、中序遍歷、后序遍歷、層序遍歷的結(jié)果為：
先序遍歷為:18 7 3 4 11 5 1 3 6 2 4 中序遍歷為:3 7 4 18 1 5 3 11 2 6 4 后序遍歷為:3 4 7 1 3 5 2 4 6 11 18 層序遍歷為:[[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]]
關(guān)于二叉樹的存儲結(jié)構(gòu)，可以選擇鏈式存儲結(jié)構(gòu)。用于表示二叉樹的鏈表中的結(jié)點至少包含3個域：數(shù)據(jù)域和左、右指針。下面會給出如何利用利用鏈式存儲結(jié)構(gòu)實現(xiàn)二叉樹（Python實現(xiàn)）。
二叉樹的Python實現(xiàn)
了解了二叉樹的基本情況后，筆者使用Python實現(xiàn)了二叉樹，其完整的Python代碼（Binary_Tree.py）如下：
from graphviz import Digraphimport uuidfrom random import sample# 二叉樹類class BTree(object): # 初始化 def __init__(self, data=None, left=None, right=None): self.data = data # 數(shù)據(jù)域 self.left = left # 左子樹 self.right = right # 右子樹 self.dot = Digraph(comment='Binary Tree') # 前序遍歷 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 levelorder(self): # 返回某個節(jié)點的左孩子 def LChild_Of_Node(node): return node.left if node.left is not None else None # 返回某個節(jié)點的右孩子 def RChild_Of_Node(node): return node.right if node.right is not None else None # 層序遍歷列表 level_order = [] # 是否添加根節(jié)點中的數(shù)據(jù) if self.data is not None: level_order.append([self]) # 二叉樹的高度 height = self.height() if height >= 1: # 對第二層及其以后的層數(shù)進行操作, 在level_order中添加節(jié)點而不是數(shù)據(jù) for _ in range(2, height + 1): level = [] # 該層的節(jié)點 for node in level_order[-1]: # 如果左孩子非空，則添加左孩子 if LChild_Of_Node(node): level.append(LChild_Of_Node(node)) # 如果右孩子非空，則添加右孩子 if RChild_Of_Node(node): level.append(RChild_Of_Node(node)) # 如果該層非空，則添加該層 if level: level_order.append(level) # 取出每層中的數(shù)據(jù) for i in range(0, height): # 層數(shù) for index in range(len(level_order[i])): level_order[i][index] = level_order[i][index].data return level_order # 二叉樹的高度 def height(self): # 空的樹高度為0, 只有root節(jié)點的樹高度為1 if self.data is None: return 0 elif self.left is None and self.right is None: return 1 elif self.left is None and self.right is not None: return 1 + self.right.height() elif self.left is not None and self.right is None: return 1 + self.left.height() else: return 1 + max(self.left.height(), self.right.height()) # 二叉樹的葉子節(jié)點 def leaves(self): if self.data is None: return None elif self.left is None and self.right is None: print(self.data, end=' ') elif self.left is None and self.right is not None: self.right.leaves() elif self.right is None and self.left is not None: self.left.leaves() else: self.left.leaves() self.right.leaves() # 利用Graphviz實現(xiàn)二叉樹的可視化 def print_tree(self, save_path='./Binary_Tree.gv', label=False): # colors for labels of nodes colors = ['skyblue', 'tomato', 'orange', 'purple', 'green', 'yellow', 'pink', 'red'] # 繪制以某個節(jié)點為根節(jié)點的二叉樹 def print_node(node, node_tag): # 節(jié)點顏色 color = sample(colors,1)[0] if node.left is not None: left_tag = str(uuid.uuid1()) # 左節(jié)點的數(shù)據(jù) self.dot.node(left_tag, str(node.left.data), style='filled', color=color) # 左節(jié)點 label_string = 'L' if label else '' # 是否在連接線上寫上標簽，表明為左子樹 self.dot.edge(node_tag, left_tag, label=label_string) # 左節(jié)點與其父節(jié)點的連線 print_node(node.left, left_tag) if node.right is not None: right_tag = str(uuid.uuid1()) self.dot.node(right_tag, str(node.right.data), style='filled', color=color) label_string = 'R' if label else '' # 是否在連接線上寫上標簽，表明為右子樹 self.dot.edge(node_tag, right_tag, label=label_string) print_node(node.right, right_tag) # 如果樹非空 if self.data is not None: root_tag = str(uuid.uuid1()) # 根節(jié)點標簽 self.dot.node(root_tag, str(self.data), style='filled', color=sample(colors,1)[0]) # 創(chuàng)建根節(jié)點 print_node(self, root_tag) self.dot.render(save_path) # 保存文件為指定文件
在上述代碼中，筆者創(chuàng)建了二叉樹類BTree，實現(xiàn)了如下方法：
初始化方法：該樹存放的數(shù)據(jù)為data,左子樹，右子樹為left和right，默認均為None;
preorder()方法：遞歸實現(xiàn)二叉樹的先序遍歷；
inorder()方法：遞歸實現(xiàn)二叉樹的中序遍歷；
postorder()方法：遞歸實現(xiàn)二叉樹的后序遍歷；
levelorder()方法：遞歸實現(xiàn)二叉樹的層序遍歷；
height()方法：計算二叉樹的高度；
leaves()方法：計算二叉樹的葉子結(jié)點；
print_tree()方法：利用Graphviz實現(xiàn)二叉樹的可視化，需要設(shè)置的參數(shù)為save_path和label，save_path為文件保存路徑，默認的保存路徑為當前路徑下的Binary_Tree.gv,可以用戶自己設(shè)置；label為是否在Graphviz文件中添加二叉樹的左右子樹的標簽，用于分清哪棵是左子樹，哪棵是右子樹，可以用用戶自己設(shè)置。
若我們需要實現(xiàn)圖3的示例二叉樹，完整的Python代碼如下：
from Binary_Tree import BTree# 構(gòu)造二叉樹, BOTTOM-UP METHODright_tree = BTree(6)right_tree.left = BTree(2)right_tree.right = BTree(4)left_tree = BTree(5)left_tree.left = BTree(1)left_tree.right = BTree(3)tree = BTree(11)tree.left = left_treetree.right = right_treeleft_tree = BTree(7)left_tree.left = BTree(3)left_tree.right = BTree(4)right_tree = tree # 增加新的變量tree = BTree(18)tree.left = left_treetree.right = right_treeprint('先序遍歷為:')tree.preorder()print()print('中序遍歷為:')tree.inorder()print()print('后序遍歷為:')tree.postorder()print()print('層序遍歷為:')level_order = tree.levelorder()print(level_order)print()height = tree.height()print('樹的高度為%s.' % height)print('葉子節(jié)點為：')tree.leaves()print()# 利用Graphviz進行二叉樹的可視化tree.print_tree(save_path='E://BTree.gv', label=True)
OK,當我們運行上述代碼時，可以得到該二叉樹的一些信息，輸出結(jié)果如下：
先序遍歷為:18 7 3 4 11 5 1 3 6 2 4 中序遍歷為:3 7 4 18 1 5 3 11 2 6 4 后序遍歷為:3 4 7 1 3 5 2 4 6 11 18 層序遍歷為:[[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]]樹的高度為4.葉子節(jié)點為：3 4 1 3 2 4
該Python代碼的優(yōu)勢在于利用Graphviz實現(xiàn)了二叉樹的可視化，可以形象直觀地得到二叉樹的圖形。在上面的代碼中，我們可以看到，構(gòu)建二叉樹不是很方便，需要手動地一個個結(jié)點去添加。那么，如果當我們需要根據(jù)某個列表，按列表順序去構(gòu)建二叉樹時，即二叉樹的層序遍歷為該列表，那又該怎么辦呢？有什么好的辦法嗎？
答案是必須有！按照某個列表去構(gòu)建二叉樹的完整Python代碼如下：
from Binary_Tree import BTree# 利用列表構(gòu)造二叉樹# 列表中至少有一個元素def create_BTree_By_List(array): i = 1 # 將原數(shù)組拆成層次遍歷的數(shù)組，每一項都儲存這一層所有的節(jié)點的數(shù)據(jù) level_order = [] sum = 1 while sum < len(array): level_order.append(array[i-1:2*i-1]) i *= 2 sum += i level_order.append(array[i-1:]) # print(level_order) # BTree_list: 這一層所有的節(jié)點組成的列表 # forword_level: 上一層節(jié)點的數(shù)據(jù)組成的列表 def Create_BTree_One_Step_Up(BTree_list, forword_level): new_BTree_list = [] i = 0 for elem in forword_level: root = BTree(elem) if 2*i < len(BTree_list): root.left = BTree_list[2*i] if 2*i+1 < len(BTree_list): root.right = BTree_list[2*i+1] new_BTree_list.append(root) i += 1 return new_BTree_list # 如果只有一個節(jié)點 if len(level_order) == 1: return BTree(level_order[0][0]) else: # 二叉樹的層數(shù)大于1 # 創(chuàng)建最后一層的節(jié)點列表 BTree_list = [BTree(elem) for elem in level_order[-1]] # 從下往上，逐層創(chuàng)建二叉樹 for i in range(len(level_order)-2, -1, -1): BTree_list = Create_BTree_One_Step_Up(BTree_list, level_order[i]) return BTree_list[0]#array = list(range(1,19))array = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'tree = create_BTree_By_List(array)print('先序遍歷為:')tree.preorder()print()height = tree.height()print('\n樹的高度為%s.\n'%height)print('層序遍歷為:')level_order = tree.levelorder()print(level_order)print()print('葉子節(jié)點為：')tree.leaves()print()# 利用Graphviz進行二叉樹的可視化tree.print_tree(save_path='E://create_btree_by_list.gv', label=True)
在上述程序中，筆者利用create_BTree_By_List()函數(shù)實現(xiàn)了按照某個列表去構(gòu)建二叉樹，輸入的參數(shù)array為列表，要求列表中至少有一個元素。運行上述程序，我們得到的26個大寫字母列表所構(gòu)建的二叉樹的圖像如下：
圖4 26個大寫字母列表所構(gòu)建的二叉樹
輸出的結(jié)果如下：
先序遍歷為:A B D H P Q I R S E J T U K V W C F L X Y M Z G N O 樹的高度為5.層序遍歷為:[['A'], ['B', 'C'], ['D', 'E', 'F', 'G'], ['H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'], ['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']]葉子節(jié)點為：P Q R S T U V W X Y Z N O
總結(jié)
二叉樹是很多重要算法及模型的基礎(chǔ)，比如二叉搜索樹（BST），哈夫曼樹(Huffman Tree)，CART決策樹等。本文先介紹了樹的基本術(shù)語，二叉樹的定義與性質(zhì)及遍歷、儲存，然后筆者自己用Python實現(xiàn)了二叉樹的上述方法，筆者代碼的最大亮點在于實現(xiàn)了二叉樹的可視化，這個功能是激動人心的。
在Python中，已有別人實現(xiàn)好的二叉樹的模塊，它是binarytree模塊，其官方文檔的網(wǎng)址為：
https://pypi.org/project/binarytree/。其使用的例子如下：
binarytree模塊演示
關(guān)于這個模塊的更多功能，可參考其官方文檔。當然，筆者還是建議您親自實現(xiàn)一下二叉樹哦，這樣能夠加深對二叉樹的理解~
在后面的文章中，筆者將會介紹二叉搜索樹（BST），哈夫曼樹(Huffman Tree)等，歡迎大家關(guān)注~
注意：本人現(xiàn)已開通微信公眾號： Python爬蟲與算法（微信號為：easy_web_scrape）， 歡迎大家關(guān)注哦~~
