一、樹

? ? ? 非線性數(shù)據(jù)結(jié)構(gòu)，在實(shí)際場景中，存在一對多，多對多的情況。

?

樹( tree）是n (n>=0）個(gè)節(jié)點(diǎn)的有限集。當(dāng)n=0時(shí)，稱為空樹。

在任意一個(gè)非空樹中，有如下特點(diǎn)。

1.有且僅有一個(gè)特定的稱為根的節(jié)點(diǎn)。

2.當(dāng)n>1時(shí)，其余節(jié)點(diǎn)可分為m (m>0）個(gè)互不相交的有限集，每一個(gè)集合本身又是一個(gè)樹，并稱為根的子樹。?

如圖所示：節(jié)點(diǎn)1:根節(jié)點(diǎn)（root），節(jié)點(diǎn)5,6,7,8:葉子節(jié)點(diǎn)（leaf）；分為不同的層級，節(jié)點(diǎn)4是父節(jié)點(diǎn)（parent）,節(jié)點(diǎn)4的孩子節(jié)點(diǎn)（child）節(jié)點(diǎn)4的兄弟節(jié)點(diǎn)（sibling）;

?

樹的最大的層級樹，稱為數(shù)的高度或深度，上圖的數(shù)的高度為4。?

二、?二叉樹

? ? ?二叉樹(binary tree）是樹的一種特殊形式。二叉顧名思義，這種樹的每個(gè)節(jié)點(diǎn)最多有2個(gè)孩子節(jié)點(diǎn)。

? ?注意：這里是最多有2個(gè)，也可能只有1個(gè)，或者沒有孩子節(jié)點(diǎn)。?

?

二叉樹節(jié)點(diǎn)的兩個(gè)孩子節(jié)點(diǎn)，一個(gè)被稱為左孩子(leftchild) ，一個(gè)被稱為右孩子（right child）。

此外，二叉樹還有兩種特殊形式，一個(gè)叫作滿二叉樹，另一個(gè)叫作完全二叉樹。

2.1、二叉樹的五種基本形式：?

2.2、二叉樹與樹的區(qū)別?：

• 樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2
• 樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分

2.3、滿二叉樹與完全二叉樹：

（1）滿二叉樹

? ? ?一個(gè)二叉樹的所有非葉子節(jié)點(diǎn)都存在左孩子和右孩子，并且所有葉子節(jié)點(diǎn)都在同一層級上，那么這個(gè)樹就是滿二叉樹。?

簡單點(diǎn)說，滿二叉樹的每一個(gè)分支都是滿的。

?

?（2）完全二叉樹

? ? ?對一個(gè)有n個(gè)節(jié)點(diǎn)的二叉樹，按層級順序編號，則所有節(jié)點(diǎn)的編號為從1到n。如果這個(gè)樹所有節(jié)點(diǎn)和同樣深度的滿二叉樹的編號為從1到n的節(jié)點(diǎn)位置相同，則這個(gè)二叉樹為完全二叉樹。

?

? ? ?在上圖中，二叉樹編號從1到12的12個(gè)節(jié)點(diǎn)，和前面滿二叉樹編號從1到12的節(jié)點(diǎn)位置完全對應(yīng)。因此這個(gè)樹是完全二叉樹。?

? ? ? 完全二叉樹的條件沒有滿二叉樹那么苛刻:滿二叉樹要求所有分支都是滿的;而完全二叉樹只需保證最后一個(gè)節(jié)點(diǎn)之前的節(jié)點(diǎn)都齊全即可。??

三、二叉樹的性質(zhì)?

1、在二叉樹的第 i 層上最多有 2^n-1個(gè)結(jié)點(diǎn)（i>=1）?

2、深度（高度）為 k 的二叉樹最多有 2^k - 1個(gè)結(jié)點(diǎn)（k>=1）

?

3、對任意一顆二叉樹，如果其葉子節(jié)點(diǎn)數(shù)為 N0,度為2的結(jié)點(diǎn)數(shù)為N2,則 N0 = N2 + 1?

設(shè) : 結(jié)點(diǎn)之間的總連線數(shù)是B ,總結(jié)點(diǎn)數(shù)是n,
????????度為0的結(jié)點(diǎn)是n0,
????????度為1的結(jié)點(diǎn)是n1,
????????度為2的結(jié)點(diǎn)是n2,?

? ? ? 從上往下看?二叉樹最大的度就是2所以的節(jié)點(diǎn)要么度是2，要么度是1，要么度是0，度是2的會發(fā)出兩條線, 度是1的發(fā)出1條線所以得到圖片里的公式 B = n2 * 2 + n1;

二叉樹的總結(jié)點(diǎn)數(shù) n = n1 +n2+n0;

總連續(xù)數(shù) B=n-1

?

由此得出：度是0的結(jié)點(diǎn)個(gè)數(shù)=度是2的結(jié)點(diǎn)個(gè)數(shù)+1

四、二叉樹的存儲

1.鏈?zhǔn)酱鎯Y(jié)構(gòu)

2.數(shù)組

?（1）鏈?zhǔn)酱鎯Y(jié)構(gòu)

??

• 存儲數(shù)據(jù)的data變量
• 指向左孩子的left指針
• 指向右孩子的right指針

（2）數(shù)組

????????使用數(shù)組存儲時(shí)，會按照層級順序把二叉樹的節(jié)點(diǎn)放到數(shù)組中對應(yīng)的位置上。如果某一個(gè)節(jié)點(diǎn)的左孩子或右孩子空缺，則數(shù)組的相應(yīng)位置也空出來。

?如何方便地在數(shù)組中定位二叉樹的孩子節(jié)點(diǎn)和父節(jié)點(diǎn)？

? ? ?假設(shè)一個(gè)父節(jié)點(diǎn)的下標(biāo)是parent，

? ? ?左孩子節(jié)點(diǎn)的下標(biāo)=2xparent +1;

? ? ?右孩子節(jié)點(diǎn)的下標(biāo)=2xparent+2。

由此：

? ? ?如果一個(gè)左孩子節(jié)點(diǎn)的下標(biāo)是leftChild，那么它的父節(jié)點(diǎn)下標(biāo)=(leftChild-1)/2。

? ? ?如果一個(gè)右孩子節(jié)點(diǎn)的下標(biāo)是rightChild，那么它的父節(jié)點(diǎn)下標(biāo)=(rightChild-2)/2。

??

?圖上所示，?節(jié)點(diǎn)5的索引是4，那么節(jié)點(diǎn)5的父節(jié)點(diǎn)=(4-2)/2=1,由此可得索引1對應(yīng)的是節(jié)點(diǎn)2

五、二叉樹的遍歷

1. 深度優(yōu)先遍歷
2. 廣度優(yōu)先遍歷

1. 深度優(yōu)先遍歷
? ? 深度優(yōu)先( depth first search，DFS ) ，顧名思義就是偏向于縱深，“一頭扎到底”的訪問方式。深度優(yōu)先遍歷又根據(jù)遍歷順序的不同分為三種：前序遍歷、中序遍歷、后序遍歷。

1.1 前序遍歷
所謂前序遍歷，是指二叉樹遍歷每個(gè)子樹的時(shí)候，都是按照根結(jié)點(diǎn)、左子樹、右子樹的順序來遍歷，因?yàn)楦Y(jié)點(diǎn)在前，所以叫做前序遍歷。前序遍歷中根結(jié)點(diǎn)的優(yōu)先級別最高。如下圖所示：

1.2 中序遍歷

如果二叉樹遍歷每個(gè)子樹的時(shí)候，都是按照左子樹、根結(jié)點(diǎn)、右子樹的順序來遍歷，因?yàn)?strong>根結(jié)點(diǎn)在中間，所以叫做中序遍歷。如下圖所示：

1.3 后序遍歷

二叉樹遍歷每個(gè)子樹的時(shí)候，都是按照左子樹、右子樹、根結(jié)點(diǎn)的順序來遍歷，因?yàn)楦Y(jié)點(diǎn)在最后，所以叫做后序遍歷。如下圖所示：

?使用遞歸的方式來操作，如圖所示

''''樹節(jié)點(diǎn)'''
class TreeNode:'''初始化'''def __init__(self,data):self.data=data #數(shù)據(jù)self.left=None #左節(jié)點(diǎn)self.right=None #右節(jié)點(diǎn)'''二叉樹'''
class MyTree:def create_tree(self,input_list=[]):#判斷數(shù)列是否為空if input_list is None or len(input_list)==0:return None#第一個(gè)出隊(duì)data=input_list.pop(0)#判斷數(shù)據(jù)為空if data is None:return None#樹節(jié)點(diǎn)node=TreeNode(data)#創(chuàng)建左節(jié)點(diǎn)node.left=self.create_tree(input_list)#創(chuàng)建右節(jié)點(diǎn)node.right =self.create_tree(input_list)return nodedef before_foreach(self,node):'''前序遍歷  （根左右）:param node:  二叉樹節(jié)點(diǎn):return:'''# 判斷節(jié)點(diǎn)為空if node is None:return None#顯示節(jié)點(diǎn)數(shù)據(jù)print(node.data,end=',')#再次遍歷左節(jié)點(diǎn)，右節(jié)點(diǎn)self.before_foreach(node.left)self.before_foreach(node.right)return nodedef middle_foreach(self,node):'''中年序遍歷  （左根右）:param node:  二叉樹節(jié)點(diǎn):return:'''# 判斷節(jié)點(diǎn)為空if node is None:return None#再次遍歷左節(jié)點(diǎn)self.middle_foreach(node.left)# 顯示節(jié)點(diǎn)數(shù)據(jù)print(node.data, end=',')# 再次遍歷右節(jié)點(diǎn)self.middle_foreach(node.right)return nodedef after_foreach(self,node):'''后序遍歷  （左右根）:param node:  二叉樹節(jié)點(diǎn):return:'''# 判斷節(jié)點(diǎn)為空if node is None:return None#再次遍歷左節(jié)點(diǎn)，右節(jié)點(diǎn)self.after_foreach(node.left)self.after_foreach(node.right)# 顯示節(jié)點(diǎn)數(shù)據(jù)print(node.data, end=',')return nodeif __name__ == '__main__':#二叉樹對象my=MyTree()#列表ll=list([5,6,8,None,None,10,None,None,9,None,7])#調(diào)用方法node=my.create_tree(input_list=ll)print('前序遍歷')my.before_foreach(node)print('\n中序遍歷')my.middle_foreach(node)print('\n后序遍歷')my.after_foreach(node)

?

?2. 廣度優(yōu)先遍歷

? ? ?廣度優(yōu)先遍歷( Breadth First Search，BFS )也叫層序遍歷，就是按照二叉樹中的層次從左到右依次遍歷每層中的結(jié)點(diǎn)。層序遍歷的實(shí)現(xiàn)思路是利用隊(duì)列來實(shí)現(xiàn)。

? ? ?先將樹的根結(jié)點(diǎn)入隊(duì)，然后再讓隊(duì)列中的結(jié)點(diǎn)出隊(duì)。隊(duì)列中每一個(gè)結(jié)點(diǎn)出隊(duì)的時(shí)候，都要將該結(jié)點(diǎn)的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)入隊(duì)。當(dāng)隊(duì)列中的所有結(jié)點(diǎn)都出隊(duì)，樹中的所有結(jié)點(diǎn)也就遍歷完成。此時(shí)隊(duì)列中結(jié)點(diǎn)的出隊(duì)順序就是層次遍歷的最終結(jié)果。如下圖所示：

?

（1） 根節(jié)點(diǎn)1入隊(duì)列

?

（2） 節(jié)點(diǎn)1出隊(duì)，輸出節(jié)點(diǎn)1，并得到節(jié)點(diǎn)1的左孩子節(jié)點(diǎn)2、右孩子節(jié)點(diǎn)3。讓節(jié)點(diǎn)2和節(jié)點(diǎn)3入隊(duì)。

（3） 節(jié)點(diǎn)2出隊(duì)，輸出節(jié)點(diǎn)2，并得到節(jié)點(diǎn)2的左孩子節(jié)點(diǎn)4、右孩子節(jié)點(diǎn)5。讓節(jié)點(diǎn)4和節(jié)點(diǎn)5入隊(duì)。

（4）?節(jié)點(diǎn)3出隊(duì)，輸出節(jié)點(diǎn)3，并得到節(jié)點(diǎn)3的右孩子節(jié)點(diǎn)6。讓節(jié)點(diǎn)6入隊(duì)。

?

（5）節(jié)點(diǎn)4出隊(duì)，輸出節(jié)點(diǎn)4，由于節(jié)點(diǎn)4沒有孩子節(jié)點(diǎn)，所以沒有新節(jié)點(diǎn)入隊(duì)。

（6）節(jié)點(diǎn)5出隊(duì)，輸出節(jié)點(diǎn)5，由于節(jié)點(diǎn)5同樣沒有孩子節(jié)點(diǎn)，所以沒有新節(jié)點(diǎn)入隊(duì)。

?

（7）?節(jié)點(diǎn)6出隊(duì)，輸出節(jié)點(diǎn)6，節(jié)點(diǎn)6沒有孩子節(jié)點(diǎn)，沒有新節(jié)點(diǎn)入隊(duì)。

??使用遞歸的方式來操作，如上圖所示

'''節(jié)點(diǎn)'''
class TreeNode:'''初始化數(shù)據(jù)'''def __init__(self, data):self.data = dataself.left = Noneself.right = None'''層序遍歷'''
def level_order_traversal(root):# 判斷節(jié)點(diǎn)為空if root is None:return []#數(shù)列result = []#隊(duì)列queue = [root]#循環(huán)while queue:level = []  #層列#循環(huán)for _ in range(len(queue)):#第一個(gè)數(shù)據(jù)出隊(duì)列node = queue.pop(0)#添加數(shù)據(jù)level.append(node.data)#判斷左節(jié)點(diǎn)是否不為空if node.left is not None:queue.append(node.left)# 判斷左節(jié)點(diǎn)是否不為空if node.right is not None:queue.append(node.right)#添加到列表中result.append(level)return resultif __name__ == '__main__':#二叉樹對象root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)root.right.right = TreeNode(6)print(level_order_traversal(root))

?

? ? 在實(shí)際應(yīng)用中，二叉樹又是使用最廣泛的，特別是二叉樹的幾種遍歷操作的規(guī)則，需要重點(diǎn)掌握。在面試或應(yīng)試中，通常會根據(jù)前序、中序、后序中的兩種序列，詢問另外一種樹的遍歷結(jié)果。

?