資料結構›Ch9 進階樹第 2 題／共 88 題
2. Huffman Coding、貪心演算法
#DS-09-002易Huffman Coding貪心演算法
Which of the following properties is true for some optimal prefix-free binary code and directly justifies the greedy choice made in the Huffman algorithm?
參考答案與解析
答案 (E)：這是 Huffman 演算法貪心選擇成立的關鍵引理——一定存在某個最佳前綴碼，讓「頻率最低的兩個符號」互為兄弟節點，且都位於樹的最大深度。這保證了每次貪心合併最小的兩個頻率是安全的。(A)(B)(C)(D) 都不夠精確或不成立（例如(D)說「不需共享同一父節點」正好與正確結論相反）。
📄 台大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch9 進階樹