樹狀結構 陳怡芬 2018/11/16 北一女中資訊專題研究

樹 2018/11/16 北一女中資訊專題研究

樹狀結構的定義 定義：樹狀結構是一個或多個節點的有限集合，它滿足： 有一個特定的節點稱為根節點（root）， 其餘的節點分成n0個獨立的集合T1, …, Tn，每個集合也都是一個樹狀結構。我們稱T1, …, Tn為根節點的子樹（subtree）。 2018/11/16 北一女中資訊專題研究

不合法的樹狀結構 2018/11/16 北一女中資訊專題研究

子樹 2018/11/16 北一女中資訊專題研究

分支度(degree)：節點的子樹個數 A B C D E F G H I 3 2 1 1 1 2018/11/16 北一女中資訊專題研究

樹葉 A D B C H E F G I 2018/11/16 北一女中資訊專題研究

樹葉 A D B C H E F G I 2018/11/16 北一女中資訊專題研究

父節點、兄弟、祖先、後代 A D B C H E F G I 2018/11/16 北一女中資訊專題研究

階層 Level 1 A B C D E F G H I Level 2 Level 3 Level 4 2018/11/16 北一女中資訊專題研究

注意 有些書的階層定義由0開始而不是1. 樹根在階層0. 我們將以樹根的階層為1. 2018/11/16 北一女中資訊專題研究

高度 =深度 =最大的階層數 Level 1 A B C D E F G H I Level 2 Level 3 Level 4 高度 =深度 =最大的階層數 Level 1 A B C D E F G H I Level 2 Level 3 Level 4 2018/11/16 北一女中資訊專題研究

二元樹 節點的有限集合 非空二元樹包含一個根節點 其他節點可以視為兩個獨立的二元樹 分別稱為左子樹和右子樹。 2018/11/16 北一女中資訊專題研究

樹與二元樹的不同 樹的分支度沒有限制，但是二元樹的分支度不能超過2 二元樹可以是空的，但是樹不行 二元樹的子樹有左右順序關係，樹沒有 2018/11/16 北一女中資訊專題研究

二元樹的特性 2018/11/16 北一女中資訊專題研究

最少節點 高度為 h二元樹之最少節點數為h. 每一個階層有一個節點 最少節點數為h 2018/11/16 北一女中資訊專題研究

最多節點 二元樹的每一個階層都有兩個節點 最多節點 = 1 + 2 + 4 + 8 + … + 2h-1 = 2h - 1 2018/11/16 北一女中資訊專題研究

節點數與高度 令 n 為高度 h 的二元樹之節點數. h <= n <= 2h – 1 log2(n+1) <= h <= n 2018/11/16 北一女中資訊專題研究

完全二元樹 每一個階層都擁有最大可能的節點數 高度為4的完全二元樹 2018/11/16 北一女中資訊專題研究

完全二元樹的節點編號 編號由 1 到 2h – 1 從最上階層往下到最下階層 同一階層中由左至右 1 2 3 4 6 5 7 8 9 10 11 12 13 14 15 2018/11/16 北一女中資訊專題研究

節點編號之性質 如果i1，則節點i的父節點，parent(i)，位於i/2。 如果i=1，則i為根節點，因此沒有父節點。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 如果i1，則節點i的父節點，parent(i)，位於i/2。 如果i=1，則i為根節點，因此沒有父節點。 2018/11/16 北一女中資訊專題研究

節點編號之性質 如果2in，則節點i的左子節點，left_child(i)，位於2i。 如果2i>n，則i沒有左子節點。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 如果2in，則節點i的左子節點，left_child(i)，位於2i。 如果2i>n，則i沒有左子節點。 2018/11/16 北一女中資訊專題研究

節點編號之性質 如果2i+1n，則節點i的右子節點，right_child(i)，位於2i+1。 3 4 5 6 7 8 9 10 11 12 13 14 15 如果2i+1n，則節點i的右子節點，right_child(i)，位於2i+1。 如果2i+1>n，則i沒有右子節點。 2018/11/16 北一女中資訊專題研究

完整二元樹 是完全二元樹從後面依序去掉幾個節點所產生的樹 編號順序和完全二元樹一樣 2018/11/16 北一女中資訊專題研究

例子 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10個節點的完整二元樹 2018/11/16 北一女中資訊專題研究

歪斜二元樹 2018/11/16 北一女中資訊專題研究

二元樹的儲存方式 陣列表示法 鏈結表示法 2018/11/16 北一女中資訊專題研究

陣列表示法 編號順序和完全二元樹一樣 編號 i 的節點放在 tree[i]. tree[] b a c d e f g h i j 1 2 3 4 5 6 7 8 9 10 tree[] 5 10 a b c d e f g h i j 2018/11/16 北一女中資訊專題研究

右歪斜二元樹 tree[] 一棵 n 個節點的二元樹需要的陣列大小介於 n+1 與 2n. a b 1 3 c 7 d 15 5 10 a 5 10 a - b c 15 d 一棵 n 個節點的二元樹需要的陣列大小介於 n+1 與 2n. 2018/11/16 北一女中資訊專題研究

鏈結表示法 2018/11/16 北一女中資訊專題研究

鏈結表示法 a c b d f e g h leftChild 資料 rightChild root 2018/11/16 北一女中資訊專題研究

樹轉換成二元樹 刪除所有節點的右鏈結，只保留下左鏈結； 將原來樹中同屬於一個父節點的兄弟用鏈結連接起來； 將整個圖形以順時針方向旋轉45°。 2018/11/16 北一女中資訊專題研究

樹轉換成二元樹 原始的樹 2018/11/16 北一女中資訊專題研究

樹轉換成二元樹 保留所有節點的左鏈結，其餘都刪除， 2018/11/16 北一女中資訊專題研究

樹轉換成二元樹 將原來的兄弟節點用鏈結連接起來， 2018/11/16 北一女中資訊專題研究

樹轉換成二元樹 順時針方向旋轉45° 2018/11/16 北一女中資訊專題研究

將樹林轉成二元樹的方法 首先將各樹樹根連結起來； 刪除所有節點之右鏈結，只留下左鏈結； 將原來樹中同屬於一個父節點的兄弟用鏈結連接起來； 將整個圖形以順時針方向旋轉45° 2018/11/16 北一女中資訊專題研究

將樹林轉成二元樹的方法 樹林 2018/11/16 北一女中資訊專題研究

將樹林轉成二元樹的方法 將各樹樹根連結起來 2018/11/16 北一女中資訊專題研究

將樹林轉成二元樹的方法 刪除所有的右鏈結，只留下左鏈結 2018/11/16 北一女中資訊專題研究

將樹林轉成二元樹的方法 將原來樹中的兄弟用鏈結連接起來 2018/11/16 北一女中資訊專題研究

將樹林轉成二元樹的方法 順時針方向旋轉45° 2018/11/16 北一女中資訊專題研究

建立算術運算之二元樹 + a b a + b - a - a 2018/11/16 北一女中資訊專題研究

建立算術運算之二元樹 (a + b) * (c – d) / (e + f) / + a b - c d e f * 2018/11/16 北一女中資訊專題研究

Merits Of Binary Tree Form* Left and right operands are easy to visualize. Code optimization algorithms work with the binary tree form of an expression. Simple recursive evaluation of expression. + a b - c d * / 2018/11/16 北一女中資訊專題研究

建立算術運算之二元樹 考慮運算子的優先次序與結合性，適當地加以括號； 由內層的括號逐次向外，並且以運算子當樹根，左邊運算元當左子樹，右邊運算元當右子樹。 2018/11/16 北一女中資訊專題研究

建立算術運算之二元樹 將A*B+C**D-E建成二元樹 按照運算子的優先權和結合性加以適當括號，得到(((A*B)+(C**D))-E) 2018/11/16 北一女中資訊專題研究

建立算術運算之二元樹 ((A*B)+(C**D)) 2018/11/16 北一女中資訊專題研究

建立算術運算之二元樹 (((A*B)+(C**D))-E) 2018/11/16 北一女中資訊專題研究

建立算術運算之二元樹 (((A/(B**C)+(D*E))-(A*C)) 2018/11/16 北一女中資訊專題研究

二元樹之尋訪 尋訪樹狀結構，即走訪樹中的每一個節點，並且每個節點恰好被尋訪一次 中序追蹤 先序追蹤 後序追蹤 階層式尋訪 2018/11/16 北一女中資訊專題研究

中序尋訪法 走訪左子樹(遞迴)； 走訪樹根； 走訪右子樹(遞迴)。 2018/11/16 北一女中資訊專題研究

中序尋訪法(visit = print) a b c b a c 2018/11/16 北一女中資訊專題研究

中序尋訪法(visit = print) g d h b e i a f j c a b c d e f g h i j 2018/11/16 北一女中資訊專題研究

中序尋訪法 ─ 投影法 g d h b e i a f j c a b c d e f g h i j 2018/11/16 北一女中資訊專題研究

中序尋訪法 + a b - c d e f * / e a + b * c d / f - 2018/11/16 北一女中資訊專題研究

先序尋訪法 走訪樹根； 走訪左子樹(遞迴)； 走訪右子樹(遞迴)。 2018/11/16 北一女中資訊專題研究

先序尋訪法 (visit = print) a b c a b c 2018/11/16 北一女中資訊專題研究

先序尋訪法 (visit = print) a b d g h e i c f j a b c d e f g h i j 2018/11/16 北一女中資訊專題研究

先序尋訪法 + a b - c d e f * / / * + a b - c d + e f 2018/11/16 北一女中資訊專題研究

後序尋訪法 走訪左子樹(遞迴)； 走訪右子樹(遞迴)； 走訪樹根。 2018/11/16 北一女中資訊專題研究

後序尋訪法 (visit = print) a b c b c a 2018/11/16 北一女中資訊專題研究

後序尋訪法 (visit = print) g h d i e b j f c a a b c d e f g h i j 2018/11/16 北一女中資訊專題研究

後序尋訪法 + a b - c d e f * / a b + c d - * e f + / 2018/11/16 北一女中資訊專題研究

階層式尋訪 尋訪結果：+-/+DEFA*BC 2018/11/16 北一女中資訊專題研究

尋訪之應用 a b c d e f g h i j 複製二元樹 測試兩棵二元樹是否相等 決定樹的高度或者節點數目 2018/11/16 北一女中資訊專題研究

階層式尋訪 Let t be the tree root. while (t != null) { visit t and put its children on a FIFO queue; remove a node from the FIFO queue and call it t; } 2018/11/16 北一女中資訊專題研究

階層式尋訪(visit = print) a b c d e f g h i j a b c d e f g h i j 2018/11/16 北一女中資訊專題研究

Binary Tree Construction* Suppose that the elements in a binary tree are distinct. Can you construct the binary tree from which a given traversal sequence came? When a traversal sequence has more than one element, the binary tree is not uniquely defined. Therefore, the tree from which the sequence was obtained cannot be reconstructed uniquely. 2018/11/16 北一女中資訊專題研究

Some Examples* preorder = ab inorder = ab postorder = ab level order = ab a b a b 2018/11/16 北一女中資訊專題研究

Binary Tree Construction* Can you construct the binary tree from which two given traversal sequences came? Depends on which two sequences are given. 2018/11/16 北一女中資訊專題研究

Preorder And Postorder* b a b preorder = ab postorder = ba Preorder and postorder do not uniquely define a binary tree. Nor do preorder and level order (same example). Nor do postorder and level order (same example). 2018/11/16 北一女中資訊專題研究

Inorder And Preorder* inorder = g d h b e i a f j c preorder = a b d g h e i c f j Scan the preorder left to right using the inorder to separate left and right subtrees. a is the root of the tree; gdhbei are in the left subtree; fjc are in the right subtree. a gdhbei fjc 2018/11/16 北一女中資訊專題研究

Inorder And Preorder* preorder = a b d g h e i c f j gdhbei afjc preorder = a b d g h e i c f j b is the next root; gdh are in the left subtree; ei are in the right subtree. a gdh afjc b ei 2018/11/16 北一女中資訊專題研究

Inorder And Preorder* preorder = a b d g h e i c f j gdh afjc b ei preorder = a b d g h e i c f j d is the next root; g is in the left subtree; h is in the right subtree. a g afjc b ei d h 2018/11/16 北一女中資訊專題研究

Inorder And Postorder* Scan postorder from right to left using inorder to separate left and right subtrees. inorder = g d h b e i a f j c postorder = g h d i e b j f c a Tree root is a; gdhbei are in left subtree; fjc are in right subtree. 2018/11/16 北一女中資訊專題研究

Inorder And Level Order* Scan level order from left to right using inorder to separate left and right subtrees. inorder = g d h b e i a f j c level order = a b c d e f g h i j Tree root is a; gdhbei are in left subtree; fjc are in right subtree. 2018/11/16 北一女中資訊專題研究

引線二元樹* 如果節點V的左鏈結指向NULL時，將這個鏈結改指向一個節點，被指到的節點為節點V的中序前行者 2018/11/16 北一女中資訊專題研究

引線二元樹* 2018/11/16 北一女中資訊專題研究

引線二元樹* 2018/11/16 北一女中資訊專題研究

最小樹是一種樹， 其中每一個節點的鍵值都不大於它的子節點（如果有的話）的鍵值 2018/11/16 北一女中資訊專題研究

最小樹 2 4 9 3 4 8 7 9 9 樹根的值最小 2018/11/16 北一女中資訊專題研究

最大樹 9 4 9 8 4 2 7 3 1 樹根的值最大 2018/11/16 北一女中資訊專題研究

最小堆積 完整二元樹 最小樹 2018/11/16 北一女中資訊專題研究

最小堆積 9 個節點的完整二元樹 2018/11/16 北一女中資訊專題研究

最小堆積 2 4 3 6 7 9 3 8 6 也是最小堆積的9 個節點的完整二元樹 2018/11/16 北一女中資訊專題研究

最大堆積 9 8 7 6 7 2 6 5 1 也是最大堆積的9 個節點的完整二元樹 2018/11/16 北一女中資訊專題研究

由於堆積是一棵完整二元樹，因此n個節點的堆積其高度為log2(n+1) 2018/11/16 北一女中資訊專題研究

陣列可以有效地表示堆積 9 8 7 6 7 2 6 5 1 9 8 7 6 7 2 6 5 1 1 2 3 4 5 6 7 8 9 10 2018/11/16 北一女中資訊專題研究

堆積之向上下移動 1 9 2 3 8 7 4 7 5 6 6 7 2 6 5 1 8 9 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 9 8 7 6 7 2 6 5 1 7 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 9 8 7 6 7 2 6 5 1 7 5 加入 5 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 9 8 7 6 7 2 6 5 1 7 7 加入 20 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 9 8 7 6 2 6 5 1 7 7 7 加入 20 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 9 7 6 8 2 6 5 1 7 7 7 加入 20 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 20 9 7 6 8 2 6 5 1 7 7 7 加入 20 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 20 9 7 6 8 2 6 5 1 7 7 7 完成 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 20 9 7 6 8 2 6 5 1 7 7 7 加入 15 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 20 9 7 6 2 6 5 1 7 7 8 7 8 加入 15 2018/11/16 北一女中資訊專題研究

插入新的元素到堆積 20 15 7 6 9 2 6 5 1 7 7 8 7 8 加入 15 2018/11/16 北一女中資訊專題研究

複雜度為O(log n), 其中 n 為堆積之大小 加入新元素之複雜度 20 15 7 6 9 2 6 5 1 7 7 8 7 8 複雜度為O(log n), 其中 n 為堆積之大小 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 最大元素在樹根 20 15 7 6 9 2 6 5 1 7 7 8 7 8 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 15 7 6 9 2 6 5 1 7 7 8 7 8 刪除最大元素後 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 重新將8插入堆積 10 個節點的堆積 15 7 6 9 2 6 5 1 7 7 8 7 8 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 15 7 6 9 2 6 5 1 7 7 7 重新將8插入堆積 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 15 7 6 9 2 6 5 1 7 7 7 重新將8插入堆積 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 15 9 7 6 8 2 6 5 1 7 7 7 重新將8插入堆積 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 15 9 7 6 8 2 6 5 1 7 7 7 最大元素為 15 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 9 7 6 8 2 6 5 1 7 7 7 刪除最大元素後 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 9 7 6 8 2 6 5 1 7 7 7 9個節點的堆積 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 9 7 6 8 2 6 5 1 重新將7插入堆積 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 9 7 6 8 2 6 5 1 重新將7插入堆積 2018/11/16 北一女中資訊專題研究

從堆積中刪除最大的元素 9 8 7 6 7 2 6 5 1 重新將7插入堆積 2018/11/16 北一女中資訊專題研究

刪除最大的元素之複雜度 9 8 7 6 7 2 6 5 1 複雜度為O(log n). 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 2 3 4 5 6 7 8 9 10 7 7 11 8 輸入 array = [-, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 2018/11/16 北一女中資訊專題研究

最大堆積之起始 從有兒子節點的最後一個節點開始 索引值為 n/2 1 2 3 4 5 6 7 8 9 11 10 7 7 8 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 2 3 4 11 6 7 8 9 10 7 7 5 8 換下一個位置 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 2 3 4 11 6 7 8 9 5 10 7 7 8 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 2 3 9 11 6 7 8 4 5 10 7 7 8 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 2 3 9 11 6 7 8 4 5 10 7 7 8 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 2 7 9 11 6 3 8 4 5 10 7 7 8 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 2 7 9 11 6 3 8 4 5 10 7 7 8 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 11 7 9 6 3 8 4 5 10 7 7 8 給 2找家 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 11 7 9 10 6 3 8 4 8 7 7 5 給 2找家 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 11 7 9 10 6 3 8 4 7 7 2 5 8 完成！換下一個位置 2018/11/16 北一女中資訊專題研究

最大堆積之起始 1 11 7 9 10 6 3 8 4 7 7 2 5 8 給 1找家 2018/11/16 北一女中資訊專題研究

最大堆積之起始 11 7 9 10 6 3 8 4 7 7 2 5 8 給 1找家 2018/11/16 北一女中資訊專題研究

最大堆積之起始 11 10 7 9 6 3 8 4 7 7 2 5 8 給 1找家 2018/11/16 北一女中資訊專題研究

最大堆積之起始 11 10 7 9 5 6 3 8 4 7 7 2 8 給 1找家 2018/11/16 北一女中資訊專題研究

最大堆積之起始 11 10 7 9 5 6 3 8 4 7 7 2 1 8 完成！ 2018/11/16 北一女中資訊專題研究

Time Complexity* Height of heap = h. 11 9 7 8 5 6 3 1 4 10 7 7 8 2 Height of heap = h. Number of subtrees with root at level j is <= 2(j-1). Time for each subtree is O(h-j+1). 2018/11/16 北一女中資訊專題研究

Complexity* Time for level j subtrees is <= 2(j-1) x (h-j+1) = t(j). Total time is t(1) + t(2) + … + t(h-1) = O(n). 2018/11/16 北一女中資訊專題研究

二元搜尋樹 二元樹 每一個元素有一鍵值，而且每一個元素的鍵值都不相同，即鍵值是唯一的。 非空的左子樹上的鍵值必須小於該子樹的根節點之鍵值。 在非空的右子樹上的鍵值必須大於在該子樹的根節點之鍵值。 左子樹和右子樹也都是二元搜尋樹。 2018/11/16 北一女中資訊專題研究

二元搜尋樹 20 10 40 6 15 30 25 2 8 只顯示鍵值 2018/11/16 北一女中資訊專題研究

加入一個元素 20 10 40 6 15 30 25 35 2 8 加入一個鍵值為 35 的元素 2018/11/16 北一女中資訊專題研究

加入一個元素 20 10 40 6 15 30 25 35 2 8 7 加入一個鍵值為 7 的元素 2018/11/16 北一女中資訊專題研究

加入一個元素 20 10 40 6 15 30 18 25 35 2 8 7 加入一個鍵值為 18 的元素 2018/11/16 北一女中資訊專題研究

加入一個元素 複雜度為 O(height) 20 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 20 10 40 6 15 30 18 25 35 2 8 7 刪除一個鍵值為 7 的樹葉 2018/11/16 北一女中資訊專題研究

刪除一個元素 20 10 40 6 15 30 18 25 35 2 8 7 刪除一個鍵值為 35 的樹葉 2018/11/16 北一女中資訊專題研究

刪除一個元素 刪除一個鍵值為 40 而且分支度為 1 的節點 20 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 刪除一個鍵值為 15 而且分支度為 1 的節點 20 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 刪除一個鍵值為 10 而且分支度為 2 的節點 20 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 跟左子樹中具有最大值的節點或者右子樹中含最小值的節點互換 20 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 跟左子樹中具有最大值的節點或者右子樹中含最小值的節點互換 20 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 跟左子樹中具有最大值的節點或者右子樹中含最小值的節點互換 20 8 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 最大鍵值必定在樹葉或者分支度為1的節點 20 8 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 刪除一個鍵值為 20 而且分支度為 2 的節點 20 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 跟左子樹中具有最大值的節點互換 20 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 跟左子樹中具有最大值的節點互換 20 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 跟左子樹中具有最大值的節點互換 18 10 40 6 15 30 18 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

刪除一個元素 複雜度為 O(height) 18 10 40 6 15 30 25 35 2 8 7 2018/11/16 北一女中資訊專題研究

霍夫曼編碼 根據所有可能符號的出現機率建立一棵霍夫曼樹 第一步：令自由節點為所有的樹葉； 第二步：從自由節點中找出加權值最小的兩個節點； 第三步：為這兩個節點做一個父親節點，他的加權值為這兩個兒子節點的加權值和； 第四步：將父親節點加入自由節點的行列而兩個兒子節點則從自由節點的行列中除名； 第五步：由父親節點做到兩個兒子節點的兩枝樹枝，一枝給0另一枝給1； 第六步：重覆執行第二步到第五步直到只剩下一個自由節點，此為樹根。 2018/11/16 北一女中資訊專題研究

霍夫曼編碼 15 7 6 6 5 A B C D E 2018/11/16 北一女中資訊專題研究

霍夫曼編碼 Sk p(sk) Code 1 霍夫曼碼 0 0.19 000 11 1 0.25 001 01 2 0.21 010 10 0 0.19 000 11 1 0.25 001 01 2 0.21 010 10 3 0.16 011 001 4 0.08 100 0001 5 0.06 101 00001 6 0.03 110 000001 7 0.02 111 000000 Lavg(Code 1)=3 2018/11/16 北一女中資訊專題研究

四分樹 2018/11/16 北一女中資訊專題研究

四分樹 2018/11/16 北一女中資訊專題研究

四分樹 2018/11/16 北一女中資訊專題研究

四分樹 2018/11/16 北一女中資訊專題研究

四分樹 2018/11/16 北一女中資訊專題研究

四分樹 2018/11/16 北一女中資訊專題研究

四分樹 2018/11/16 北一女中資訊專題研究