CHAP. 10] BINARY TREES 261
HUFFMAN ALGORITHM, GENERAL TREES
10.30. Consider the 2-treeTin Fig. 10-36(a) which contains the lettersA,B,C,D,E,F,Gas external nodes. Find the
Huffman coding of the letters determined by the treeT.
10.31. Find the weighted path lengthPof the tree in Fig. 10-36(a) if the data itemsA,B,...,Gare assigned the following
weights:
(A, 13 ), (B, 2 ), (C, 19 ), (D, 23 ), (E, 29 ), (F, 5 ), (G, 9 )
10.32. Using the data in Problem 10.31, find a Huffman coding for the seven letters using a 2-tree with a minimum path
lengthP, and findP.
10.33. LetTbe the general tree in Fig. 10-36(b). Find the corresponding binary treeT′.
Fig. 10-36COMPUTER PROBLEMS
Problems 10.34 to 10.40 refer to Fig. 10-37 which is a list of employee records stored in memory. It is a binary search
tree with respect to the NAME key. It uses a pointer HEAD where the number of employees is in SSN[HEAD], the total salary
is in SALARY[HEAD], and the root of the tree is in LEFT[HEAD]. Also, to allow insertions, the available (empty) locations
form a linked list with AVAIL pointing to the first element in the list, and the linking is maintained by the array LEFT.
Fig. 10-3710.34. Draw a diagram of the binary search tree NAME.
10.35. Write a program which prints the list of employee records in alphabetical order. (Hint: Print the records in inorder.)
10.36. Write a program which reads the nameNNNof an employee and prints the employee’s record. Test the program using
(a) Evans; (b) Smith; and (c) Lewis.