心智圖資源庫 【學習筆記】資料結構-樹
資料結構中關於樹的一些知識，內容有哈夫曼樹、樹表的查找、線索二元樹、二元樹遍歷方式、最小生成樹，歡迎大家學習。
軟體系統測試知識點總結
Lumion10.0基本特效使用
LaTeX
01資料結構
資料結構-演算法心智圖
資料結構排序演算法
資料結構查找演算法
資料結構與演算法
資料結構實作與演算法解析
資料結構
樹
哈夫曼樹
帶權路徑長度WPL
設二元樹具有n個帶權值的葉結點，那麼從根結點到各個葉結點的路徑長度與相應結點權值的乘積的和，叫做二叉樹的帶權路徑長度WPL (weighted Path Length) 。
相同的葉結點構造出不同的二元樹
權值越大的葉子結點，越靠近根，wpl的值越小
定義
具有最小帶權路徑長度的二元樹稱為哈夫曼樹(也稱為最優樹)。
如何構造？
原則
權值越大的葉結點越靠近根結點。
權值越小的葉結點越遠離根結點。
找小值（合成的節點也要一起比較）
過程
有n0個帶權值的葉子結點的
應用
哈弗曼編碼（前綴編碼）
哈夫曼編碼特徵:權值越大的字元編碼越短，反之越長。
在一組字符的哈夫曼編碼中，不可能出現一個字符的哈夫曼編碼是另一個字符哈夫曼編碼的前綴。
字元編碼
機器指令
樹表的查找
二元排序樹
左<根<右
平衡二元樹AVL
二元排序樹的改良版（特殊的二元排序樹），盡量保證樹越矮越好！
如何判斷樹是否在正常的長高？
平衡因子=左子樹高度-右子樹高度
平衡因子<=1的二元排序樹
平衡二元樹的最大深度和最小節點數
B樹（平衡二元樹的拓展）
插入
創建B樹就是不斷進行插入操作的過程
線索二元樹
左空鏈域的條件:處於序列最左端，原來左指標就是空的。
右空鏈域的條件:處於序列最右端，原來是右指標就是空的。
二元樹遍歷方式
針對根節點
前序
根-左-右
中序
左-根-右
後序
左-右-根
層次
一行一行遍歷
最小生成樹
Prim演算法
要求
權值最小，不能成環
針對節點少的題
Prime演算法的核心步驟是：在帶權連通圖中V是包含所有頂點的集合， U已經在最小生成樹中的節點，從圖中任某一頂點v開始，此時集合U={v}，重複執行下述運算：在所有u∈U,w∈V-U的邊(u,w)∈E中找出一條權值最小的邊，將(u,w)這一邊加入到已找到邊的集合，並且將點w加入到集合U中，當U=V時，就找到了這顆最小生成樹。
Kruskal演算法
先把節點都確定，依序選擇路徑最短的
不能成環
針對邊數少的題
基本思想：以邊為主導。在帶權連通圖中，U是所有邊構成的集合，N是頂點數量，設SU是已經在最小生成樹上的邊構成的集合。重複執行下述操作:每次選擇一條權值最小的邊e∈U-SU,且與SU中邊不構成環的邊，加入到SU中。當SU中邊數量等於N-1時，就找到了最小生成樹。
題
如果一個節點不是葉節點，那麼就會有孩子,這些孩子就是一群親兄弟
沒有右側指標的節點的數量是:根節點 非葉節點數量
排除對稱的，數目，要確保一直是左少右多或左多右少
ASL平均查找長度
與樹的高度有關
第五章樹與二元樹
二元樹的遍歷與哈夫曼樹
困難：二元樹與樹和森林的轉換
多以選擇題形式考查，也會涉及樹的遍歷和哈夫曼樹的演算法
n個結點的有限集合
根節點唯一
子樹數無限制，但互不相交
度數：節點所擁有的子樹的個數
二元樹：度數都<=2
性質
在二元樹的第i層上最多有2^i-1個節點。
二元樹中如果深度為k,那麼最多有2^k-1個節點。 (k>=1)
n0=n2 1 ,n0表示度數為0的節點數,n2表示度數為2的節點數。
在完全二元樹中，具有n個節點的完全二元樹的深度為[log2n] 1，其中[log2n]是向下取整
[二元樹]節點計算公式N = n0 n1 n2
節點總數=總度數 1=Oxn0 1xn1 2xn2 ..
滿叉樹
所有節點都存在左右子樹，且所有葉子節點都在同一層
完全二元樹
葉子結點只能出現在最下層和次下層，
而最下面一層的結點都集中在該層最左邊的若干位置的二元樹。
樹、森林、二元樹的遍歷對應關係
堆疊
必須是完全二元樹
完全二元樹只允許最後一行不為滿。且最後一行必須從左到右排序。最後一行元素之間不可以有間隔
堆積性
大根堆
小根堆
基本操作
堆的存儲
1.依層序遍歷編號，用一維數組表示
父節點為i，左子結點下標2i 1，右子節點2i 2（此規則在演算法中常使用）
上濾
只有樹的最後一個元素破壞了堆序性
主要用於插入新元素到堆中
複雜度：O(logN)
下濾
只有根節點破壞堆序性
根節點向下調整
建堆
亂序數組如何轉換成堆？
自頂向下
插入堆，上濾
複雜度：O(NlogN)
由下而上
先把元素調整成堆，下濾，從倒數第二行開始，對父節點下濾操作
複雜度：O(N)
應用：優先隊列
兩個操作
插入隊列
彈出最小元素
可以用小根堆實現
因為小根堆的根節點是min，彈出後將剩餘元素調整成堆（將最後一個元素置於根節點，下濾）
堆排序：將優先隊列的元素依序彈出
Wondershare EdrawMind
