CODEWITHSUNDEEP
c++treeasciihuffman-code
Ruka Tsoi
Ruka Tsoi

Reputation: 45

Build a huffman tree from a code table

I am confused about how to build a huffman tree from a code table. The code table consists of 2 columns, the string code (binary presentation) and symb (the hexadecimal value)

the symbCode struct:

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

the Function:

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

}

I have googled a few websites providing tutorials for huffman tree. But I still can't figure it out. Should i new a tree node or do something else?

The reference table:

 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

Upvotes: 0

Views: 2849

Answers (1)

SliceSort
SliceSort

Reputation: 375

Use binary tree, and for every node you have two path: to left child, and to right child. To left child means 0, to right child means 1. After whole tree is completed, from root to a leaf node, the path (sequenct of 1s and 0s) is the code of the value in leaf node.

So, every code in your table is actually a path from root to leaf. Pick codes one by one, check the path from root(and the code from left), if not exist, creat all nodes (including leaf); if partially exist(leftist numbers in code are same), complete the path to leaf.

Upvotes: 2

Related Questions