Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 10] BINARY TREES 257

(b) The inorder traversal ofTfollows:

A, D, E, F, G, H, J, M, P, Q, R, W

Observe that this is the alphabetical listing of the letters. (The inorder traversal of any binary search treeTyields

a sorted list of the nodes.)

10.11. Consider the binary treeTin Fig. 10-28(a). Describe the treeTafter: (a) the nodeMand (b) the nodeD

are deleted.

(a) The nodeMhas only one child,P. Hence deleteMand letPbecome the left child ofRin place ofM.

(b) The nodeDhas two children. Find the inorder successor ofD, which is the nodeE. First deleteEfrom the tree,

and then replaceDby the nodeE.

Fig. 10-28(b) shows the updated treeT.

10.12. LetHbe the minheap in Fig. 10-29(a). (His aminheapsince the smaller elements are on top of the heap,

rather than the larger elements.) Describe the heap after ITEM=11 is inserted intoH.

Fig. 10-29

First insert ITEM as the next node in the complete tree, that is, as the left child of node 44. Then repeatedly

compare ITEM with its PARENT, and interchange ITEM and PARENT as long as ITEM<PARENT. Since 11<44,

interchange 11 and 44. Since 11<22, interchange 11 and 22. Since 11>8, ITEM=11 has found its appropriate

place in the heapH. Figure 10-29(b) shows the final heapH. The shaded edges indicate the path of ITEM as it moves

up the tree.

PATH LENGTHS, HUFFMAN’S ALGORITHM

10.13. LetTbe the weighted 2-tree in Fig. 10-30(a). Find the weighted path lengthPof the treeT.

Multiply each weightWiby the lengthLiof the path from the root ofTto the node containing the weight, and

then sum all such products to obtainP. Thus:

P= 4 ( 2 )+ 15 ( 4 )+ 25 ( 4 )+ 5 ( 3 )+ 8 ( 2 )+ 16 ( 2 )

= 8 + 60 + 100 + 15 + 16 + 32

= 231

10.14. Suppose the six weights 4, 15, 25, 5, 8, 16 are given. Find a 2-treeTwith the given weights and with a
minimum path lengthP. (CompareTwith the tree in Fig. 10-30(a).)
Use Huffman’s algorithm. That is, repeatedly combine the two subtrees with minimum weights into a single
subtree as follows:
(a) 4 , 15 , 25 , 5 , 8 , 16 ; (d) 25 , 17 , 31
;
(b) 15 , 25 , 9
, 8 , 16 ; (e) 42
, 31 ;
(c) 15 , 25 , 17
, 16 ; (f ) 73
.