Chapter 11: Q21E (page 770)
what are the codes for a, e, i, k, o, p, and u if the coding scheme is represented by this tree?
Short Answer
a:000, e:001, i:01, k:1100, o:1101, p:11110, u:11111.
Step by step solution
Over 22 million students worldwide already upgrade their learning with Vaia!
Use the given binary tree.
When a prefix code is represented by the binary tree, the characters are the labels of the leaves in the tree and the edges are the tree are labelled by bits. The bit strings from root to leaf from the characters.
The edges of this tree are labelled so that from the root an edge leading to left is assigned a 0 and edge leading to right assigned a 1. From the figure, following every left of leaves, the bit string 000 represents the character a.
Starting from the root leading to left is assigned a 0 and edge leading to right assigned a 1 give a bit sting 01 and is represented by the character i.
Starting from the root leading to left is assigned a 0 and edge leading to left is assigned a 0 and an edge leading to right assigned a 1 give a bit string 001 and is represented by the character e.
Final conclusion.
Starting from the root leading to right assigned a 1 and edge leading to right assigned a 1 and an edge leading to right assigned a 1, and again a right assigned by 1 and last leading to right assigned a 1 gives the bit string 11111 and is represented by the character u.
Starting from the root leading to right assigned a 1 and edge leading to right assigned a 1 and an edge leading to right assigned a 1, and again a right assigned by 1 and at last leading to a left assigned a 0 gives the bit string 11110 and is represented by the character p.
Starting from the root leading to right assigned a 1 and edge leading to right assigned a 1 and an edge leading to a 0 to left and a left leading to a zero gives the bit string 1100 and is represented by the character k.
Starting from the root leading to right assigned a 1 and edge leading to right assigned a 1 and an edge leading to a 0 to left and a right leading to a 1 gives the bit string 11 01 and is represented by the character o.
Hence, from the tree, the prefix codes for the characters a, e, i, k,o, p and u are
000,001,01,1100,1101,11110 and 11111 respectively.
