410 Intermediate C Programming
FIGURE 24.8: A list of tree nodes. This figure shows the list as it is being built. The tree
is the same as the one shown in Fig. 24.4 (c).
24.2.4 Build a Code Book
The next step creates the code book from the tree. We use a two-dimensional array
to store the code book. In each row, the first column stores the character. The remaining
columns store the code, i.e., the bit-sequence for the character. The maximum length of a
code is the tree’s height minus one since the root itself is counted as one when computing
the height. The number of rows is the number of leaf nodes. For the tree in Fig. 24.7, the
height is 8 and there are 8 leaf nodes. In general, the tree’s height is much smaller than the
number of leaf nodes. For example, the tree for the Charter of the United Nations has 57
leaf nodes but the tree’s height is only 12. The following table shows the two-dimensional
array for the code book. Since the codes’ lengths are different, −1isusedtoterminatea
sequence of bits.
Huffman Compression 411
FIGURE 24.9: Display the tree in DDD.
index character code
[0] → h 0 −1
[1] → d 1 0 −1
[2] → p 1 1 0 −1
[3] → T 1 1 1 0 0 −1
[4] → E 1 1 1 0 1 0 0 −1
[5] → N 1 1 1 0 1 0 1 −1
[6] → G 1 1 1 0 1 1 −1
[7] → g 1 1 1 1 −1
Do you notice that only one row (for ’h’) has 0 in the first column? The reason for this
is that there is only one node on the left side of the root. There are seven nodes on the
right side of the root and ones are filled to the first column of seven rows. From the root,
after moving down to the right child, there is only one node on the left side (for ’d’). As a
result, only one row has zero in column 2. The other six rows have ones in column 2.
Fig. 24.10 shows the general rule. If there are n leaf nodes on the left side of a node,
zeros are filled in n rows. The column of the zeros is determined by the distance to the
root. If the node is the root itself, then the first column is used. Similarly, if there are m
leaf nodes on the right side, ones are filled in m rows.
The following functions compute the height of a tree and the number of leaf nodes. To
determine a tree’s height, the function recursively computes the heights of the left subtree
and the right subtree. Then the function chooses the taller of the two subtrees. To determine
the number of leaf nodes, the function increments a counter when a leaf node is encountered.
A leaf node is a node that has no children nodes.
s t a t i c i n t Tr ee_he i ghtHe lper ( T r eeNode * tn , i nt height )1
{2
412 Intermediate C Programming
(a) (b)
FIGURE 24.10: If there are n leaf nodes on the left side, zeros should be filled in n rows.
The column is determined by the distance from the root.
i f ( tn == 0)3
{4
return height ;5
}6
int lh = Tree _heig h tHel p er ( tn -> left , height + 1) ;7
int rh = Tree _heig h tHel p er ( tn -> right , height + 1);8
i f ( lh < rh )9
{10
return rh;11
}12
i f ( lh > rh )13
{14
return lh;15
}16
return lh;17
}18
19
int Tree_he ight ( TreeNode * tn)20
{21
return Tre e_hei ghtHe lper (tn , 0) ;22
}23
24
s t a t i c void Tree_l eafHe l per ( TreeNo d e * tn , in t * num )25
{26
i f ( tn == 0)27
{28
return ;29
}30
// if it is a leaf node , add one31
TreeNode * lc = tn -> left ;32
TreeNode * rc = tn -> right ;33
i f (( lc == NULL ) && ( rc == NULL ) )34
{35
Huffman Compression 413
(* num ) ++;36
return ;37
}38
Tree _leafH elper (lc , num );39
Tree _leafH elper (rc , num );40
}41
42
int Tree_leaf ( Tr e eN ode * tn )43
{44
int num = 0;45
Tree _leafH elper (tn , & num ) ;46
return num ;47
}48
The following listing is part of the encode function after the code tree has been built.
// the linked list is no longer needed1
TreeNode * root = head -> tnptr ;2
free ( head );3
4
// build the code book5
// get the number of leaf nodes6
int numRow = Tree_l e af ( root );7
// get the tree ’s height8
int numCol = Tree _height ( root );9
// numCol should add 1 to a ccommoda t e the ending -110
numCol ++;11
// create a 2D array initializ e the codes to -112
int * * c o debook = malloc ( s i z e o f ( i nt *) * numRow ) ;13
int row ;14
for ( row = 0; row < numRow ; row ++)15
{16
codebook [ row ] = malloc ( s i z e o f ( i nt ) * numCol ) ;17
int col ;18
// ini tialize to -119
for ( col = 0; col < numCol ; col ++)20
{21
codebook [ row ][ col ] = -1;22
}23
}24
build CodeBoo k ( root , codebook );25
print CodeBoo k ( codebook , numRow );26
return 1;27
}28
The following listing shows the function buildCodeBook. It uses a recursive helper func-
tion to traverse the tree. When a leaf node is encountered, the character is stored. At line
14, the function uses the very first column (with index zero) to store the characters. The
code book codes start from the second index (i.e., index 1), which is passed as the fourth
argument to buildCodeBookHelper at line 44.
void buil dCod e Book Helpe r ( TreeNode * tn , i n t * * codebook ,1
int * row , in t col )2
414 Intermediate C Programming
{3
i f ( tn == NULL )4
{5
return ;6
}7
// is it a leaf node ?8
TreeNode * lc = tn -> left ;9
TreeNode * rc = tn -> right ;10
i f (( lc == NULL ) && ( rc == NULL ) ) // it is a leaf node11
{12
// finish one code13
codebook [* row ][0] = tn -> value ; // the character14
(* row ) ++; // finish one row15
return ;16
}17
i f ( lc != NULL )18
{19
// populat e this column of the entire s u b t r e e20
int numRow = Tree_le af ( lc );21
int ind ;22
for ( ind = * row ; ind < (* row ) + numRow ; ind ++)23
{24
codebook [ ind ][ col ] = 0;25
}26
buil dCod e Book Helpe r ( lc , codebook , row , col + 1) ;27
}28
i f ( rc != NULL )29
{30
int numRow = Tree_le af ( rc );31
int ind ;32
for ( ind = * row ; ind < (* row ) + numRow ; ind ++)33
{34
codebook [ ind ][ col ] = 1;35
}36
buil dCod e Book Helpe r ( rc , codebook , row , col + 1) ;37
}38
}39
void build CodeBoo k ( T reeNode * root , i n t * * cod e book )40
{41
int row = 0;42
// column start at 1 , column = 0 stores the char a cter43
buil dCod e Book Helpe r ( root , codebook , & row , 1) ;44
}45
46
void print CodeBoo k ( i n t * * codebook , i n t numRow )47
{48
int row ;49
for ( row = 0; row < numRow ; row ++)50
{51
// print the characte r52
printf (" %c: " , code b oo k [ row ][0]) ;53
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.