I. Essay questions (50 pts) Use the Huffman Tree in Figure 6.5 on Page 300 to do
ID: 3598677 • Letter: I
Question
I. Essay questions (50 pts)
Use the Huffman Tree in Figure 6.5 on Page 300 to do the following:
1. Encode the word “halloween”
2. Decode the binary string: 1000100001100100111101
300 Chapter 6 Trees FIGURE 6.5 Huffman Code Tree 01 0 1 Lu p) g 0 1 However, to decode a file of letters and spaces, you walk down the Huffman tree, starting at the root, until you reach a letter and then append that letter to the out- put text. Once you have reached a letter, go back to the root. Here is an example. The substrings that represent the individual letters are shown in alternate colors to help you follow the process. The underscore in the second line represents a space character (code is 111). 10001010011110101010100010101110100011 -e a Huffman trees are discussed further in Section 6.6. A Binary Search Tree The tree in Figure 6.2 is a binary search tree because, for each node, all words in its left subtree precede the word in that node, and all words in its right subtree follow the word in that node. For example, for the root node dog, all words in its left sub- tree (cat, canine) precede dog in the dictionary, and all words in its right subtree (wolf follow dog. Similarly, for the node cat, the word in its left subtree (canine) precedes . There are no duplicate entries in a binary search tree. More formally, we define a binary search tree as follows: A set of nodes T is a binary search tree if either of the following is true: T is empty If T is not empty, its root node has two subtrees, T, and TR, such that T, and TR are binary search trees and the value in the root node of T is greater than all values in T, and is less than all values in TRExplanation / Answer
Solution:
Let's start decoding the word halloween
we will go letter by letter and then combine them
h=> 0001
o=> 1001
l=> 10111
l=> 10111
o=> 1001
w=> 110001
e=> 010
e=> 010
n=> 0111
0001100110111100110111101110100100111
Let's decode the string: 1000100001100100111101
100010 is g
0001 is h
1001 is o
0011 is s
1101 is t
and the decoded binary string is ghost.
Please, please upvote and ask your doubts in the comments.