三、數(shù)據(jù)結(jié)構(gòu)3.4 樹形結(jié)構(gòu)1. 概念1節(jié)點組成樹形結(jié)構(gòu)的元素2特性只能有一個前驅(qū)但可以有多個后繼每個節(jié)點在樹形結(jié)構(gòu)中的路徑都是唯一的根節(jié)點沒有前驅(qū)只有后繼的頂層節(jié)點分支節(jié)點有前驅(qū)也有后繼葉子節(jié)點只有前驅(qū)沒有后繼的節(jié)點稱為葉子節(jié)點3層根節(jié)點所在層數(shù)為1后繼每過一個節(jié)點層數(shù)14節(jié)點高度從葉子節(jié)點出發(fā)到達根節(jié)點的節(jié)點個數(shù)5節(jié)點深度從根節(jié)點出發(fā)到指定節(jié)點的節(jié)點個數(shù)樹的高度 樹的深度 樹的層數(shù)6子樹樹形結(jié)構(gòu)可以看做是由很多子樹構(gòu)成7多個子樹構(gòu)成的屬性結(jié)構(gòu)稱為森林2. 二叉樹1概念樹形結(jié)構(gòu)中所有節(jié)點最多有2個后繼節(jié)點稱為二叉樹2節(jié)點類型1. 根節(jié)點2. 葉子節(jié)點3. 分支節(jié)點只有左孩子只有右孩子左孩子右孩子都有3完全二叉樹將二叉樹編碼后展開編號連續(xù)的稱為完全二叉樹4滿二叉樹二叉樹所有的葉子節(jié)點都在同一層每一層上的節(jié)點都是滿的5特性二叉樹第k層最 2^k-1 個節(jié)點滿二叉樹前k層有 2^k -1 個節(jié)點6. 二叉樹的遍歷深度優(yōu)先遍歷DFS前序遍歷根左右中序遍歷左根右后續(xù)遍歷左右根廣度優(yōu)先遍歷BFS:逐層從左到右遍歷3.5 哈希表1. 哈希一種算法通過哈希算法將數(shù)據(jù)映射成鍵值根據(jù)鍵值來存取數(shù)據(jù)以降低查找數(shù)據(jù)時的時間復(fù)雜度2. 哈希沖突多個數(shù)據(jù)通過哈希算法映射成相同的鍵值就會產(chǎn)生哈希沖突3.6排序和查找1. 冒泡排序相鄰兩個元素比較大的向后走小的向前走逐漸將最大值放入最末尾循環(huán)將前面元素排序即可時間復(fù)雜度:O(n^2)穩(wěn)定性穩(wěn)定2. 選擇排序假設(shè)前面的元素為最小值將最小值與后續(xù)元素比較最終獲得當(dāng)前最小值與前面元素交換到對應(yīng)的位置時間復(fù)雜度:O(n^2)穩(wěn)定性不穩(wěn)定3. 插入排序?qū)⑶懊嬖乜闯捎行驍?shù)列將后續(xù)元素插入有序數(shù)列中稱為新的有序數(shù)列時間復(fù)雜度:O(n^2)穩(wěn)定性穩(wěn)定4. 希爾排序?qū)?shù)組根據(jù)步長拆分成若干個小數(shù)組依次對每個小數(shù)組進行插入排序?qū)?shù)據(jù)變成大致有序最后再完成一次插入排序時間復(fù)雜度:O(nlogn)穩(wěn)定性不穩(wěn)定5. 快速排序選取第一個元素作為鍵值從后面找比鍵值小的放前面從前面找比鍵值大的放后面最終鍵值放中間如果左側(cè)有元素遞歸快速排序如果右側(cè)有元素遞歸快速排序時間復(fù)雜度:O(nlogn)穩(wěn)定性不穩(wěn)定