Huffman Code: Binary Tree construction for given message by huffman algorithm

Construction Of Huffman tree for a given message

Step You have to follow:

Arrange all letters in the increasing order of their frequency and then construct binary tree by assigning least frequency letter as left child to the tree. After constructing binary tree from root to leaf every left branch assigned with 0 and right branch assigned with 1.
Notes: You can also take minimum frequency at right side or assigned it with 0 but be consistent whatever you choose.

Example:   Message contains “EEEABBCCDDEEE” what will be total minimum bits required for store it.

Symbol    Frequency
A       ==   1
B       ==   2
C       ==   2
D       ==   2
E       ==   6

Step 1: Find two char with minimum frequency

   [3]
0/     \1
A       B

Now we have
Weight gain from adding two minimum char ==> [3]
C ==> 2

D ==> 2

E ==> 6

Now Find again 2 minimum and add it Here c => 2 and d => 2 is minimum

  [4]
0/   \1
C     D

Now we have wright [4] , [3], E=> 6 Here minimum is 4 and 3 so merge both above diagram.
      [7]
   0/      \1
  [3]       [4]
 0/ \1    0/   \1
 A   B    C     D

Now we have wright [7], E=> 6 Here we have remaining 2 so merge both above diagram.
   [13]
0/    \1
E      [7]
     0/   \1
    [3]   [4]
   0/ \1  0/ \1
   A   B  C   D

=================================================
Symbol Frequency Code Code Length total Length
A       1         100    3             3
B       2         101    3             6
C       2         110    3             6
D       2         111    3             6
E       6          0     1             6
=================================================
                                   Total=27 Bit required.


Another Good Resource
Advertisements

One thought on “Huffman Code: Binary Tree construction for given message by huffman algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s