0x01 線性數據結構
線性數據結構是計算機組織數據的一種方式
- 線性結構是一個數據元素集合
- 有一個唯一的首元素
- 有一個唯一的尾元素
- 除了首元素和尾元素，所有的元素都有一個唯一的先驅
- 除了首元素和尾元素，所有的元素都有一個唯一的後繼
常見的線性數據結構有：數組、棧、隊列、鏈表等
數組
Python語言沒有提供數組數據類型，通常使用列表作為數組。
棧
棧(Stack)是一種特殊的列表
棧的核心操作
棧的實現 Python列表從最後的位置添加和移除元素都非常高效，可天然地實現棧的操作
list = []
list.append(1)
list.append(2)
print(list)
# [1,2]
list.pop
print(list)
# [1]
隊列
隊列(Quene)也是一種特殊的列表
隊列的核心操作
隊列的實現 隊列用列表實現並不適合(在首部添加數據只能用insert方法需要移動其他數據)，collections.deque是Python提供的雙端隊列，支持從任一端添加刪除數據，速度快
- collections import deque
- = deque() dq.append(1) dq.append(2) print(dq) # deque([1,2]) dq.popleft() # deque([2]) dq.popleft() # deque([])
0x02 樹的概念
樹不是一種線性結構，是非線性的，樹在計算機科學裡應用廣泛，包括操作系統、圖形學、數據庫和計算機網絡等。
樹的術語
- 節點(Node) 樹中每一個數據元素稱為一個節點，節點是樹的基本構成部分。
- 邊(Edge) 邊也是樹的基本構成部分。邊有方向，鏈接兩個節點，並表示兩個之間的聯系。
除了根節點外每個節點都有且只有一條與其他節點相連的入邊(指向該節點的邊)，每個節點可能有許多條出邊(從該節點指向其他節點的邊)
- 根節點(Root) 根節點是樹中唯一一個沒有入邊的節點
- 路徑(Path) 路徑是由邊連接起來的節點的有序排列。
- 子節點集(Children) 當一個節點的入邊來自另一個節點時，稱前者是後者的子節點，同一個節點的所有子節點構成子節點集。
- 父節點(Parent) 一個節點是它出邊所連接所有節點的父節點
- 兄弟節點(Sibling) 同一個節點的所有子節點互為兄弟節點
- 子樹(Subtree) 子樹是一個父節點的某個子節點的所有邊和後代節點所構成的集合
- 葉節點(Leaf Node) 沒有子節點的節點稱為葉節點
- 層數(Level) 一個節點的層數是指從根節點到該節點的路徑中的邊的數目
- 高度(Height) 樹的高度等於所有節點的層數的最大值
樹的定義
樹是節點和連接節點的邊的集合，它有以下特征：
- 有一個節點被設計為根節點
- 除了根節點，每個節點都通過一條邊與它唯一的父節點相連接
- 可以沿著唯一的路徑從根節點到每個節點
- 如果這個樹的每個節點都至多有兩個子節點，稱為
二叉樹
0x03 二叉樹
二叉樹的定義
- 二叉樹是由n(n≥0)個結點組成的有限集合、每個結點最多有兩個子樹的有序樹。它或者是空集，或者是一個根和稱為左、右子樹的兩個不相交的二叉樹組成。
- 結點的度和樹的度 每個結點具有的子樹個數稱為結點的度，樹中所有結點的度的最大值稱為樹的度
- 二叉樹的度為2
二叉樹的特點
- 二叉樹是有序樹，即使只有一個子樹，也必須區分左、右子樹；
- 二叉樹每個結點的度不能大於2，只能取0、1、2三者之一
- 二叉樹所有結點的形態有五種:空結點、無左右子樹的結點、只有左子樹的結點、只有右子樹的結點和具有左右子樹的結點
二叉樹的性質
- 二叉樹的第i層至多擁有2^i-1個結點
- 對任何一棵二叉樹T，如果其葉結點數為N0,度為2的結點數為N2，則N0=N2-1
- 滿二叉樹：當樹中每一層都滿時，則稱此樹為滿二叉樹。
- 完全二叉樹：在一棵二叉樹中，除最後一層外，若其余層都是滿的，並且最後一層或者是滿的，或者是右邊缺少連續的若干個結點，則稱此樹為完全二叉樹
- 滿二叉樹是完全二叉樹的特例
- 深度為h的滿二叉樹的結點數為2^h-1
二叉樹的遍歷
按照一定次序訪問樹中的所有結點，並且每個結點的值僅被訪問一次的過程
- 可能的三種遍歷次序
- 先序遍歷：首先訪問根結點然後遍歷左子樹，最後遍歷右子樹
- 中序遍歷：中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹
- 後序遍歷：首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點
