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