(3) If more than two nodes have the same least frequency, then you have to merge the two that bave the least and the second least label in lexical order. Please draw the full Huffman tree.

題組內容

4. Huffman tree : Huffimnan algorithm is a variable-length encoding method, in which a Huffiman tree is constructed. Suppose seven symbols A, B, C, D, E, F, G with frequencies 8, 15, 1, 6, 15, 3, 7, respectively, are given. You have to obey the following rules for constructing the Hufiman tree:

3. Two-way insertion sort : Suppose the output sorted sequence is increasing. The two-way insertion sort is a modification of the simple insertion sort (straightforward insertion sort), described as follows. After read the input elements, a separate output array a[0], a[1], a[2], a[n-1] is used to store the sorted sequence. This output array acts as a circular structure, that is, the right position of a[i] is a[i+1] if 0≤ i ≤ n-2, and the right position of a[n-1] is a[0]. The first input element is put into a[0] initially. Once a contiguous group of elements are in the array, room for a new input element is made by shifting all smaller elements one step to the left or all larger element one step to the right. The choice of left-shift or right-shift to perform depends on which would cause the smallest amount of shifts. Use the following 6 input elements to illustrate how this algorithm works. You have to show the content of the output array after each input element is inserted into the array. 27,35,43, 31,29,33.

題組內容

(3) If more than two nodes have the same least frequency, then you have to merge the two that bave the least and the second least label in lexical order. Please draw the full Huffman tree.

相關申論題

相關試卷