非線性結(jié)構(gòu)(樹狀結(jié)構(gòu))

特點(diǎn): 每個(gè)節(jié)點(diǎn)都可以有n個(gè)子節(jié)點(diǎn)(后繼節(jié)點(diǎn)) 和 n個(gè)父節(jié)點(diǎn)(前驅(qū)節(jié)點(diǎn))

代表: 樹, 圖......

概述

屬于數(shù)據(jù)結(jié)構(gòu)之 非線性結(jié)構(gòu)的一種, 父節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)(后續(xù)節(jié)點(diǎn))

特點(diǎn)

1. 有且只有1個(gè)根節(jié)點(diǎn)

2. 每個(gè)節(jié)點(diǎn)都可以有1個(gè)父節(jié)點(diǎn)及任意個(gè)子節(jié)點(diǎn), 前提: 根節(jié)點(diǎn)除外(沒有父節(jié)點(diǎn))

3. 沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱之為: 葉子節(jié)點(diǎn)

二叉樹概念和性質(zhì)

每個(gè)節(jié)點(diǎn)最多只能有2個(gè)子節(jié)點(diǎn)

二叉樹分類:

1. 完全二叉樹: 除了最后1層, 其他層的節(jié)點(diǎn)都是滿的

2. 滿二叉樹: 包括最后1層, 所有層的節(jié)點(diǎn)都是滿的

3. 不完全二叉樹: 某層(不僅僅是最后1層)的節(jié)點(diǎn)數(shù)量不滿

常用二叉樹:

1. 平衡二叉樹: 防止樹退化成鏈表, 指的是: 任意節(jié)點(diǎn)的兩顆子樹的高度差不超過1

2. 排序二叉樹: 主要是對(duì)元素排序的

存儲(chǔ)方式

更推薦使用 鏈表的方式來存儲(chǔ), 每個(gè)節(jié)點(diǎn)有三部分組成, 分別是: 元素域(數(shù)值域), 左子樹(地址域), 右子樹(地址域)

針對(duì)于, 多叉樹的情況, 可以將其轉(zhuǎn)成二叉樹, 然后再來存儲(chǔ)

性質(zhì)

1. 在二叉樹的第i層上至多有2i-1 個(gè)結(jié)點(diǎn)（i>0）eg：第3層最多結(jié)點(diǎn)個(gè)數(shù)2^((3-1))

2. 深度為k的二叉樹至多有2k - 1個(gè)結(jié)點(diǎn)（k>0）eg:層次2^((3))-1= 7

3. 對(duì)于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0 = N2+1

4. 最多有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為log2(n+1)

5. 對(duì)完全二叉樹，若從上至下、從左至右編號(hào)，則編號(hào)為i的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)必為2i＋1,其父節(jié)點(diǎn)的編號(hào)必為i//2（i＝1時(shí)為根,除外）

二叉樹的廣度優(yōu)先

廣度優(yōu)先可以找到最短路徑：

相當(dāng)于層次遍歷，先把第層給遍歷完，看有沒有終點(diǎn)；再把第層遍歷完，看有沒有重點(diǎn)

插入節(jié)點(diǎn)

1. 初始操作：

   初始化隊(duì)列、將根節(jié)點(diǎn)入隊(duì)、準(zhǔn)備加入到二叉樹的新結(jié)點(diǎn)

2. 重復(fù)執(zhí)行：

   獲得并彈出隊(duì)頭元素

   1、若當(dāng)前結(jié)點(diǎn)的左右子結(jié)點(diǎn)不為空，則將其左右子節(jié)點(diǎn)入隊(duì)列

   2、若當(dāng)前結(jié)點(diǎn)的左右子節(jié)點(diǎn)為空，則將新結(jié)點(diǎn)掛到為空的左子結(jié)點(diǎn)、或者右子節(jié)點(diǎn)

圖示

二叉樹的深度優(yōu)先

深度優(yōu)先往往可以很快找到搜索路徑：

比如：先找一個(gè)結(jié)點(diǎn)看看是不是終點(diǎn)，若不是繼續(xù)往深層去找，直到找到終點(diǎn)。、中序，先序，后序?qū)儆谏疃葍?yōu)先算法

示例

層次(廣度)遍歷: 0123456789

先序遍歷: 0137849256 根 左 右

中序遍歷: 7381940526 左 根 右

后序遍歷: 7839415620 左 右 根

圖示

二叉樹代碼演示

# 創(chuàng)建節(jié)點(diǎn)類
class Node(object):# 初始化屬性def __init__(self, item):self.item = item ?# 數(shù)值域self.lchild = None ?# 左子樹(地址域)self.rchild = None ?# 左子樹(地址域)
?
?
# 創(chuàng)建二叉樹類
class BinaryTree(object):def __init__(self, root: Node = None):self.root = root ?# 根節(jié)點(diǎn)
?# 添加元素函數(shù)(完全二叉樹)def add(self, item):# 判斷根節(jié)點(diǎn)是否為空if self.root is None:self.root = Node(item)return# 根節(jié)點(diǎn)不為空, 找到缺失節(jié)點(diǎn)# 創(chuàng)建隊(duì)列, 用于記錄已存在的節(jié)點(diǎn)queue = []# 把根節(jié)點(diǎn)添加到隊(duì)列queue.append(self.root)# 循環(huán)遍歷隊(duì)列, 直至 把新元素添加到合適的位置while True:# 獲取隊(duì)列中的第一個(gè)元素node = queue.pop(0)# 左子樹為空if node.lchild is None:node.lchild = Node(item)return ?# 結(jié)束添加動(dòng)作else:# 左子樹存在, 就將其添加到隊(duì)列中queue.append(node.lchild)# 右子樹為空if node.rchild is None:node.rchild = Node(item)return ?# 結(jié)束添加動(dòng)作else:# 右子樹存在, 就將其添加到隊(duì)列中queue.append(node.rchild)
?# 廣度優(yōu)先def breadth_travel(self):# 判斷根節(jié)點(diǎn)是否為空if self.root is None:return ?# 為空直接結(jié)束# 創(chuàng)建隊(duì)列, 記錄所有節(jié)點(diǎn)queue = []# 將根節(jié)點(diǎn), 添加到隊(duì)列中queue.append(self.root)# 只要隊(duì)列長(zhǎng)度大于0, 就說明還有節(jié)點(diǎn), 循環(huán)遍歷while len(queue) > 0:# 獲取隊(duì)列中的第一元素node = queue.pop(0)# 輸出當(dāng)前節(jié)點(diǎn)print(node.item, end='\t')# 判斷當(dāng)前節(jié)點(diǎn)的左子樹是否為空if node.lchild is not None:# 不為空, 則將左子樹入隊(duì)queue.append(node.lchild)# 判斷當(dāng)前節(jié)點(diǎn)的右子樹是否為空if node.rchild is not None:# 不為空, 則將左子樹入隊(duì)queue.append(node.rchild)
?# 深度優(yōu)先: 先序(根左右)def preorder_travel(self, root):# 判斷根節(jié)點(diǎn)是否不為空if root is not None:# 中序先輸出根節(jié)點(diǎn)print(root.item, end='\t')# 遞歸左子樹self.preorder_travel(root.lchild)# 遞歸右子樹self.preorder_travel(root.rchild)
?# 深度優(yōu)先: 中序(左根右)def mid_travel(self, root):if root is not None:self.mid_travel(root.lchild)print(root.item, end='\t')self.mid_travel(root.rchild)
?# 深度優(yōu)先: 后序(左右根)def poster_travel(self, root):if root is not None:self.poster_travel(root.lchild)self.poster_travel(root.rchild)print(root.item, end='\t')
?

三. 算法

排序類相關(guān)

穩(wěn)定性: 排序前后的相對(duì)位置(相同的元素位置)是否發(fā)生變化

穩(wěn)定排序: 冒泡排序、插入排序、歸并排序和基數(shù)排序

不穩(wěn)定排序: 選擇排序、快速排序、希爾排序、堆排序

冒泡排序

原理

相鄰元素兩輛比較, 大的往后走, 這樣第一輪比較完畢后, 最大值就在最大索引處

核心

1. 比較的總輪數(shù) 列表長(zhǎng)度 - 1

2. 每輪比較的總次數(shù) 列表長(zhǎng)度 - 1 - 輪數(shù)(從0 開始)

3. 誰和誰比較(交換) j 和 j + 1 比較

圖解

代碼

def buble_sort(my_list):# 定義變量n存儲(chǔ)列表長(zhǎng)度n = len(my_list)# 比較的輪數(shù)for i in range(n - 1): ?# i: 0, 1, 2, 3# 記錄交換的次數(shù)count = 0# 每輪比較的次數(shù)for j in range(n - 1 - i): ?# j: 4, 3, 2, 1if my_list[j] > my_list[j + 1]:# 交換時(shí)計(jì)數(shù)器加一count += 1my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]print(f'第 {i} 輪交換了 {count} 次')# 如果當(dāng)前輪次交換了0次, 則跳出外循環(huán)if count == 0:break
?
?
if __name__ == '__main__':list1 = [2, 1, 4, 5, 3]buble_sort(list1)print('list1', list1)print('-' * 21)
?list2 = [5, 3, 4, 7, 2]buble_sort(list2)print('list2', list2)
?

冒泡總結(jié)

時(shí)間復(fù)雜度: 最優(yōu)O(n), 最差O(n2)

遍歷一遍發(fā)現(xiàn)沒有任何元素發(fā)生了位置交換,終止排序

算法穩(wěn)定性:穩(wěn)定算法

選擇排序

原理

第一輪: 假設(shè)索引為0的元素時(shí)最小值, 依次和后續(xù)的元素比較, 只要比該值小, 就紀(jì)錄住真正最小值的那個(gè)索引, 第一輪比較完畢后, 把最小值放到索引為0的位置即可

第二輪: 假設(shè)索引為1的元素時(shí)最小值, 依次和后續(xù)的元素比較, 只要比該值小, 就紀(jì)錄住真正最小值的那個(gè)索引, 第一輪比較完畢后, 把最小值放到索引為1的位置即可

......

解釋:

選擇排序就是把符合要求的數(shù)據(jù)選擇出來進(jìn)行排序

核心

1. 比較的總輪數(shù) 列表長(zhǎng)度 - 1

2. 每輪比較的總次數(shù) i + 1 ~ 列表的最后1個(gè)元素

3. 誰和誰比較(交換) j 和 min_index 位置的元素比較

比較過程

具體的比較過程, 假設(shè)共 5 個(gè)元素 比較的輪數(shù) 每輪比較的總次數(shù) 誰和誰比較 第0輪 4 0和1, 0和2, 0和3, 0和4 第1輪 3 1和2, 1和3, 1和4 第2輪 2 2和3, 2和4 第3輪 1 3和4

代碼

def select_sort(my_list):# 定義變量n存儲(chǔ)列表長(zhǎng)度n = len(my_list)# 比較的輪數(shù)for i in range(n - 1): ?# i: 0, 1, 2, 3# 記錄最小值索引min_idx = i# 每輪比較的次數(shù)for j in range(i + 1, n): ?# j: 4, 3, 2, 1# 判斷min_idx后的元素是否比min_idx小if my_list[j] < my_list[min_idx]:# 將最小值索引設(shè)為jmin_idx = j# 如果最小值索引等于i說明i的位置是正確的,不交換if min_idx != i:# 交換my_list[i], my_list[min_idx] = my_list[min_idx], my_list[i]
?
?
if __name__ == '__main__':list1 = [2, 1, 4, 5, 3]select_sort(list1)print('list1', list1)print('-' * 21)
?list2 = [5, 3, 4, 7, 2]select_sort(list2)print('list2', list2)
?

選擇總結(jié)

算法穩(wěn)定性: 不穩(wěn)定算法

時(shí)間復(fù)雜度: 最優(yōu): O(n2), 最差: O(n2)

插入排序

原理

把要排序的列表分成兩部分, 第一部分是有序的(拍好序的), 第二部分是無序的(待排序的), 然后從待排序的列表中, 依次取出每個(gè)值, 插入到 排好序的列表的 合適位置 .

核心

1. 比較的總輪數(shù) 列表長(zhǎng)度 - 1 for i in range(1, n)

2. 每輪比較的總次數(shù) i ~ 0(逆向遍歷) for i in range(i, 0, -1)

3. 誰和誰比較(交換) i 和 j 的每個(gè)值 比較

比較過程

具體的比較過程, 假設(shè)共 5 個(gè)元素 比較的輪數(shù) 每輪比較的總次數(shù) 誰和誰比較 第1輪 4 1和0 第2輪 3 2和1, 2和0 第3輪 2 3和2, 3和1, 3和0 第4輪 1 4和3, 4和2, 4和1, 4和0

代碼

def insert_sort(my_list):# 定義變量n存儲(chǔ)列表長(zhǎng)度n = len(my_list)# 比較的輪數(shù)for i in range(1, n): ? ? ? ? ? # i: 1,  2, ? 3, ? ? 4# 每輪比較的次數(shù)for j in range(i, 0, -1): ? # j: 1  2,1  3,2,1  4,3,2,1# 判斷當(dāng)前元素(待排序)是否比前面的元素(排好序的)小if my_list[j] < my_list[j - 1]:# 交換當(dāng)前元素和當(dāng)前元素的前一個(gè)元素my_list[j], my_list[j - 1] = my_list[j - 1], my_list[j]else:break
?
?
if __name__ == '__main__':list1 = [2, 1, 4, 5, 3]insert_sort(list1)print('list1', list1)print('-' * 21)
?list2 = [5, 3, 4, 7, 2]insert_sort(list2)print('list2', list2)
?

插入總結(jié)

算法穩(wěn)定性: 穩(wěn)定算法

時(shí)間復(fù)雜度: 最優(yōu): O(n) 最壞: O(n2)

查找類相關(guān)(二分查找)

此處只記錄二分查找, 并非查找只有二分查找這一種

介紹

1. 概述: 他是一種高效的查找類算法, 也叫: 折半查找

2. 細(xì)節(jié): 要被查找的列表必須是有序的

1. 原理:

   1. 獲取列表的中間位置的元素, 然后和要查找的元素進(jìn)行比較

   2. 如果相等, 直接返回結(jié)果即可

   3. 如果比中間值小, 去 中間前 范圍查找

   4. 如果比中間值大, 去 中間后 范圍查找

遞歸版

def binary_search(my_list, item):n = len(my_list)if n <= 0:return Falsemid = n // 2if item == my_list[mid]:return Trueelif item < my_list[mid]:return binary_search(my_list[:mid], item)else:return binary_search(my_list[mid + 1:], item)

非遞歸版

def binary_search(my_list, item):# 計(jì)算列表長(zhǎng)度n = len(my_list)# 定義初始起始位置為0start = 0# 定義初始終止位置為列表長(zhǎng)度減1end = n - 1# 當(dāng)起始位置大于終止位置時(shí)結(jié)束循環(huán)while start <= end:# 定義中間位置為起始位置加終止位置除2mid = (start + end) // 2# 判斷中間索引位置的元素是否為要查找的元素if my_list[mid] == item:return True# 判斷中間索引位置的元素比要查找的位置小elif my_list[mid] < item:# 設(shè)置起始位置索引為中間位置加1start = mid + 1# 判斷中間索引位置的元素比要查找的位置大else:# 設(shè)置終止位置索引為中間位置減1end = mid - 1return False
?
?
if __name__ == '__main__':list1 = [1, 2, 3, 4, 5, 6, 7]print(binary_search(list1, 4))
?
?

總結(jié)

1. 必須采用順序存儲(chǔ)結(jié)構(gòu)

2. 必須按關(guān)鍵字大小有序排列

3. 時(shí)間復(fù)雜度: 最優(yōu): O(1) 最壞: O(logn)