3.3.1 棧的概述
棧（Stack）是一個線性結構，其維護了一個有序的數據列表，列表的一端稱為棧頂（top），另一端稱為棧底（bottom）。棧對數據的操作有明確限定，插入元素只能從棧頂進行，刪除元素也只能棧頂開始逐個進行，通常將插入元素稱為入棧（push），刪除元素稱為出棧（pop）。正是由于上述規定，棧保證了后進先出的原則（LIFO，Last-In-First-Out）。

棧的底層實現既可以選擇數組也可以選擇鏈表，只要能保證后進先出的原則即可。
3.3.2 棧的功能定義
方法 說明
size() 返回棧中元素個數
is_empty() 判斷棧是否為空
push(item) 將新元素壓入棧中
pop() 獲取棧頂元素，并將棧頂元素彈出棧
peek() 獲取棧頂元素，但不彈出棧
3.3.3 棧的實現
使用動態數組實現一個棧。
class Stack:
def init(self):
“”“初始化棧”“”
self.__size = 0
self.__items = []

@property
def size(self):"""獲取棧元素個數"""return self.__sizedef is_empty(self):"""判斷棧是否為空"""return self.__size == 0def push(self, item):"""入棧"""self.__items.append(item)self.__size += 1def pop(self):"""出棧"""if self.is_empty():raise Exception("棧為空")item = self.__items[self.__size - 1]del self.__items[self.__size - 1]self.__size -= 1return itemdef peek(self):"""訪問棧頂元素"""if self.is_empty():raise Exception("棧為空")return self.__items[self.__size - 1]

3.3.4 棧的應用
1）有效括號
力扣20題https://leetcode.cn/problems/valid-parentheses/description/
（1）題目描述
給定一個只包括“(”，“)”，“[”，“]”，“{”，“}”的字符串s，判斷字符串是否有效。
有效字符串需滿足：
? 左括號必須用相同類型的右括號閉合。
? 左括號必須以正確的順序閉合。
? 每個右括號都有一個對應的相同類型的左括號。
（2）示例
示例 1：
輸入：s = “()”
輸出：true
示例 2：
輸入：s = “()[]{}”
輸出：true
示例 3：
輸入：s = “(]”
輸出：false
示例 4：
輸入：s = “([])”
輸出：true
（3）思路分析
遇到左括號則入棧，遇到右括號則出棧一個左括號與之匹配，如果能夠匹配則繼續，如果匹配失敗或者棧為空則返回False。
（4）代碼實現
class Solution:
def isValid(self, s):
stack = []
for i in s:
match i:
case “(” | “[” | “{”:
stack.append(i)
case “)”:
if (not stack) or (stack.pop() != “(”):
return False
case “]”:
if (not stack) or (stack.pop() != “[”):
return False
case “}”:
if (not stack) or (stack.pop() != “{”):
return False
return True if not stack else False

if name == “main”:
solution = Solution()
s = “()[]{}”
print(s, solution.isValid(s))
s = “(]”
print(s, solution.isValid(s))
s = “([)]”
print(s, solution.isValid(s))
s = “{[]}”
print(s, solution.isValid(s))
3.4 隊列
3.4.1 隊列的概述
隊列（Queue）也是一個線性結構，其同樣維護了一個有序的數據列表，隊列的一端稱為隊首，另一端稱為隊尾。隊列也對數據操作做出了明確限定，插入元素只能從隊尾進行，刪除元素只能從隊首進行，通常將插入操作稱為入隊（enqueue），將刪除操作稱為出隊（dequeue）。也正是由于上述限制，隊列保證了先進先出（FIFO，First-In-First-Out）的原則。

隊列的底層實現既可以選擇數組也可以選擇鏈表，只要能保證先進先出的原則即可。
常見的隊列包括兩種：
? 單向隊列：只能從一端插入數據，從另一端刪除數據，遵循先進先出。
? 雙向隊列：在隊列的兩端都可以進行插入和刪除操作。
3.4.2 隊列的功能定義
方法 說明
size() 返回隊列中元素個數
is_empty() 判斷隊列是否為空
push(item) 向隊尾添加元素
pop() 從隊首取出元素
peek() 訪問隊首元素
3.4.3 隊列的實現
使用鏈表實現一個單向隊列。
class Node:
def init(self, data):
self.data = data
self.next = None

class Queue:
def init(self):
“”“初始化隊列”“”
self.__head = None
self.__tail = None
self.__size = 0

@property
def size(self):"""獲取隊列元素個數"""return self.__sizedef is_empty(self):"""判斷隊列是否為空"""return self.__size == 0def push(self, data):"""入隊"""node = Node(data)if self.is_empty():self.__head = nodeself.__tail = nodeelse:self.__tail.next = nodeself.__tail = nodeself.__size += 1def pop(self):""" "出隊"""if self.is_empty():raise Exception("隊列為空")data = self.__head.dataself.__head = self.__head.nextself.__size -= 1return datadef peek(self):"""訪問隊首元素"""if self.is_empty():raise Exception("隊列為空")return self.__head.data

3.5 哈希表
3.5.1 哈希表的概述
哈希表（Hash Table，也叫散列表），由一系列鍵值對（key-value pairs）組成，并且可以通過鍵（key）查找對應的值（value）。哈希表通過建立key與value之間的映射，實現高效的查詢，我們向哈希表中輸入一個key，可以在O(1)的時間內獲取對應的value。
例如通過客戶id獲取客戶姓名：

哈希表常見的一個操作是根據key來查找value，考慮到數組查詢效率最高，選擇基于數組實現哈希表。利用哈希函數計算key的哈希值，然后將哈希值映射到數組索引。在實現過程中我們可能會遇到如下問題：
? 如何將一個個key映射到數組的索引？
? 如果多個key映射到數組同一個索引怎么辦？
? 數組長度是固定的，如果后續元素過多，大于數組長度怎么辦？
1）哈希函數
哈希表的核心組件是哈希函數。該函數將key轉換為一個數組索引。哈希函數的目標是盡量均勻地將所有可能的key分布到表的不同位置，以減少沖突的發生。
哈希函數的執行步驟分為兩步：
? 通過某種哈希算法計算出key的哈希值。
? 哈希值對數組長度取余，獲取key對應的數組索引。
index = hash(key) % capacity
例如我們使用一個簡單的哈希算法 hash(key)=key 將客戶id映射到一個長度為8的數組的索引，即 index = key % 8 。

常見的哈希算法：
? 通用哈希算法：除法哈希、乘法哈希、MurmurHash、CityHash。
? 加密哈希算法：MD5（已被成功攻擊）、SHA-1（已被成功攻擊）、SHA-2、SHA-3。
? 文件完整性檢查算法：Adler-32、CRC32。
2）哈希沖突
哈希函數可能會將不同的鍵值映射到同一個索引位置，這就是所謂的哈希沖突。處理沖突的方式有多種，最常見的兩種是鏈式法（Chaining）和開放尋址法（Open Addressing）。
（1）鏈式法
將發生碰撞的每個鍵值對作為一個節點（Node）組成一個鏈表（Linked List），然后將鏈表的頭節點保存在數組的目標位置中。這樣一來，向字典中寫入數據時，若發現數組的目標位置已有數據，那么就將當前的鍵值對作為一個節點插入鏈表；從字典中讀取數據時，則從數組的目標位置獲取鏈表，并進行遍歷，直到找到目標數據。

（2）開放尋址法
當發生沖突時根據某種探查策略尋找下一個空槽位。常見的探查策略包括：
? 線性探查（Linear Probing）：如果當前位置已經被占用，就探查下一個位置。
? 二次探查（Quadratic Probing）：以平方的步長進行探查。
? 雙重哈希（Double Hashing）：使用另一個哈希函數來計算新的索引。
3）負載因子
負載因子（Load Factor）是哈希表中元素個數與表的大小的比率。當負載因子過高時，可能需要進行擴容操作，以保持操作的效率。
較小的負載因子可以減少沖突的可能性，較大的負載因子可以提高哈希表的內存利用率。通常情況下負載因子在0.7~0.8是一個比較好的選擇。
3.5.2 哈希表的功能定義
方法 說明
size() 返回哈希表中鍵值對個數
is_empty() 判斷哈希表是否為空
put(key, value) 向哈希表插入鍵值對
remove(key) 從哈希表中根據鍵刪除鍵值對
get(key) 從哈希表中根據鍵獲取值
for_each(func) 遍歷哈希表中的鍵值對
3.5.3 哈希表的實現
class Node:
def init(self, key, value):
self.key = key
self.value = value
self.next = None

class HashTable:

def __init__(self):"""初始化哈希表"""self.__capacity = 8  # 數組長度self.__size = 0  # 鍵值對個數self.__load_factor = 0.7  # 負載因子self.__table = [None] * self.__capacitydef display(self):"""顯示哈希表內容"""for i, node in enumerate(self.__table):print(f"Index {i}: ", end="")current = nodewhile current:print(f"({current.key}, {current.value}) -> ", end="")current = current.nextprint("None")print()def __hash(self, key):"""哈希函數，根據key計算索引"""return hash(key) % self.__capacitydef __grow(self):"""哈希表負載因子超過閾值時進行擴容"""self.__capacity = self.__capacity * 2self.__table, old_table = [None] * self.__capacity, self.__tableself.__size = 0# 將舊哈希表中的元素重新插入到新的哈希表中for node in old_table:current = nodewhile current:self.put(current.key, current.value)current = current.next@property
def size(self):"""獲取哈希表鍵值對個數"""return self.__sizedef is_empty(self):"""判斷哈希表是否為空"""return self.__size == 0def put(self, key, value):"""插入鍵值對，處理哈希沖突"""# 如果負載因子超過閾值則進行擴容if self.__size / self.__capacity > self.__load_factor:self.__grow()index = self.__hash(key)new_node = Node(key, value)# 如果當前位置為空，直接插入if self.__table[index] is None:self.__table[index] = new_nodeelse:# 否則，發生哈希沖突，鏈式存儲current = self.__table[index]while current and current.next:# 如果鍵已經存在，更新值if current.key == key:current.value = valuereturncurrent = current.next# 如果鍵不存在，插入到鏈表尾部current.next = new_nodeself.__size += 1def remove(self, key):"""刪除鍵值對"""index = self.__hash(key)current = self.__table[index]prev = Nonewhile current:if current.key == key:if prev:# 刪除非頭節點prev.next = current.nextelse:# 刪除頭節點self.__table[index] = current.nextself.__size -= 1return Trueprev = currentcurrent = current.nextreturn Falsedef get(self, key):"""訪問鍵值對"""index = self.__hash(key)current = self.__table[index]while current:if current.key == key:return current.valuecurrent = current.nextreturn Nonedef for_each(self, func):"""遍歷哈希表"""for node in self.__table:current = nodewhile current:func(current.key, current.value)current = current.next

3.6 樹
3.6.1 樹的概述
樹（Tree）由一系列具有層次關系的節點（Node）組成。

樹的常見術語：
? 父節點：節點的上層節點。
? 子節點：節點的下層節點。
? 根節點：位于樹的頂端，沒有父節點的節點。
? 葉節點：位于樹的底端，沒有子節點的節點。
? 邊：連接兩個節點的線段。
? 節點的度：節點的子節點數量。
? 節點的層：從根開始定義起，根為第1層，根的子節點為第2層，以此類推。
? 節點的深度：從根節點到該節點所經過的邊的數量，根的深度為0。
? 節點的高度：從距離該節點最遠的葉節點到該節點所經過的邊的數量，所有葉節點的高度為0。
? 樹的深度（高度）：從根節點到最遠葉節點所經過的邊的數量。

3.6.2 二叉樹簡介
樹形結構中最具代表性的一種就是二叉樹（Binary Tree）。二叉樹規定，每個節點最多只能有兩個子節點，兩個子節點分別被稱為左子節點和右子節點。以左子節點為根節點的子樹被稱為左子樹，以右子節點為根節點的子樹被稱為右子樹。

3.6.3 二叉樹存儲結構
1）二叉樹的數組存儲

采用數組結構存儲二叉樹，訪問與遍歷速度較快。但不適合存儲數據量過大的樹，且增刪效率較低，而且樹中存在大量None的情況下空間利用率較低，因此不是主流方式。
2）二叉樹的鏈表存儲

3.6.4 常見的二叉樹
1）完全二叉樹
完全二叉樹只有最下面一層的節點未被填滿，且靠左填充。

2）滿二叉樹
滿二叉樹所有層的節點都被完全填滿，滿二叉樹也是一種完全二叉樹。

3）平衡二叉樹
平衡二叉樹中任意節點的左右子樹高度之差不超過1。

4）二叉搜索樹
二叉搜索樹中的每個節點的值，大于其左子樹中的所有節點的值，并且小于右子樹中的所有節點的值。

5）AVL樹
AVL 樹是一種自平衡的二叉搜索樹，插入和刪除時會進行旋轉操作來保證樹的平衡性。
6）紅黑樹
紅黑樹是一種特殊的二叉搜索樹，除了二叉搜索樹的要求外，它還具有以下特性：
? 每個節點或者是黑色，或者是紅色。
? 根節點是黑色。
? 每個葉節點都是黑色。這里葉節點是指為空（None）的節點。
? 紅色節點的兩個子節點必須是黑色的。即從每個葉到根的所有路徑上不能有兩個連續的紅色節點。
? 從任一個節點到其每個葉的所有路徑上包含相同數目的黑色節點。
7）堆
堆（Heap）是一種滿足特定條件的完全二叉樹，主要可分為兩種類型：
? 大頂堆：每個父節點的值都大于等于其子節點的值。根節點為樹中的最大值。
? 小頂堆：每個父節點的值都小于等于其子節點的值。根節點為樹中的最小值。
8）霍夫曼樹
霍夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹，通常用于數據壓縮，它的構建基于字符出現頻率的概率。
9）B樹
B樹是一種自平衡的多路查找樹。雖然它不是嚴格意義上的二叉樹，但與二叉樹的結構類似。經常用于數據庫、文件系統等需要磁盤訪問的應用。
10）B+樹
B+樹是B樹的優化版本。它通過將數據集中存儲在葉子節點并通過鏈表連接來實現高效的范圍查詢，并且非葉子節點僅存儲索引，提高了磁盤利用率。
3.6.5 二叉搜索樹的功能定義
方法 說明
size() 返回樹中節點個數
is_empty() 判斷樹是否為空
search(item) 查找節點是否存在
add(item) 向二叉搜索樹中插入節點
remove(item) 從二叉搜索樹中刪除節點
for_each(func, order) 按指定方式遍歷二叉樹
3.6.6 二叉樹的創建
from collections import deque

class Node:
“”“二叉樹節點”“”

def __init__(self, data):self.data = dataself.left = Noneself.right = None

class BinarySearchTree:
“”“二叉搜索樹”“”

def __init__(self):"""初始化二叉樹"""self.__root = Noneself.__size = 0def print_tree(self):"""打印樹的結構"""# 先得到樹的層數def get_layer(node):"""遞歸計算樹的層數"""if node is None:return 0else:left_depth = get_layer(node.left)right_depth = get_layer(node.right)return max(left_depth, right_depth) + 1layer = get_layer(self.__root)# 層序遍歷并打印queue = deque([(self.__root, 1)])current_level = 1while queue:node, level = queue.popleft()if level > current_level:print()current_level += 1if node:print(f"{node.data:^{20*layer//2**(level-1)}}", end="")else:print(f"{"N":^{20*layer//2**(level-1)}}", end="")if level < layer:if node:queue.append((node.left, level + 1))queue.append((node.right, level + 1))else:queue.append((None, level + 1))queue.append((None, level + 1))print()@property
def size(self):"""返回樹中節點的個數"""return self.__sizedef is_empty(self):"""判斷樹是否為空"""return self.__size == 0

3.6.7 二叉搜索樹的查找操作
查找時先與當前節點比較大小，等于則找到了目標節點，小于則向左子節點查找，大于則向右子節點查找。如果查找到None仍未找到則說明該節點不在樹中。

后續插入與刪除操作也會用到查找，所以此處提供一個__search_pos()方法，返回查找到的節點和其父節點供后續使用。
def search(self, item):
“”“查找節點是否存在”“”
return self.__search_pos(item)[0] is not None

def __search_pos(self, item):"""查找節點，返回(節點,父節點)。如果節點不存在則為None，此時父節點為一個葉節點"""parent = Nonecurrent = self.__rootwhile current:if item == current.data:breakparent = currentcurrent = current.left if item < current.data else current.rightreturn current, parent

3.6.8 二叉搜索樹的插入操作
插入時先執行查找操作，查找時保存當前節點的父節點。如果找到了節點則說明樹中已有此元素，退出。如果找到了None，此時None的父節點為葉節點，應將該元素插入該葉節點的子節點。

def add(self, item):"""插入節點"""node = Node(item)if self.is_empty():self.__root = nodeelse:current, parent = self.__search_pos(item)# 如果節點之前已存在則返回if current:return# 如果節點之前不存在，則插入父節點的左節點或右節點if parent.data > item:parent.left = nodeelse:parent.right = nodeself.__size += 1

3.6.9 二叉搜索樹的刪除操作
需要保證刪除節點后仍然保證二叉搜索樹的性質。刪除操作需要根據目標節點的子節點數量為0、1、2分三種情況。
1）目標節點的子節點數量為0
直接刪除目標節點。

2）目標節點的子節點數量為1
將目標節點替換為其子節點。

3）目標節點的子節點數量為2
使用目標節點的右子樹最小節點、或左子樹最大節點替換目標節點。

4）代碼實現
def remove(self, item):
“”“刪除節點”“”
current, parent = self.__search_pos(item)
if not current:
return

    # 如果刪除的是葉節點（沒有子節點）if not current.left and not current.right:if parent:if parent.left == current:parent.left = Noneelse:parent.right = Noneelse:# 如果沒有父節點，說明是根節點self.__root = None# 如果刪除的節點只有一個子節點elif not current.left or not current.right:child = current.left if current.left else current.rightif parent:if parent.left == current:parent.left = childelse:parent.right = childelse:# 如果沒有父節點，說明是根節點self.__root = child# 如果刪除的節點有兩個子節點else:# 找到中序后繼（右子樹中最小的節點）successor = self.__get_min(current.right)successor_data = successor.data# 刪除中序后繼節點self.remove(successor_data)# 用中序后繼的值替代當前節點current.data = successor_dataself.__size -= 1def __get_min(self, node):"""找到當前子樹的最小節點"""current = nodewhile current.left:current = current.leftreturn current

3.6.10 二叉樹的遍歷
1）深度優先
深度優先搜索（DFS，Depth First Search）盡可能地深入每一個分支，直到不能再深入為止，然后回溯到上一個節點，繼續嘗試其他的分支。

（1）前序遍歷
先訪問當前節點，再訪問節點的左子樹，再訪問節點的右子樹。
def dfs(node):
“”“前序遍歷”“”
if node is None:
return
print(node) # 訪問當前節點
dfs(node.left) # 訪問節點的左子樹
dfs(node.right) # 訪問節點的右子樹
（2）中序遍歷
先訪問節點的左子樹，再訪問當前節點，再訪問節點的右子樹。
二叉搜索樹中序遍歷的結果是有序的。
def dfs(node):
“”“中序遍歷”“”
if node is None:
return
dfs(node.left) # 訪問節點的左子樹
print(node) # 訪問當前節點
dfs(node.right) # 訪問節點的右子樹
（3）后續遍歷
先訪問節點的左子樹，再訪問節點的右子樹，再訪問當前節點。
def dfs(node):
“”“后序遍歷”“”
if node is None:
return
dfs(node.left) # 訪問節點的左子樹
dfs(node.right) # 訪問節點的右子樹
print(node) # 訪問當前節點
2）廣度優先
（1）層序遍歷
廣度優先搜索（BFS，Breadth First Search）從起始節點開始，首先訪問該節點的所有子節點，然后再訪問子節點的子節點，依此類推，逐層訪問節點。

廣度優先搜索一般使用隊列實現，每訪問一個節點，就將該節點的子節點添加進隊列中。
3）代碼實現
def for_each(self, func, order=“inorder”):
“”“遍歷樹，默認中序遍歷”“”
match order:
case “inorder”:
self.__inorder_traversal(func)
case “preorder”:
self.__preorder_traversal(func)
case “postorder”:
self.__postorder_traversal(func)
case “levelorder”:
self.__levelorder_traversal(func)

def __inorder_traversal(self, func):"""深度優先搜索：中序遍歷"""def inorder(node):if node:inorder(node.left)func(node.data)inorder(node.right)inorder(self.__root)def __preorder_traversal(self, func):"""深度優先搜索：前序遍歷"""def preorder(node):if node:func(node.data)preorder(node.left)preorder(node.right)preorder(self.__root)def __postorder_traversal(self, func):"""深度優先搜索：后序遍歷"""def postorder(node):if node:postorder(node.left)postorder(node.right)func(node.data)postorder(self.__root)def __levelorder_traversal(self, func):"""廣度優先搜索：層序遍歷"""queue = deque()queue.append(self.__root)while queue:node = queue.popleft()func(node.data)if node.left:queue.append(node.left)if node.right:queue.append(node.right)

3.6.11 完整代碼
from collections import deque

class Node:
“”“二叉樹節點”“”

def __init__(self, data):self.data = dataself.left = Noneself.right = None

class BinarySearchTree:
“”“二叉搜索樹”“”

def __init__(self):"""初始化二叉樹"""self.__root = Noneself.__size = 0def print_tree(self):"""打印樹的結構"""# 先得到樹的層數def get_layer(node):"""遞歸計算樹的層數"""if node is None:return 0else:left_depth = get_layer(node.left)right_depth = get_layer(node.right)return max(left_depth, right_depth) + 1layer = get_layer(self.__root)# 層序遍歷并打印queue = deque([(self.__root, 1)])current_level = 1while queue:node, level = queue.popleft()if level > current_level:print()current_level += 1if node:print(f"{node.data:^{20*layer//2**(level-1)}}", end="")else:print(f"{"N":^{20*layer//2**(level-1)}}", end="")if level < layer:if node:queue.append((node.left, level + 1))queue.append((node.right, level + 1))else:queue.append((None, level + 1))queue.append((None, level + 1))print()@property
def size(self):"""返回樹中節點的個數"""return self.__sizedef is_empty(self):"""判斷樹是否為空"""return self.__size == 0def search(self, item):"""查找節點是否存在"""return self.__search_pos(item)[0] is not Nonedef __search_pos(self, item):"""查找節點，返回(節點,父節點)。如果節點不存在則為None，此時父節點為一個葉節點"""parent = Nonecurrent = self.__rootwhile current:if item == current.data:breakparent = currentcurrent = current.left if item < current.data else current.rightreturn current, parentdef add(self, item):"""插入節點"""node = Node(item)if self.is_empty():self.__root = nodeelse:current, parent = self.__search_pos(item)# 如果節點之前已存在則返回if current:return# 如果節點之前不存在，則插入父節點的左節點或右節點if parent.data > item:parent.left = nodeelse:parent.right = nodeself.__size += 1def remove(self, item):"""刪除節點"""current, parent = self.__search_pos(item)if not current:return# 如果刪除的是葉節點（沒有子節點）if not current.left and not current.right:if parent:if parent.left == current:parent.left = Noneelse:parent.right = Noneelse:# 如果沒有父節點，說明是根節點self.__root = None# 如果刪除的節點只有一個子節點elif not current.left or not current.right:child = current.left if current.left else current.rightif parent:if parent.left == current:parent.left = childelse:parent.right = childelse:# 如果沒有父節點，說明是根節點self.__root = child# 如果刪除的節點有兩個子節點else:# 找到中序后繼（右子樹中最小的節點）successor = self.__get_min(current.right)successor_data = successor.data# 刪除中序后繼節點self.remove(successor_data)# 用中序后繼的值替代當前節點current.data = successor_dataself.__size -= 1def __get_min(self, node):"""找到當前子樹的最小節點"""current = nodewhile current.left:current = current.leftreturn currentdef for_each(self, func, order="inorder"):"""遍歷樹，默認中序遍歷"""match order:case "inorder":self.__inorder_traversal(func)case "preorder":self.__preorder_traversal(func)case "postorder":self.__postorder_traversal(func)case "levelorder":self.__levelorder_traversal(func)def __inorder_traversal(self, func):"""深度優先搜索：中序遍歷"""def inorder(node):if node:inorder(node.left)func(node.data)inorder(node.right)inorder(self.__root)def __preorder_traversal(self, func):"""深度優先搜索：前序遍歷"""def preorder(node):if node:func(node.data)preorder(node.left)preorder(node.right)preorder(self.__root)def __postorder_traversal(self, func):"""深度優先搜索：后序遍歷"""def postorder(node):if node:postorder(node.left)postorder(node.right)func(node.data)postorder(self.__root)def __levelorder_traversal(self, func):"""廣度優先搜索：層序遍歷"""queue = deque()queue.append(self.__root)while queue:node = queue.popleft()func(node.data)if node.left:queue.append(node.left)if node.right:queue.append(node.right)

3.7 圖
3.7.1 圖的概述
前面我們學習了線性結構和樹，線性結構局限于只有一個直接前驅和一個直接后繼的關系，樹也只能有一個直接前驅，也就是父節點，當我們需要表示多對多的關系時，就需要用到圖了，圖是比樹更普遍的結構，可以認為樹是一種特殊的圖。圖由節點和邊組成。

圖的常見術語：
? 節點：也稱為頂點，是圖的基礎部分。
? 邊：連接兩個節點，也是圖的基礎部分。可以是單向的，也可以是雙向的。
? 權重：邊可以添加“權重”變量。
? 鄰接：兩節點之間存在邊，則稱這兩個節點鄰接。
? 度：一個節點的邊的數量。入度為指向該節點的邊的數量，出度為該節點指向其他節點的邊的數量。
? 路徑：從一節點到另一節點所經過的邊的序列。
? 環：首尾節點相同的路徑。
3.7.2 圖的分類
1）有向圖和無向圖
? 有向圖：邊是單向的。
? 無向圖：邊是雙向的。

2）連通圖和非連通圖
? 連通圖：從某個節點出發，可以到達其余任意節點。
? 非連通圖：從某個節點出發，有節點不可達。

3.7.3 圖的常用表示法
1）鄰接矩陣
鄰接矩陣用一個n×n的矩陣來表示有n個節點之間的關系，矩陣的每一行（列）代表一個節點，矩陣m行n列的值代表是否存在由m指向n的邊。鄰接矩陣適合存儲稠密圖。

2）鄰接表
鄰接表存儲n個鏈表、列表或其他容器，每個容器存儲該節點的所有鄰接節點。鄰接表適合存儲稀疏圖，空間效率高，尤其在處理邊遠少于節點的圖時表現優越，但在進行邊查找時不如鄰接矩陣高效。

3.7.4 圖的遍歷
1）廣度優先搜索
廣度優先搜索（BFS，Breadth First Search）從起始節點開始，首先訪問該節點的所有鄰接節點，然后再訪問鄰接節點的鄰接節點，依此類推，逐層訪問節點。
? 從圖的起始節點開始，首先訪問該節點，并標記為已訪問。
? 然后依次訪問所有未被訪問的鄰接節點，并將它們加入到隊列中。
? 當隊列中的節點被訪問時，繼續訪問它的鄰接節點，并將新的節點加入隊列。
? 直到隊列為空，表示所有節點都已被訪問。
2）深度優先搜索
深度優先搜索（DFS，Depth First Search）盡可能地深入到圖的每一個分支，直到不能再深入為止，然后回溯到上一個節點，繼續嘗試其他的分支。
? 從圖的一個起始節點開始，訪問這個節點并標記為已訪問。
? 對于每個未訪問的鄰接節點，遞歸地執行 DFS，直到沒有未訪問的鄰接節點。
? 當回溯到一個節點時，繼續訪問它的其他鄰接節點。
第 4 章 常用算法
4.1 查找算法
4.1.1 二分查找
1）算法原理
二分查找又稱折半查找，適用于有序列表。其利用數據的有序性，每輪縮小一半搜索范圍，直至找到目標元素或搜索區間為空為止。

2）代碼實現
def binary_search(arr, target):
left, right = 0, len(arr) - 1

while left <= right:mid = left + (right - left) // 2if arr[mid] == target:return mid  # 找到目標值，返回索引elif arr[mid] < target:left = mid + 1  # 目標值在右半部分else:right = mid - 1  # 目標值在左半部分return -1  # 未找到目標值

3）復雜度分析
（1）時間復雜度
在循環中，區間每輪縮小一半，因此時間復雜度為O(logn)。
（2）空間復雜度
使用常數大小的額外空間，空間復雜度為O(1)。
4.1.2 查找多數元素
力扣169題https://leetcode.cn/problems/majority-element/description/
返回數組中數量超過半數的元素，要求時間復雜度O(n)、空間復雜度O(1)。
示例：
? 輸入：nums = [2,2,1,1,1,2,2]
? 輸出：2
1）思路分析
為了嚴格符合復雜度要求，可以使用多數投票算法，多數投票算法也叫摩爾投票算法。摩爾投票算法的核心思想是對立性和抵消，它基于這樣一個事實：如果一個元素在數組中出現的次數超過數組長度的一半，那么在不斷消除不同元素對的過程中，這個多數元素最終會留下來。
具體來說，算法維護兩個變量：一個是候選元素 candidate，另一個是該候選元素的計數 count。在遍歷數組的過程中，遇到與候選元素相同的元素時，計數加 1；遇到不同的元素時，計數減 1。當計數減為 0 時，說明當前候選元素被抵消完，需要更換候選元素為當前遍歷到的元素，并將計數重置為 1。
算法步驟
? 初始化：
? 選擇數組的第一個元素作為初始候選元素 candidate。
? 將計數 count 初始化為 1。
? 遍歷數組：
? 從數組的第二個元素開始遍歷。
? 若當前元素與候選元素相同，count 加 1。
? 若當前元素與候選元素不同，count 減 1。
? 當 count 變為 0 時，將當前元素設為新的候選元素，并將 count 重置為 1。
? 返回結果：
? 遍歷結束后，candidate 即為多數元素。
代碼實現
def majorityElement(nums):
# 初始化候選元素為數組的第一個元素
candidate = nums[0]
# 初始化候選元素的票數為 1
count = 1
# 從數組的第二個元素開始遍歷
for num in nums[1:]:
if num == candidate:
# 如果當前元素與候選元素相同，票數加 1
count += 1
else:
# 如果當前元素與候選元素不同，票數減 1
count -= 1
if count == 0:
# 當票數為 0 時，更新候選元素為當前元素，并將票數重置為 1
candidate = num
count = 1
return candidate

測試示例

nums = [2, 2, 1, 1, 1, 2, 2]
print(majorityElement(nums))