Python数据结构与算法（第七天）
56.樹(shù)與樹(shù)算法
樹(shù)的概念
樹(shù)（英語(yǔ)：tree）是一種抽象數(shù)據(jù)類(lèi)型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。它具有以下的特點(diǎn)：
- 每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)；
- 沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)；
- 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；
- 除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)；
??
樹(shù)的術(shù)語(yǔ)
- 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的度；
- 樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)的度稱(chēng)為樹(shù)的度；
- 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)；
- 父親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱(chēng)為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；
- 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的子節(jié)點(diǎn)；
- 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱(chēng)為兄弟節(jié)點(diǎn)；
- 節(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類(lèi)推；
- 樹(shù)的高度或深度：樹(shù)中節(jié)點(diǎn)的最大層次；
- 堂兄弟節(jié)點(diǎn)：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟；
- 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；
- 子孫：以某節(jié)點(diǎn)為根的子樹(shù)中任一節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的子孫。
- 森林：由m（m>=0）棵互不相交的樹(shù)的集合稱(chēng)為森林；
樹(shù)的種類(lèi)
- 無(wú)序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒(méi)有順序關(guān)系，這種樹(shù)稱(chēng)為無(wú)序樹(shù)，也稱(chēng)為自由樹(shù)；
- 有序樹(shù)：樹(shù)中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系，這種樹(shù)稱(chēng)為有序樹(shù)；
- 二叉樹(shù)：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹(shù)的樹(shù)稱(chēng)為二叉樹(shù)；
- 完全二叉樹(shù)：對(duì)于一顆二叉樹(shù)，假設(shè)其深度為d(d>1)。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹(shù)被稱(chēng)為完全二叉樹(shù)，其中滿(mǎn)二叉樹(shù)的定義是所有葉節(jié)點(diǎn)都在最底層的完全二叉樹(shù);
- 平衡二叉樹(shù)（AVL樹(shù)）：當(dāng)且僅當(dāng)任何節(jié)點(diǎn)的兩棵子樹(shù)的高度差不大于1的二叉樹(shù)；
- 排序二叉樹(shù)（二叉查找樹(shù)（英語(yǔ)：Binary Search Tree），也稱(chēng)二叉搜索樹(shù)、有序二叉樹(shù)）；
- 霍夫曼樹(shù)（用于信息編碼）：帶權(quán)路徑最短的二叉樹(shù)稱(chēng)為哈夫曼樹(shù)或最優(yōu)二叉樹(shù)；
- B樹(shù)：一種對(duì)讀寫(xiě)操作進(jìn)行優(yōu)化的自平衡的二叉查找樹(shù)，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個(gè)子樹(shù)。
- 二叉樹(shù)：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹(shù)的樹(shù)稱(chēng)為二叉樹(shù)；
樹(shù)的存儲(chǔ)與表示
順序存儲(chǔ)：將數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)在固定的數(shù)組中，然在遍歷速度上有一定的優(yōu)勢(shì)，但因所占空間比較大，是非主流二叉樹(shù)。二叉樹(shù)通常以鏈?zhǔn)酱鎯?chǔ)。?
?鏈?zhǔn)酱鎯?chǔ)：?
由于對(duì)節(jié)點(diǎn)的個(gè)數(shù)無(wú)法掌握，常見(jiàn)樹(shù)的存儲(chǔ)表示都轉(zhuǎn)換成二叉樹(shù)進(jìn)行處理，子節(jié)點(diǎn)個(gè)數(shù)最多為2
常見(jiàn)的一些樹(shù)的應(yīng)用場(chǎng)景
1.xml，html等，那么編寫(xiě)這些東西的解析器的時(shí)候，不可避免用到樹(shù)
2.路由協(xié)議就是使用了樹(shù)的算法
3.mysql數(shù)據(jù)庫(kù)索引
4.文件系統(tǒng)的目錄結(jié)構(gòu)
5.所以很多經(jīng)典的AI算法其實(shí)都是樹(shù)搜索，此外機(jī)器學(xué)習(xí)中的decision tree也是樹(shù)結(jié)構(gòu)
57.二叉樹(shù)的概念
二叉樹(shù)的基本概念
二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。通常子樹(shù)被稱(chēng)作“左子樹(shù)”（left subtree）和“右子樹(shù)”（right subtree）
二叉樹(shù)的性質(zhì)(特性)
性質(zhì)1:?在二叉樹(shù)的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)（i>0）
性質(zhì)2:?深度為k的二叉樹(shù)至多有2^k - 1個(gè)結(jié)點(diǎn)（k>0）
性質(zhì)3:?對(duì)于任意一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1;
性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度必為 log2(n+1)
性質(zhì)5:對(duì)完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則編號(hào)為i 的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)必為2i＋1；其雙親的編號(hào)必為i/2（i＝1 時(shí)為根,除外）
?
58.二叉樹(shù)的廣度優(yōu)先遍歷
二叉樹(shù)的節(jié)點(diǎn)表示以及樹(shù)的創(chuàng)建
class Node(object):"""節(jié)點(diǎn)類(lèi)"""def __init__(self, item):self.item = itemself.lchild = Noneself.rchild = Noneclass Tree(object):"""樹(shù)類(lèi)"""def __init__(self):self.root = None59.二叉樹(shù)的實(shí)現(xiàn)
二叉樹(shù)的實(shí)現(xiàn)
class Node(object):"""節(jié)點(diǎn)類(lèi)"""def __init__(self, item):self.item = itemself.lchild = Noneself.rchild = Noneclass Tree(object):"""樹(shù)類(lèi)"""def __init__(self):self.root = Nonedef add(self,item):node = Node(item)if self.root is None:self.root = nodereturnqueue = [self.root]while queue:cur_node = queue.pop(0)if cur_node.lchild is None:cur_node.lchild = nodereturnelse:queue.append(cur_node.lchild)if cur_node.rchild is None:cur_node.rchild = nodereturnelse:queue.append(cur_node.rchild)60.二叉樹(shù)的先序、中序、后序遍歷
廣度優(yōu)先遍歷(層次遍歷)
從樹(shù)的root開(kāi)始，從上到下從從左到右遍歷整個(gè)樹(shù)的節(jié)點(diǎn)
def breadth_travel(self):"""利用隊(duì)列實(shí)現(xiàn)樹(shù)的層次遍歷"""if self.root is None:returnqueue = [self.root]while queue:cur_node = queue.pop(0)print(cur_node.item)if cur_node.lchild is not None:queue.append(cur_node.lchild)if cur_node.rchild is not None:queue.append(cur_node.rchild) if __name__ == "__main__":tree = Tree()tree.add(1)tree.add(2)tree.add(3)tree.add(4)tree.add(5)tree.breadth_travel() 1 2 3 4 5深度優(yōu)先遍歷
對(duì)于一顆二叉樹(shù)，深度優(yōu)先搜索(Depth First Search)是沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支。
那么深度遍歷有重要的三種方法。這三種方式常被用于訪問(wèn)樹(shù)的節(jié)點(diǎn)，它們之間的不同在于訪問(wèn)每個(gè)節(jié)點(diǎn)的次序不同。這三種遍歷分別叫做先序遍歷（preorder），中序遍歷（inorder）和后序遍歷（postorder）。我們來(lái)給出它們的詳細(xì)定義，然后舉例看看它們的應(yīng)用。
先序遍歷
在先序遍歷中，我們先訪問(wèn)根節(jié)點(diǎn)，然后遞歸使用先序遍歷訪問(wèn)左子樹(shù)，再遞歸使用先序遍歷訪問(wèn)右子樹(shù)
根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)
中序遍歷
在中序遍歷中，我們遞歸使用中序遍歷訪問(wèn)左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后再遞歸使用中序遍歷訪問(wèn)右子樹(shù)
左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)
后序遍歷 在后序遍歷中，我們先遞歸使用后序遍歷訪問(wèn)左子樹(shù)和右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)
左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)
61.二叉樹(shù)由遍歷確定一棵樹(shù)
二叉樹(shù)由遍歷確定一棵樹(shù)
后續(xù)遍歷：7 8 3 9 4 1 5 6 2 0? ? ? ?左右根
中序遍歷：7?3 8 1 9 4 0 5 2 6? ? ? ?左根右
總結(jié)
以上是生活随笔為你收集整理的Python数据结构与算法（第七天）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： Python数据结构与算法（第六天）
- 下一篇： 机器学习-数据科学库（第一天）