Re: [問題] 列出Huffman code的演算法
雖然是個很久以前問過的問題
不過剛好最近有處理到Huffman編CodeBook的問題
想了一個演算法，讓大家見笑好了：
先來設一下Node的struct內容
struct Node
{
int Filter;
string BitCode;
Node *LeftChild;
Node *RightChild;
};
void PostOrderEncode(Node *node, string LRBit, string FatherBitCode)
{
node-BitCode = FatherBitCode + LRBit;
if (node->LeftChild != NULL)
PostOrderEncode(node->LeftChild, "0", node->BitCode);
if (node->RightChild != NULL)
PostOrderEncode(node->RightChild, "1", node->BitCode);
if (node->Filter != -1)
cout <<node->BitCode <<endl;
}
由於建立Huffman時，會有非Leaf Node的中間節點
中間節點的部份，通常把值設為-1，因為如果是處理圖片的Pixel是不能用0的
設這個參數在Node的結構中，主要是方便過濾而已，不設並不影響
使用此PostOrderEncode Function，一開始想當然爾是丟入root點
也就會變成：PostOrderEncode(root, "", "");
在LRBit這個參數中，所代表的是你往左或是往右搜尋
也就是下一個節點應該在BitCode後面加入的編碼
而FatherBitCode的部份，則是目前這個節點的BitCode
也就是將目前節點和下一個節點應該編碼的字串結合，就成了此節點的BitCode
故此可編出所有Leaf的BitCode
最後講一下過濾，就是印出非末端節點的BitCode，中間節點的BitCode與我們無關
以上，一些小小的心得分想
感謝有興趣的人撥空收看
--
ˍˍ
很多人在即將失去的時候，不知他即將失去，最後他就真正失去 ▕天險▏
其實，一個不曾失去的人最可憐。因為，他永遠學不會什麼叫珍惜。▕刀藏▏
￣￣
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.118.10.197
※ 編輯: godman362 來自: 122.118.0.12 (04/10 07:11)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：