復(fù)習(xí)100分鐘拿下100分，你能做的到嗎？【數(shù)據(jù)結(jié)構(gòu)】（總復(fù)習(xí)）加油、加油！?。?/h1>
二叉樹
考點：
- 二叉樹的性質(zhì)（結(jié)點數(shù)、深度、n0=n2+1、i與2i與2i+1）
- 二叉樹的遍歷（前序、中序、后序）
- 哈夫曼樹和哈夫曼編碼
- 樹與森林的轉(zhuǎn)換
例題一：
- 求二叉樹的先序遍歷、中序遍歷、后序遍歷和層次遍歷。
- 已知前序或后序（確定根）、中序（確定左右），還原二叉樹
例題二：
- 先序遍歷算法（遞歸版）
例題三：
- 構(gòu)造哈夫曼樹，以及哈夫曼編碼。（構(gòu)造樹、編碼）
- 求帶權(quán)路徑的長度 WPL
例題四：
- 已知森林的前序和后序，畫出森林（通過二叉樹來畫）
- 知識點：
- 森林的先序?qū)?yīng)二叉樹的先序、森林的后序?qū)?yīng)二叉樹的中序
- 森林的先序遍歷：一棵樹一棵樹的遍歷（從上往下）
- 森林的先序遍歷：一棵樹一棵樹的遍歷（從下往上）
- 二叉樹 ——> 森林
- 連線：左孩子的所有右孩子與父結(jié)點連線
- 刪線：斷掉所有的右孩子
- 調(diào)整：分層次調(diào)整
圖
考點：
- 鄰接矩陣：順序存儲，稠密圖
- 鄰接表：順序+鏈式，稀疏圖
- 遍歷：廣度優(yōu)先BFS、深度優(yōu)先DFS
- 最小生成樹：連通圖，邊的權(quán)和最小
- 普里姆算法：最近頂點
- 克魯斯卡爾算法：最短邊
- 最短路徑：迪杰斯特拉算法、弗洛伊德算法
- 拓撲排序AOV
- 關(guān)鍵路徑AOE
例題一：
- 鄰接矩陣與鄰接表的存儲表示
例題二：
- 深度優(yōu)先遍歷（借助 棧）
- 廣度優(yōu)先遍歷（借助 隊列）
例題三：
- 用普里姆算法找出最小生成樹（找最近頂點）
- 用克魯斯卡爾算法找出最小生成樹（找最短邊）
查找
考點：
- 折半查找（二分查找）
- 二叉排序樹
- 散列表的查找
例題一：
- 哨兵模式的順序查找：返回0沒有找到，非0則找到
例題二：
- 折半查找：順序存儲的有序數(shù)，類似于排序二叉樹
- 折半查找非遞歸算法
- 折半查找遞歸算法
例題三：
- 二叉排序樹：左小右大
- 二叉排序樹算法（遞歸）
- 二叉排序樹的構(gòu)造（不同的插入次序生成的二叉排序樹形態(tài)不同）
- 二叉排序樹的刪除
標簽：
