從代碼表構建huffman樹

我對如何從代碼表構建huffman樹感到困惑。該代碼表包括2列，字符串碼（二進制介紹）和SYMB（十六進制值）從代碼表構建huffman樹

的symbCode結構體：

struct symbCode 
{ 
char symb; 
string code; //string of '0' and '1' 
};

的功能：

void huffmanTree::buildTreeFromCodeTable(symbCode *table, int n) 
{ 
//construct the Huffman tree from the code table 
//n = number of symbols in the code table 

}

我已經一派一些提供huffman樹教程的網站。但我仍然無法弄清楚。我應該新建一個樹節點還是做其他事情？

參考表：

Num_Alphabet 96 
ASCII Huffman_Code 
    a  011000 
20  0100 
21  11101110110 
22  1110111010 
23  11101111000 
24  11101111001 
25  11110100001 
26  0000010000 
27  0000010001 
28  100100100 
29  100100101 
2a  000000100 
2b  000000101 
2c  0110010 
2d  101101000 
2e  1110010 
2f  0000000110 
30  11110101 
31  11110110 
32  11110111 
33  11111010 
34  11111011 
35  11111100 
36  11111101 
37  11111110 
38  11111111 
39  0000011 
3a  101101001 
3b  01100110 
3c  000001001 
3d  00000011 
3e  000000000 
3f  01100111 
40  0000000111 
41  00011 
42  1110011 
43  001010 
44  011010 
45  01010 
46  001000 
47  1110110 
48  1001000 
49  10101 
4a  0010011 
4b  1000001 
4c  011111 
4d  100001 
4e  010110 
4f  00010 
50  1111100 
51  00000101 
52  010111 
53  10100 
54  110000 
55  110011 
56  10010011 
57  100000010 
58  000000001 
59  10110101 
5a  000000010 
5b  11101111100 
5c  11101111101 
5d  11101111110 
5e  11101111111 
5f  11101110010 
60  11101110011 
61  10001 
62  100101 
63  110001 
64  110010 
65  10011 
66  101111 
67  101100 
68  011110 
69  11010 
6a  001011 
6b  011011 
6c  111100 
6d  00001 
6e  111010 
6f  01110 
70  101110 
71  111101001 
72  111000 
73  11011 
74  00110 
75  00111 
76  0010010 
77  10000000 
78  100000011 
79  1011011 
7a  1111010001 
7b  1110111101 
7c  11110100000 
7d  1110111000 
7e  11101110111

來源

2013-11-28 Ruka Tsoi

霍夫曼樹是根據字符串中符號的頻率構建的。那麼考慮到哪些參考？ – StoryTeller

@StoryTeller添加了參考。 –

我想這個表的想法是你開始從樹的根部插入每個符號。二進制序列描述了你需要從根節點到目標節點的路徑。將「0」解釋爲「左孩子」和「1」作爲「右孩子」，以便在樹上找到自己的路。但要求這個由Stackoverflow用戶編寫的代碼是不合適的。 – jogojapan

使用二叉樹，併爲每個節點有兩個路徑：左孩子，右孩子。對於左邊的孩子意味着0，對於右邊的孩子意味着1.在整棵樹完成後，從根到葉子節點，路徑（1s和0s的序列）是葉子節點中值的代碼。

因此，表中的每個代碼實際上是從根到葉的路徑。選擇一個接一個的代碼，檢查從根（和左邊的代碼）的路徑，如果不存在，創建所有節點（包括葉）;如果部分存在（代碼中的左數字相同），請完成葉子的路徑。

來源

2013-11-29 02:13:36 SliceSort

從代碼表構建huffman樹

回答

相關問題